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 необходимой мне структурой?

Целочисленная индексация достаточна, средняя сложность также.