В чем разница между std::set и std::vector?

Question

В чем разница между std::set и std::vector?

сейчас я изучаю STL. Я читал о set контейнер. У меня есть вопрос, когда вы хотите использовать set? После прочтения описание набора похоже, это бесполезно, потому что мы можем заменить его на vector. Не могли бы вы сказать плюсы и cos для vector vs set контейнеров. Спасибо

774 4

c++stl

4 ответов:

Comments

Ничего не найдено.

Nicol Bolas · Accepted Answer · 2016-05-04 23:05:25

A set прикажут. Это гарантированный чтобы оставаться в определенном порядке, в соответствии с функтором, который вы предоставляете. Независимо от того, какие элементы вы добавляете или удаляете (если вы не добавляете дубликат, который не разрешен в set), Он всегда будет заказана.

A vector ровно и только заказ вы явно даете его. Элементы vector находятся там, где вы их положили. Если вы приведете их в негодность, тогда они не в порядке; теперь вы надо sort контейнер, чтобы вернуть их в порядок.

по общему признанию,set имеет относительно ограниченное применение. При надлежащей дисциплине можно было бы вставлять элементы в vector и держать его в порядке. Однако, если вы постоянно вставляете и удаляете элементы из контейнера,vector столкнется со многими проблемами. Он будет делать много копирования / перемещения элементов и так далее, так как это фактически просто массив.

время, необходимое для вставки элемента в a vector пропорционально количеству элементов уже в vector. Время, необходимое для вставки элемента в set пропорционально log₂ из числа пунктов. Если количество предметов велико, это огромная разница. log₂ (100,000) - это ~16; это значительное улучшение скорости. То же самое касается и удаления.

однако, если вы делаете все ваши вставки сразу, во время инициализации, то нет никаких проблем. Вы можете вставить все в vector, сортировать его (заплатив эту цену один раз), а затем использовать стандартные алгоритмы для сортировки vectors для поиска элементов и перебора отсортированного списка. И в то время как итерация по элементам set не совсем медленно, повторяя над vector быстрее.

так что есть случаи, когда сортировка vector бьет a set. При этом вы действительно не должны беспокоиться о расходах на такого рода оптимизацию, если не знаете, что это необходимо. Так что используйте set Если вы у вас есть опыт работы с системой, которую вы пишете (и, следовательно, знаете, что вам нужна эта производительность) или есть данные профилирования в руке, которые говорят вам, что вам нужно vector, а не set.

dasblinkenlight · Accepted Answer · 2011-12-31 08:34:55

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

конечно, вы можете поддерживать вектор уникальных элементов, но ваша производительность будет сильно страдать, когда вы выполняете операции, ориентированные на набор. Например, предположим, что у вас есть набор из 10000 элементов и вектор из 10000 различных неупорядоченных элементов. Теперь предположим, что вам нужно проверить, является ли значение X среди значений в наборе (или среди значений в векторе). Если X не входит в число предметов, поиск вектора будет примерно в 100 раз медленнее. Вы увидите аналогичные различия в производительности при вычислении объединений наборов и пересечений.

подводя итог, наборы и векторы имеют разные цели. Вы можете использовать вектор вместо набора, но это было требуется больше работы, и, вероятно, повредит производительность довольно сильно.

Zang MingJie · Accepted Answer · 2011-12-31 08:39:18

это быстрее, для поиска элемента с набором, чем вектор (за o(журнал(N)) против o(n) времени). Для поиска элемента по вектору вам нужно перебрать все элементы в векторе, но набор использует красно-черное дерево для оптимизации поиска, только несколько элементов будут искать, чтобы найти совпадение.

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

но вектор неупорядочен, вы можете перемещать его с помощью вставки порядок.

jo_ · Accepted Answer · 2016-12-08 19:27:32

форма cpluplus.com набор:

наборы-это контейнеры, которые хранят уникальные элементы после определенного порядок.

таким образом, набор упорядочен и элемент однозначно представлен

в то время как vect:

векторы-это контейнеры последовательностей, представляющие массивы, которые могут изменяться размер.

таким образом, вектор находится в порядке его заполнения и может содержать несколько одинаковых элементов

предпочитаю набор:

если вы хотите отфильтровать несколько одинаковых значений

если вы хотите разобрать элементы в указанном порядке (для этого в vector требуется специально отсортировать вектор).

предпочитаю вектор:

если вы хотите сохранить одинаковые значения

если вы хотите разобрать элементы в том же порядке, как вы нажали их (предполагая, что вы не обрабатываете порядок вектора)