вектор или карта, который использовать?
6 ответов
Я предполагаю, что Вы соответствуете map<A, B> vector<pair<A, B> >.
Во-первых, находя объект в очень маленьком векторе может легко быть быстрее, чем то же самое в карте, потому что вся память в векторе всегда непрерывна (и так игры более приятно с кэшами компьютеров и такими вещами), и количество сравнений должно было найти, что что-то в векторе могло бы быть о том же что касается карты. Для нахождения элемента в карте нужно меньше операций в пределе очень больших контейнеров.
точка, где карты становятся быстрее, чем векторы, зависит от реализации от Вашего процессора, какие данные находятся в карте и тонких вещах как то, какая память находится в кэше процессора. Как правило, точка, где карта становится быстрее, была бы приблизительно 5-30 элементами.
альтернатива должна использовать контейнер хеша. Их часто называют hash_map или unordered_map. Классы, названные hash_map, не являются частью официального стандарта (и существует несколько вариантов там); std::tr1::unordered_map. Карта хеша часто быстрее, чем карта нормалей для поисков, независимо от того, сколько элементов находится в ней, но быстрее ли это на самом деле, зависит от того, каков ключ, как она хешируется, что оценивает Вас, должны иметь дело с, и как ключ сравнен в станд.:: карта. Это не сохраняет вещи в определенном порядке как станд.:: карта, но Вы сказали, что не заботитесь об этом. Я рекомендовал бы карты хеша особенно, если ключи являются целыми числами или указателями, потому что они хешируют очень быстро.
Карты обычно реализуются как деревья двоичного поиска, и обход двоичного дерева всегда идет с немного служебным (работающие сравнения, обходя ссылки, и т.д.), векторы являются в основном просто массивами. Для очень небольших количеств данных, возможно, 8 или 12 элементов, иногда это быстрее только, чтобы сделать линейный поиск по массиву, чем обойти дерево двоичного поиска.
можно выполнить некоторые синхронизации сами для наблюдения, где точка безубыточности - время поиск более чем четыре элемента, тогда восемь, тогда шестнадцать, и так далее для нахождения зоны наилучшего восприятия для конкретной реализации STL.
Карты действительно имеют тенденцию иметь набор маленьких выделений на всем протяжении "кучи", тогда как векторы непрерывны, таким образом, уровень удачного обращения в кэш векторов может иногда быть немного лучше в случаях, где Вы выполняете итерации по всем элементам по всей длине.
"По умолчанию используйте вектор при необходимости в контейнере" - Bjarne Stroustrup.
Иначе, я нахожу, что эта небольшая блок-схема очень хорошей справки:
При выполнении всех вставок сразу тогда выполнение большого количества поисков можно использовать вектор и отсортировать его, когда Вы посредством вставки; тогда используйте lower_bound, чтобы сделать быстрый поиск. Это могло бы быть быстрее, чем использование карты, даже для больших количеств объектов.
Я думаю, что необходимо использовать контейнер, который соответствует данным прежде всего. станд.:: вектор используется в ситуациях, где Вы использовали бы массив в C++ перед STL или C: Вы хотите, чтобы непрерывный блок памяти снабдил значения быстрым постоянным поиском времени. станд.:: карта должна использоваться для отображения ключей к значениям. Основное перекрытие здесь является вектором по сравнению с картой с size_t как ключ. В этом случае существует две проблемы: действительно ли индексы непрерывны? В противном случае Вы будете, вероятно, тратить впустую память с вектором. Во-вторых, какое время поиска Вы хотите? Вектор имеет постоянный поиск времени, в то время как станд.:: карта обычно реализуется как дерево RB, которое имеет O (зарегистрируйте n), время поиска, и даже карта хеша (такая как TR1 unordered_map) обычно имеет худшую сложность, потому что индекс (или хеш этого) будет отображен на блоке, который может содержать несколько значений.
, Если стремились к вектору с парами: Вы могли, элементы вектора и использования находят для нахождения элементов. Но это - двоичный поиск и практически будет с такой скоростью, как станд.:: карта.
Так или иначе, попытайтесь смоделировать данные очевидным способом. Преждевременная оптимизация часто не помогает многому.
Другой способ посмотреть на это, то, если мы говорим о маленьких контейнерах, тогда никакой не собирается взять очень долго для поиска. Если Вы не перероете этот контейнер на очень жестком цикле, разница во времени, вероятно, будет незначительна.
В этом случае, я искал бы, какой контейнер более тесно соответствует тому, что Вы хотите сделать. При поиске конкретного значения встроенная находка карты (), метод будет намного легче (и менее сложным для использования), чем создание для цикла и итерации по вектору.
Вы время, вероятно, стоит намного больше, чем несколько наносекунд тут и там.