Выбор контейнера STL для очень большого списка

Question

У меня очень большой список элементов (~ 2 миллиона), которые я хочу оптимизировать для скорости доступа. Я перебираю элементы, используя итератор (++ it).
Прямо сейчас код реализован с использованием std:map<std::wstring, STRUCT>.
Интересно, стоит ли менять std :: map на std::deque<std::pair<std::wstring, STRUCT>>. Я думаю, что у меня было бы преимущество использования арифметики указателей и минимизации пропадания кэша. Стоит?
Я знаю, что профилирование - это ответ, но мне нужно мнение перед тем, как это реализовать ...

Answer 1

Если вы заранее знаете размер, тогда std :: Vector определенно поможет вам, если ваши объекты не слишком большие.

std::vector<Object> list;
list.reserve(2000000);

А затем заполните его как обычно.

Это самый быстрый и наименее потребляющий память подход.Тем не менее, вы должны быть в состоянии выделить достаточно непрерывной памяти.Но за исключением случаев, когда ваш объект имеет размер 1 КБ, это не должно быть проблемой.

Answer 2

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

Общая производительность приложения, конечно, будет зависеть от того, сколько разВы повторяете, и как вы строите свои данные в первую очередь.Для простого теста, как только ваша карта будет заполнена, вы можете построить вектор из нее следующим образом:

vector<pair<K,V> > myvec(mymap.begin(), mymap.end());

Где K и V - ключевые и тип значения карты.Затем просто используйте векторные итераторы вместо итераторов карты и сравните производительность.

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

Answer 3

Как правило, если вы выполняете поиск только в этом наборе (без вставок / удалений), вам, вероятно, лучше использовать отсортированный последовательный монетодержатель, например, deque или vector.Затем вы можете использовать простой двоичный поиск, чтобы найти необходимые элементы.Преимущество использования последовательного контейнера состоит в том, что он лучше с точки зрения использования памяти, имеет очень простую реализацию и обеспечивает лучшую локальность ссылок.Я написал бы одну версию кода с использованием вектора, а другую версию кода с использованием deque, а затем сравнил бы их с точки зрения соответствия требованиям, чтобы решить, какой из них использовать в окончательной версии.необходимо обновить (нужно вставить новые элементы или часто удалять старые элементы), лучше выбрать карту.Или, может быть, вам просто нужно полностью удалить контейнеры STL и просто использовать базу данных в памяти (см. SQLite), но это сильно зависит от того, какую проблему вы решаете.

Answer 4

С deque вы потеряете (или должны будете заново реализовать) преимущество пар ключ-значение. Если это не важно для ваших данных, я бы рассмотрел использование deque.