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

Anunordered_set是使用外部链接实现为哈希表的。

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

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

然而，正如我在之前的回答中指出的那样，标准中实际指定的内容比大多数人似乎意识到的要多得多。正如我在那里概述的那样，可能（几乎）不可能违反预期，但仍然（在某种程度上）满足标准中的要求，但即使在最好的情况下，这样做也会非常困难。对于大多数实际目的，您可以假设它有点像链表向量。

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

同样，还有unordered_map和unordered_multimap，它们又非常相似，只不过它们将存储的内容分开为键和与该键关联的值，并且当它们进行散列时，只查看键部分，而不查看值部分）。