c++ - 在无序容器中插入的确定性

Question

如果我在两个无序容器中插入相同的（大小和值）元素，使用两个迭代器遍历容器是否总是在相同的位置给出相同的元素？

如果是，是否可以制作（单个！）散列函数来打破这种确定性？

Answer 1

这取决于：如果您将相同的元素以相同的顺序插入到两个不同的无序容器中，那么两个容器的顺序应该相同，即使顺序本身是未指定的。

推理有点复杂：所有操作hash(k)和重新分配都是确定性的。虽然标准中没有实际引用，但在 an 之后执行 a find()in的能力似乎排除了任何类型的随机或其他非确定性插入。O(1)insert()

然而，如果你改变插入的顺序，那么所有的赌注都会被取消，因为内部重新分配会改变元素的顺序：

23.2.5 无序关联容器 [unord.req]

9 无序关联容器的元素被组织成桶。具有相同哈希码的键出现在同一个桶中。随着元素被添加到无序关联容器中，桶的数量会自动增加，因此每个桶的平均元素数保持在一个界限以下。重新散列使迭代器无效，更改元素之间的顺序，并更改元素出现在哪些桶中，但不会使指针或对元素的引用无效。对于 unordered_multiset 和 unordered_multimap，重新散列保留了等效元素的相对顺序。