Производительность доступа итератора для карты STL против вектора?

Question

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

Answer 1

И с картой, и с вектором повторение всей коллекции равно O (N). однако (например, список против вектора) вектор хранит элементы непрерывно, поэтому доступ к следующему элементу намного дешевле, поскольку он будет оптимально использовать кэш, а карта - нет.

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

Answer 2

Итерация по каждому элементу карты занимает O (n) времени. википедии

Answer 3

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

Вообще говоря, если вам нужно много вставлять, удалять или искать по ключу, тогда карта - путь.

Если вам нужно настроить контейнер только один раз, а затем обращаться к нему как к массиву, используйте вектор.

РЕДАКТИРОВАТЬ: Таблица производительности операций контейнера STL:

Answer 4

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

Answer 5

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

Не могли бы вы рассказать нам больше о том, что вы ожидаете сделать, когда будете перебирать всю карту?

Answer 6

Используйте карту, если вам нужен быстрый способ доступа по ключу. В противном случае используйте вектор постоянно, если с профилировщиком не будут обнаружены проблемы с производительностью