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

Ответ 1

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

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

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

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

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

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

Ответ 2

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

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

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

Ответ 3

быстрее искать элемент против множества, чем вектор (O (log (n)) vs O (n)). Чтобы выполнить поиск элемента по вектору, вам необходимо выполнить итерацию всех элементов в векторе, но для использования поиска используйте красно-черное дерево для оптимизации поиска. Посмотрите только на несколько элементов, чтобы найти совпадение.

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

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

Ответ 4

form cpluplus.com набор:

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

так что множество упорядочено И элемент однозначно представлен

а vect:

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

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

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

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

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

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