Какова разница в производительности между использованием итератора для циклического перехода по карте STL по сравнению с вектором? Я хотел бы использовать ключ карты для вставки, удаления и некоторых доступов, но мне также нужно делать регулярный доступ к каждому элементу на карте.
Производительность доступа к Итератору для карты STL против вектора?
Ответ 1
С обоими картами и векторами, итерация по всей коллекции равна O (N). однако вектор векторного вектора (например, векторный вектор) хранит элементы смежно, поэтому доступ к следующему элементу намного дешевле, потому что он будет использовать кеш оптимально, тогда как карта не будет.
Но поскольку вам нужно искать на основе ключей, на самом деле нет альтернативы. Вы можете использовать вектор пар, отсортированный по первому элементу, но если сбор должен быть изменен, это будет очень медленным. Просто используйте карту.
Ответ 2
Итерация через каждый элемент отображения принимает O (n) время. wikipedia
Ответ 3
Эта ссылка имеет хорошую таблицу производительности для различных операций над всеми контейнерами STL.
Вообще говоря, если вам нужно сделать много вставки, удаления или поиска на основе ключа, тогда карта - это путь.
Если вам нужно только один раз настроить контейнер, а затем получить доступ к нему, как массив, то используйте вектор.
EDIT: таблица производительности операций контейнера STL:
Ответ 4
Итерация через карту может быть линейной, но практически, она не настолько эффективна из реализаций на С++. Поэтому мой совет - использовать вектор и использовать другую карту для поиска элементов в векторе в линейном времени.
Ответ 5
Просмотр дерева не дорого (grosso modo, например, связанный список), вы не сможете извлечь выгоду из кеша с помощью вектора, но обычно это то, что вы делаете, когда вы итерируете, что дорого, а не сама итерация.
Не могли бы вы рассказать нам больше о том, что вы ожидаете делать, когда вы повторяете всю карту?
Ответ 6
Используйте карту, если вам нужен быстрый способ доступа с помощью ключа. В противном случае используйте вектор все время, пока не будут обнаружены некоторые проблемы с производительностью с профилировщиком.