He leído mucho sobreunordered_map (c ++ 11) complejidad de tiempo aquí en stackoverflow, pero no he encontrado la respuesta a mi pregunta.

Asumamos la indexación por entero (solo por ejemplo):

Las funciones Insert / at trabajan constantemente (en tiempo promedio), por lo que este ejemplo tomaría O (1)

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

Lo que me interesa es cuánto tiempo se tarda en recorrer todos los valores (sin clasificar) almacenados en el mapa, por ejemplo.

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

¿Puedo suponer que se accede a cada valor almacenado solo una vez (o dos veces o tiempos constantes)? Eso implicaría que la iteración a través de todos los valores se encuentra en el mapa O con valor N (N). La otra posibilidad es que mi ejemplo con claves {1,10,100000} podría tomar hasta 1000000 iteración (si está representado por una matriz)

¿Hay algún otro contenedor que se pueda iterar de forma lineal y que se pueda acceder al valor mediante una clave determinada constantemente?

Lo que realmente necesitaría es (pseudocódigo)

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

¿Es std :: unordered_map la estructura que necesito?

La indexación de enteros es suficiente, la complejidad promedio también.