вектор или карта, какой использовать?

Question

Я слышал, как многие люди говорили, что если число элементов, ожидаемых в контейнере, относительно мало, лучше использовать std::vector вместо std::map, хотя я использую контейнер только для поиска, а не для итерации.

Какова реальная причина этого?

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

Есть ли вектор лучше или хуже, чем карта при фрагментации виртуального адресного пространства?

Я использую библиотеку STL, которая поставляется вместе с Visual Studio (то есть реализация Microsoft), это имеет какое-либо отличие от других реализаций?

Answer 1

Полагаю, вы сравниваете map<A, B> с vector<pair<A, B> >.

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

Точка, в которой карты становятся быстрее, чем векторы, зависит от реализации, от вашего процессора, от того, какие данные находятся на карте, и от тонких вещей, таких как объем памяти в кеше процессора. Как правило, точка, где карта становится быстрее, будет около 5-30 элементов.

Альтернативой является использование хеш-контейнера. Их часто называют hash_map или unordered_map. Классы с именем hash_map не являются частью официального стандарта (и существует несколько вариантов); std::tr1::unordered_map есть. Хеш-карта часто быстрее, чем обычная карта для поиска, независимо от того, сколько в ней элементов, но насколько она на самом деле быстрее, зависит от того, что является ключом, как он хэшируется, с какими значениями вам приходится иметь дело, и как ключ сравнивается в std :: map. Он не хранит вещи в определенном порядке, например, std :: map, но вы сказали, что вас это не волнует. Я бы порекомендовал карты хешей, особенно если ключи целые или указатели, потому что они очень быстро.

Answer 2

Карты обычно реализуются в виде бинарных деревьев поиска, и обход бинарного дерева всегда сопряжен с небольшими издержками (выполнение сравнений, обход ссылок и т. Д.). Векторы - это в основном просто массивы. Для очень небольших объемов данных, может быть, 8 или 12 элементов, иногда просто выполнить линейный поиск по массиву быстрее, чем обходить двоичное дерево поиска.

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

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

Answer 3

«По умолчанию используйте вектор, когда вам нужен контейнер» - Бьярн Страуструп.

В остальном я нахожу эту небольшую блок-схему очень полезной:

http://homepages.e3.net.nz/~djm/cppcontainers.html

Answer 4

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

Answer 5

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

В этом случае я бы посмотрел, какой контейнер более соответствует тому, что вы хотите сделать. Если вы ищете конкретное значение, встроенный в карту метод find () будет намного проще (и менее сложен в использовании), чем создание цикла for и итерация по вектору.

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

Answer 6

Я думаю, что вы должны использовать контейнер, который в первую очередь соответствует данным. std :: vector используется в ситуациях, когда вы используете массив в C или pre-STL C ++: вам нужен непрерывный блок памяти для хранения значений с быстрым постоянным поиском по времени. std :: map должен использоваться для сопоставления ключей со значениями. Основным перекрытием здесь является вектор против карты с ключом size_t. В этом случае есть две проблемы: индексы непрерывны? Если нет, вы, вероятно, будете тратить память с вектором. Во-вторых, какое время поиска вы хотите? Вектор имеет постоянный поиск по времени, в то время как std :: map обычно реализуется как дерево RB, которое имеет время поиска O (log n), и даже хэш-карта (такая как TR1 unordered_map) обычно имеет худшую сложность, потому что индекс (или его хеш) будет отображен в корзину, которая может содержать несколько значений.

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

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

Answer 7

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

Но иногда std::vector можно использовать вместо std::map даже для поиска.

Если в ваших парах ключ-значение будет очень мало элементов, вы можете выполнить итеративный поиск по ключу даже в std::vector<std::pair<x,y>>.

Это связано с тем, что хеширование требует времени, особенно для хеширования строк и других операций на карте, таких как хранение данных в куче.

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