std::unordered_set 中的元素如何存储在 C++ 的内存中？
How are elements in an std::unordered_set stored in memory in C++?
在摆弄类型双关迭代器时，我偶然发现了这样做的能力
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 如何将其元素存储在内存中？当一个元素被添加到集合中时会发生什么？它在内存中的什么位置？如果它没有存储在元素一个接一个地排列的类似数组的容器中，又如何跟踪它？
std::unordered_set 存储其内存的方式是实现定义的。标准无所谓，只要满足要求即可。
在 VS 版本中，它将它们存储在 std::list 中（通过创建和管理附加数据提供快速访问） - 因此每个元素也有指向 prev 和 next 的指针通过 new 存储（至少我记得 std::list).
unordered_set 使用外部链接实现为散列 table。
这基本上意味着你有一个链表数组（通常称为 "buckets"）。因此，要将项目添加到 unordered_set，您首先要对要插入的新项目进行哈希处理。然后，您获取该散列并将其缩小到数组当前大小的范围（can/will 随着您添加更多项而扩展）。然后将新项目添加到该链表的尾部。
因此，根据散列产生的值，两个连续插入的项目可能（而且经常会）插入链表中 table 的完全不同部分。然后链表中的节点通常会被动态分配，因此即使是同一个链表中的两个连续项也可能位于完全不相关的地址。
然而，正如我在 an earlier answer 中指出的那样，标准中实际指定的内容比大多数人似乎意识到的要多得多。正如我在那里概述的那样，可能（几乎）可能违反预期并仍然（有点）满足标准中的要求，但即使充其量，这样做也非常困难。对于大多数实际用途，您可以假设它有点像链表向量。
大多数相同的事情适用于 unordered_multiset-- 唯一的根本区别是您可以拥有多个具有相同键的项目，而不是只有一个具有特定键的项目。
同样，还有unordered_map和unordered_multimap，它们又很相似，除了它们将存储的东西分成一个键和一个与该键相关联的值，并且当它们做散列，只看key部分，不看value部分）。
我不想直接回答问题，而是想解决 "type-punning" 技巧。 （我把它放在引号中是因为提供的代码没有演示类型双关。也许代码针对这个问题进行了适当的简化。无论如何，*vec.begin() 给出了 int，所以 &*vec.begin()是一个 int*。进一步转换为 void* 然后返回 int* 是一个净空操作。）
您的代码利用的属性是
*(begin_i + 1) == *(vec.begin() + 1) // Using the initial value of begin_i
*(&*vec.begin() + 1) == *(vec.begin() + 1) // Without using an intermediary
这是 contiguous iterator, which is associated with a contiguous container 的 属性。这些是将其元素存储在相邻内存位置的容器。标准库中的连续容器是string、array和vector；这些是唯一可以保证您的技巧有效的标准容器。在 deque 上尝试一开始可能会奏效，但如果向 &*begin() 添加足够多的内容，尝试就会失败。其他容器倾向于单独动态分配元素，因此元素地址之间不需要有任何关系；元素通过指针而不是 position/index.
链接在一起
这样我就不会忽略提出的问题：
无序集只需要将元素组织到桶中。除了要求具有相同散列值的所有元素都放在同一个桶中之外，没有关于如何完成的要求。 （这 并不 暗示同一个桶中的所有元素都具有相同的哈希值。）实际上，每个桶可能被实现为一个 list，并且桶的容器可能是 vector，只是因为重用代码很酷。同时，这是一个实现细节，所以它可以从编译器到编译器，甚至从编译器版本到编译器版本。没有任何保证。
在摆弄类型双关迭代器时，我偶然发现了这样做的能力
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 如何将其元素存储在内存中？当一个元素被添加到集合中时会发生什么？它在内存中的什么位置？如果它没有存储在元素一个接一个地排列的类似数组的容器中，又如何跟踪它？
std::unordered_set 存储其内存的方式是实现定义的。标准无所谓，只要满足要求即可。
在 VS 版本中，它将它们存储在 std::list 中（通过创建和管理附加数据提供快速访问） - 因此每个元素也有指向 prev 和 next 的指针通过 new 存储（至少我记得 std::list).
unordered_set 使用外部链接实现为散列 table。
这基本上意味着你有一个链表数组（通常称为 "buckets"）。因此，要将项目添加到 unordered_set，您首先要对要插入的新项目进行哈希处理。然后，您获取该散列并将其缩小到数组当前大小的范围（can/will 随着您添加更多项而扩展）。然后将新项目添加到该链表的尾部。
因此，根据散列产生的值，两个连续插入的项目可能（而且经常会）插入链表中 table 的完全不同部分。然后链表中的节点通常会被动态分配，因此即使是同一个链表中的两个连续项也可能位于完全不相关的地址。
然而，正如我在 an earlier answer 中指出的那样，标准中实际指定的内容比大多数人似乎意识到的要多得多。正如我在那里概述的那样，可能（几乎）可能违反预期并仍然（有点）满足标准中的要求，但即使充其量，这样做也非常困难。对于大多数实际用途，您可以假设它有点像链表向量。
大多数相同的事情适用于 unordered_multiset-- 唯一的根本区别是您可以拥有多个具有相同键的项目，而不是只有一个具有特定键的项目。
同样，还有unordered_map和unordered_multimap，它们又很相似，除了它们将存储的东西分成一个键和一个与该键相关联的值，并且当它们做散列，只看key部分，不看value部分）。
我不想直接回答问题，而是想解决 "type-punning" 技巧。 （我把它放在引号中是因为提供的代码没有演示类型双关。也许代码针对这个问题进行了适当的简化。无论如何，*vec.begin() 给出了 int，所以 &*vec.begin()是一个 int*。进一步转换为 void* 然后返回 int* 是一个净空操作。）
您的代码利用的属性是
*(begin_i + 1) == *(vec.begin() + 1) // Using the initial value of begin_i
*(&*vec.begin() + 1) == *(vec.begin() + 1) // Without using an intermediary
这是 contiguous iterator, which is associated with a contiguous container 的 属性。这些是将其元素存储在相邻内存位置的容器。标准库中的连续容器是string、array和vector；这些是唯一可以保证您的技巧有效的标准容器。在 deque 上尝试一开始可能会奏效，但如果向 &*begin() 添加足够多的内容，尝试就会失败。其他容器倾向于单独动态分配元素，因此元素地址之间不需要有任何关系；元素通过指针而不是 position/index.
这样我就不会忽略提出的问题：
无序集只需要将元素组织到桶中。除了要求具有相同散列值的所有元素都放在同一个桶中之外，没有关于如何完成的要求。 （这 并不 暗示同一个桶中的所有元素都具有相同的哈希值。）实际上，每个桶可能被实现为一个 list，并且桶的容器可能是 vector，只是因为重用代码很酷。同时，这是一个实现细节，所以它可以从编译器到编译器，甚至从编译器版本到编译器版本。没有任何保证。