stl — сложность C ++ std :: unordered_map
Я много читал о unordered_map (C ++ 11) время сложность здесь, в stackoverflow, но я не нашел ответа на свой вопрос.
Давайте предположим индексацию по целому числу (только для примера):
Функции insert / at работают постоянно (в среднем времени), поэтому в этом примере потребуется O (1)
std::unordered_map<int, int> mymap = {
{ 1, 1},
{ 100, 2},
{ 100000, 3 }
};
Что меня интересует, так это то, сколько времени требуется, чтобы перебрать все (несортированные) значения, хранящиеся в карте — например,
for ( auto it = mymap.begin(); it != mymap.end(); ++it ) { ... }
Можно ли предположить, что к каждому сохраненному значению обращаются только один раз (или дважды, или с постоянным временем)? Это подразумевает, что итерация всех значений находится в N-значном отображении O (N). Другая возможность состоит в том, что мой пример с ключами {1,10,100000} может занять до 1000000 итераций (если представлен массивом)
Есть ли какой-либо другой контейнер, который может быть линейно повторен и значение которого постоянно доступно по заданному ключу?
Что мне действительно нужно, так это (Псевдокод)
myStructure.add(key, value) // O(1)
value = myStructure.at(key) // O(1)
for (auto key : mySructure) {...} // O(1) for each key/value pair = O(N) for N values
Является ли std :: unordered_map необходимой мне структурой?
Целочисленная индексация достаточна, средняя сложность также.
Решение
Независимо от того, как они реализованы, стандартные контейнеры предоставляют итераторы, которые отвечают требованиям итераторов. Для увеличения итератора требуется постоянное время, поэтому итерация по всем элементам любой стандартный контейнер O (N).
Другие решения
Гарантии сложности всех стандартных контейнеров указаны в Стандарт C ++.
std::unordered_map доступ к элементу и вставка элемента должны быть сложными O(1) в среднем и O(N) наихудший случай (см. разделы 23.5.4.3 и 23.5.4.4; страницы 797-798).
Конкретная реализация (то есть реализация стандартной библиотеки конкретного поставщика) может выбирать любую структуру данных, какую пожелает. Однако, чтобы соответствовать Стандарту, их сложность должна быть по крайней мере как указано.
Существует несколько различных способов реализации хеш-таблицы, и я предлагаю вам больше узнать о них, если вам интересно, но основные два — через цепочку и открытую адресацию.
В первом случае у вас есть массив связанных списков. Каждая запись в массиве может быть пустой, каждый элемент в хеш-таблице будет находиться в некотором сегменте. Таким образом, итерация идет по массиву, и по каждому непустому списку в нем. Ясно, что O (N), но потенциально может быть очень неэффективно в зависимости от того, как распределены связанные списки.
Во втором случае у вас есть только один очень большой массив, в котором будет много пустых слотов. Здесь итерация снова явно линейна, но может быть неэффективной, если таблица в основном пуста (что должно быть в целях поиска), потому что фактически присутствующие элементы будут находиться в разных строках кэша.
В любом случае, у вас будет линейная итерация, и вы будете касаться каждого элемента ровно один раз. Обратите внимание, что это верно для std::map итерация там тоже будет линейной. Но в случае карт итерация определенно будет гораздо менее эффективной, чем итерация вектора, так что имейте это в виду. Если в вашем сценарии использования требуется ОБА быстрый доступ и быстрая итерация, если вы вставляете все свои элементы заранее и никогда не стираете, было бы гораздо лучше иметь и карту, и вектор. Возьмите дополнительное пространство для дополнительной производительности.