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

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

какова реальная причина?

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

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

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

7 54
c++ castle-windsor performance

7 ответов:

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

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

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

55

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

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

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

27

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

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

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

22

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

4

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

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

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

3

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

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

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

2

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

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

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

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

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

0