c++ - std::unordered_set 中的元素如何存储在 C++ 的内存中？

Question

在摆弄类型双关迭代器时，我发现了这样做的能力

std::vector<int> vec{ 3, 7, 1, 8, 4 };
int* begin_i = (int*)(void*)&*vec.begin();

std::cout << "1st: " << begin_i << " = " << *begin_i << std::endl;
begin_i++;
std::cout << "2nd: " << begin_i << " = " << *begin_i << std::endl;

然后我尝试用 std::unordered_set 做同样的事情:

std::unordered_set<int> set{ 3, 7, 1, 8, 4 };
for (auto& el : set)
{ // Display the order the set is currently in
    std::cout << el << ", ";
}
std::cout << '\n' <<std::endl;

int* begin_i = (int*)(void*)&*set.begin();

std::cout << "1st: " << begin_i << " = " << *begin_i << std::endl;
begin_i++;
std::cout << "2nd: " << begin_i << " = " << *begin_i << std::endl;

但我得到的输出是:

4, 8, 1, 7, 3,

1st: [address] = 4
2nd: [address] = 0

我假设这是因为无序集的元素位于内存的不同部分？考虑到我还使用基于范围的循环打印了元素的存储顺序，我在这里感到很困惑。

我的问题是 std::unordered_set 如何将其元素存储在内存中？当一个元素被添加到集合中时会发生什么？它在内存中的什么位置？如果它没有存储在元素一个接一个地排列的类似数组的容器中，又如何跟踪它？

Answer 1

unordered_set 使用外部链接作为哈希表实现。

这基本上意味着您有一个链表数组(通常称为“桶”)。因此，要将项目添加到 unordered_set，您首先要对要插入的新项目进行哈希处理。然后，您获取该散列并将其减少到数组当前大小的范围(随着您添加更多项目，它可以/将扩展)。然后，您将新项目添加到该链表的尾部。

因此，根据散列产生的值，两个连续插入的项可能(而且经常会)插入到表中完全不同部分的链表中。那么链表中的节点通常会被动态分配，因此即使是同一链表中的两个连续项也可能位于完全不相关的地址。

正如我在 an earlier answer 中指出的那样然而，标准中实际上对此进行了详细说明，这比大多数人似乎意识到的要多得多。正如我在那里概述的那样，可能(几乎)可能违反预期并仍然(有点)满足标准中的要求，但即使充其量，这样做也非常困难。对于大多数实际用途，您可以假设它有点像链表 vector 。

大多数相同的事情适用于 unordered_multiset——唯一的根本区别是您可以拥有多个具有相同键的项目，而不是只有一个具有特定键的项目。

同样，还有 unordered_map 和 unordered_multimap，它们又很相似，除了它们将存储的东西分成一个键和一个与该键关联的值，当他们做散列时，只看关键部分，而不是值(value)部分)。