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 循环访问此 map 时，它会按照我插入的正确顺序打印 key。我测试了 unordered_set，结果相同。

所以我的问题是，C++ 标准是否像 Java 的 LinkedHashMap 一样保证访问顺序为插入顺序？

Answer 1

不，它是无序，没有这样的保证。

Elements in an unordered associative container are organized into buckets, keys with the same hash will end up in the same bucket. The number of buckets is increased when the size of the container increases to keep the average number of elements in each bucket under a certain value.

Rehashing invalidates iterator and might cause the elements to be re-arranged in different buckets but it doesn't invalidate references to the elements.

这对 unordered_map 和 unordered_set 都有效。

您可能还想检查这个问题 Keep the order of unordered_map as we insert a new key

---

但是，在内部，无序 容器的实现可能会使用 list 或其他有序 容器来存储元素并仅存储对其子列表的引用桶，这将使迭代顺序与插入顺序一致，直到插入足够多的元素导致列表重新排列。 VS 实现就是这种情况。