C++ список STL по сравнению с набором

std :: list - O (1) для вставки и удаления. Но вам может потребоваться O (n), чтобы найти точку вставки или удаления. std :: set - O (log (n)) для вставок и удалений, обычно он реализуется как красно-черное дерево.

Примите во внимание усилия по поиску точки вставки / удаления, чтобы сделать свой выбор.

Сначала подумайте о семантике, а затем о производительности.

Если у вас есть набор целых чисел и вы вставите в него целые числа 6, 8, 13, 8, 20, 6 и 50, вы получите набор, содержащий следующие пять элементов: { 6, 8, 13, 20, 50}.

Если вы сделаете это со списком, вы получите список, содержащий следующие семь элементов: {6, 8, 13, 8, 20, 6, 50} .

Итак, чего вы хотите? Нет смысла сравнивать скорость контейнеров с такой разной семантикой.

Если вы заботитесь о скорости, то вам лучше использовать std::vector. std::list выполняет одно выделение кучи каждый раз, когда вставляется элемент, и это обычно является узким местом.

Исключение составляют случаи, когда отдельные элементы очень дорого копировать, или когда у вас их очень много. В таких случаях список, скорее всего, будет работать лучше, поскольку ему не нужно перемещать элементы при изменении размера. std::deque также является хорошим вариантом, но для выбора между этими двумя вариантами вам потребуется профилировать ваше приложение.

Наконец, используйте std::set, только если вам нужно сохранить элементы отсортированными (или если вам не нужны повторяющиеся элементы). В противном случае он будет работать значительно медленнее, чем список или вектор.

Список

1. Поиск (линейное время).
2. Вставка, удаление, перемещение (занимает постоянное время).
3. Элементы могут быть упорядочены.
4. Элементы могут быть отсортированы.
5. Элементы могут дублироваться.

Набор

1. Поиск (логарифмический по размеру).
2. Вставка и удаление (логарифмически в общем случае).
3. Элементы не упорядочены.
4. Элементы всегда сортируются от меньшего к большему.
5. Элементы уникальны.

В списке std::list вставка и удаление занимают время O(1), что означает очень быстро, и прежде всего означает скорость, которая не зависит от количества элементов в списке.

В std::set вставка и удаление занимают время O(log(N)), что означает немного медленнее, если в наборе содержится много элементов. N в выражении O(log(N)) означает количество элементов. Grosso modo, это означает, что время, затрачиваемое на операцию, как бы пропорционально логарифму (основание здесь не имеет значения, так как это эквивалентно умножению на константу, которая игнорируется при теоретическом анализе алгоритмов) числа элементов в множестве.

Но крайне важно учитывать время, затрачиваемое на поиск элемента для удаления. Если вы должны перебрать весь контейнер в поисках элемента, который нужно удалить, что, скорее всего, так и будет, то std::list займет довольно много времени для этого поиска, которое будет в O(N) (что означает не быстро, потому что время прямо пропорционально количеству элементов, а не логарифму от него), в то время как std::set займет время в O(log N) для поиска.

Также отметим, что эти теоретические анализы становятся абсолютно недействительными для контейнеров с очень малым количеством элементов, и в этом случае скрываемые ими множительные константы становятся более важными, чем семейство временных функций, на котором они фокусируются.

Вкратце: std::list => Медленнее для поиска элемента для удаления; быстрее для его удаления. std::set => Быстрее для поиска элемента для удаления; менее быстро для его удаления.

Но для всей операции, и для большого количества элементов, std::set лучше.

Вы также должны рассмотреть возможность использования хэш-таблиц. Хорошие их реализации есть в Boost, Qt или C++0x. Они выполняют все эти операции за время, стремящееся к O(1) (что означает очень очень быстро).

Вы должны сами измерить производительность при реальном использовании на реальных данных. Проверьте как типичную, так и наихудшую производительность.

Хотя std::vector имеет временную сложность O(N) для случайной вставки, std::set O(log(N)) и std::list O(1), std::vector работает лучше во многих случаях. Только если производительность не настолько важна, чтобы тратить время на ее измерение, переходите к сложности big-O.

"Если вы не измеряете, вы не занимаетесь проектированием" (Рико Мариани)