Контейнерная сложность

Question

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

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

Answer 1

Как вы хотите, 'const' сортированный контейнер, предлагаю std::vector, который является кэш-памяти.

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

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

Инициализация O(n log n).

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