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

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

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

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

Действительно ли какой-либо другой тариф/хуже, чем карта при фрагментации виртуального адресного пространства?

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

Ответ 1

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

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

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

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

Ответ 2

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

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

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

Ответ 3

"По умолчанию используйте вектор, когда вам нужен контейнер" - Bjarne Stroustrup.

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

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

Ответ 4

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

Ответ 5

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

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

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

Ответ 6

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

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

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

Ответ 7

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

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

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

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

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