C ++ 11: гарантирует ли unordered_map / set порядок обхода как порядок вставки?

Question

Я написал некоторый код, подобный этому:

unordered_map<int, int> uii;
uii.insert(make_pair(12,4));
uii.insert(make_pair(3,2));
uii.insert(make_pair(6,1));
uii.insert(make_pair(16,9));
....

Когда я использую цикл for, чтобы посетить эту карту, он печатает ключ в правильном порядке моей вставки.Я протестировал unordered_set с тем же результатом.

Так что мой вопрос в том, гарантирует ли стандарт C ++ порядок посещения как порядок вставки, как в Java LinkedHashMap?

Answer 1

Нет, это unordered, такой гарантии нет.

Элементы в неупорядоченном ассоциативном контейнере организованы в сегменты, ключи с таким же хешем будут в концетакое же ведро .Количество сегментов увеличивается, когда размер контейнера увеличивается, чтобы среднее количество элементов в каждом сегменте не превышало определенного значения.

Перефразировка делает недействительным итератор и может привести к перестановке элементов в разных сегментах, но это не делает недействительными ссылки на элементы.

Это верно как для unordered_map, так и для unordered_set.

Возможно, вы также захотитеотметьте этот вопрос Сохраняйте порядок unordered_map, когда мы вставляем новый ключ

---

Но внутренне реализация неупорядоченного контейнера может использовать list или другой заказал контейнер для хранения элементов и хранения только ссылок на подсписки в его корзинах, в результате чего порядок итераций совпадал бы с порядком вставки до тех пор, пока не будет вставлено достаточно элементов, чтобы список переставил .Так обстоит дело с реализацией VS.