Eu li muito sobreunordered_map (c ++ 11) complexidade do tempo aqui no stackoverflow, mas não encontrei a resposta para a minha pergunta.

Vamos supor indexação por inteiro (apenas por exemplo):

As funções inserir / at trabalham constantemente (em tempo médio), então este exemplo levaria O (1)

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

O que eu estou curioso sobre quanto tempo demora para percorrer todos os valores (não separados) armazenados no mapa - por exemplo,

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

Posso supor que cada valor armazenado seja acessado apenas uma vez (ou duas vezes ou constantes)? Isso implicaria que a iteração através de todos os valores está no mapa N-valorado (N). A outra possibilidade é que meu exemplo com chaves {1,10,100000} poderia levar até a iteração de 1000000 (se representada por array)

Existe algum outro contêiner, que pode ser iterado linearmente e valor acessado por uma determinada chave constantemente?

O que eu realmente preciso é (pseudo-có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

Std :: unordered_map a estrutura que eu preciso?

Indexação inteira é suficiente, complexidade média também.