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

Question

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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

Answer 4

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

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

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

, а vect:

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

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

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

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

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

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