Список С++ STL и набор

Ответ 1

List

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

Set

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

Ответ 2

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

Рассмотрите возможность поиска точки вставки/удаления, чтобы сделать ваш выбор.

Ответ 3

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

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

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

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

Ответ 4

В 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 или С++ 0x. Они выполняют все эти операции во времени, стремясь к O (1) (что очень быстро).

Ответ 5

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

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

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

Ответ 6

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

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

"Если вы не измеряете, что не разрабатываете" (Rico Mariani)