итерация упорядоченных и неупорядоченных контейнеров

Давайте рассмотрим set против unordered_set.

Основное отличие здесь заключается в «природе» итерации, то есть обход набора даст вам элементы по порядку, а обход диапазона в неупорядоченном наборе даст вам набор значений в произвольном порядке.

Предположим, вы хотите пройти через диапазон [it1, it2]. Если мы исключим время поиска, необходимое для поиска элементов it1 и it2, не может быть прямого сопоставления одного случая с другим, поскольку не гарантируется, что промежуточные элементы будут одинаковыми, даже если вы использовали одни и те же элементы для создания контейнера. .

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

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

С другой стороны, неупорядоченные наборы — это хеш-таблицы, и, насколько мне известно , реализация STL использует хеширование с цепочкой. Это означает (на очень высоком уровне), что для структуры используется (непрерывный) буфер, где каждый элемент является главой цепочки (списка), содержащей элементы. То, как элементы расположены в этих цепочках (сегментах) и в буфере, повлияет на время обхода, однако на этот раз вы снова будете гоняться за указателями, прыгая через разные списки. Я не думаю, что он будет сильно отличаться от случая с деревом, но точно не будет лучше.

В любом случае микронастройка и бенчмаркинг дадут вам ответ для вашего конкретного приложения.

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

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

Вообще говоря, производительность контейнера — довольно сложная тема, и обычно ее нужно тестировать в реальном приложении, чтобы получить надежный ответ. Существует множество вещей, определяемых реализацией, которые могут повлиять на производительность. Я бы выбрал hash_set, если бы мне пришлось идти вслепую. Копирование в vector также может оказаться хорошим вариантом.

РЕДАКТИРОВАТЬ: Как сказал @TonyD в своем комментарии, существует правило, запрещающее аннулировать итераторы во время добавления элемента, когда max_load_factor() не превышено, это практически исключает резервные контейнеры, которые непрерывны в памяти.

Таким образом, копирование всего в вектор кажется еще более разумным вариантом. Если вам нужно удалить дубликаты, возможным вариантом может быть использование http://en.cppreference.com/w/cpp/algorithm/sort и легкое игнорирование дубликатов. Я слышал, что использование vector и sort для отсортированного массива (или вектора) довольно часто используется в случае необходимости в контейнере, который должен быть сортировщиком и чаще повторяется, чем модифицируется.

итерация от самого быстрого к самому медленному должна быть: set > map > unordered_set > unordered_map; set немного легче, чем map, и они упорядочены по правилу двоичного дерева, поэтому должны работать быстрее, чем контейнеры unordered_.