Dużo czytałemmapa nieuporządkowana (c ++ 11) złożoność czasu tutaj w stackoverflow, ale nie znalazłem odpowiedzi na moje pytanie.

Załóżmy, że indeksowanie jest liczbą całkowitą (na przykład):

Funkcje insert / at działają stale (w średnim czasie), więc ten przykład zajmie O (1)

std::unordered_map<int, int> mymap = {
            { 1, 1},
            { 100, 2},
            { 100000, 3 }
};

Ciekawe, ile czasu zajmuje iterowanie wszystkich (nieposortowanych) wartości zapisanych na mapie - np.

for ( auto it = mymap.begin(); it != mymap.end(); ++it ) { ... }

Czy mogę założyć, że dostęp do każdej przechowywanej wartości ma tylko jeden raz (lub dwa razy lub stały czas)? Oznaczałoby to, że iteracja przez wszystkie wartości znajduje się na mapie O (N) o wartości N. Inną możliwością jest to, że mój przykład z kluczami {1,10,100000} może zająć do 1000000 iteracji (jeśli jest reprezentowana przez tablicę)

Czy istnieje jakikolwiek inny kontener, który można iterować liniowo i stale uzyskiwać dostęp do wartości przez dany klucz?

Naprawdę potrzebowałbym tego (pseudo kod)

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

Czy std :: unordered_map to struktura, której potrzebuję?

Indeksowanie całkowite jest wystarczające, średnia złożoność również.