C ++ STL список против набора

Question

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

Спасибо!

Answer 1

Список

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

Установить

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

Answer 2

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

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

Answer 3

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

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

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

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

Answer 4

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

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

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

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

Чтобы сделать его коротким: std :: list => Замедляет поиск удаляемого элемента; быстрее удалить его. std :: set => Ускорить поиск удаляемого элемента; менее быстро, чтобы удалить его.

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

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

Answer 5

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

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

«Если вы не измеряете, вы не инженер» (Рико Мариани)

Answer 6

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

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

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