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

Question

如果我在两个无序容器中插入相同的(大小和值)元素,那么使用两个迭代器遍历容器总会在同一位置给出相同的元素吗？

如果是的话,可以使用(单个!)散列函数来打破这个决定论吗？

Answer 1

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

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

但是，如果您更改插入顺序，那么所有的赌注都会被取消，因为内部重新分配将更改元素的顺序：

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

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