Сложность контейнера

Question

Сложность контейнера

Следовательно, у меня есть std::set<int> а также std::list<int>,
Я хочу отсортировать мой контейнер.
Для набора у меня будет сложность, как O(nlogn) за n вставленные элементы.
Для списка у меня будет сложность, как O(n) для вставки n элементы + O(nlogn) для вызова list::sort,
В обоих случаях сложность O(nlogn), но есть дополнительные O(n) операции в случае std::list, И у меня есть некоторое постоянное время для set восстановление равновесия.

Вот вопрос, какой контейнер будет работать быстрее?

1

array-algorithms c++stl time-complexity

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Как хочешьConstотсортированный контейнер, предлагаю std::vector который кеш дружественен.

Во время инициализации:

push_back все элементы O(n),
std::sort вектор O(n log n),
std::unique если вы хотите удалить дубликаты (как std::set делает). O(n),

Итак, инициализация O(n log n),

Чтобы проверить, существует ли элемент, используйте std::binary_search иметь O(log n) вместо O(n),

2