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如何将其元素存储在内存中？将元素添加到集合中会发生什么？它在内存中的位置如何，以及如何跟踪它是否未存储在类似数组的容器中，在该容器中元素是一个接一个的？

虽然搞乱类型迭代器，但我遇到了执行std :: vector vec {3，7，1，8，4};的能力。 int * begin_i =（int *）（void *）＆* vec.begin（）; std :: cout <

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

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

因此，取决于散列产生的值，可以（并且经常会）将两个连续插入的项目插入到表的完全不同部分的链接列表中。然后，通常会动态分配链表中的节点，因此即使同一链表中的两个连续项也可能位于完全不相关的地址。

但是，正如我在an earlier answer中指出的那样，标准中实际上对此进行了很多规定，比大多数人似乎意识到的要多。正如我在此处概述的那样，可能（几乎）可能违反预期，但仍然（某种程度上）符合标准中的要求，但是即使充其量也很难做到。出于大多数实际目的，您可以假设它有点像链表的向量。

unordered_multiset大部分相同—唯一的根本区别是您可以具有多个具有相同键的项，而不是只有一个具有特定键的项。

[同样，还有unordered_map和unordered_multimap，它们再次非常相似，除了它们将存储在密钥中的内容和与该密钥相关联的值分开，并且当它们进行哈希处理时，只看关键部分，而不是价值部分）。

而不是直接回答问题，我想谈谈“类型欺骗”的把戏。 （之所以用引号引起来，是因为所提供的代码未演示类型转换。也许针对该问题对代码进行了适当的简化。无论如何，*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的属性，与contiguous container关联。这些是将其元素存储在相邻存储位置中的容器。标准库中的连续容器是string，array和vector；这些是保证您的把戏起作用的唯一标准容器。首先尝试在deque上进行尝试，但是如果在&*begin()中添加了足够的内容，则尝试将失败。其他容器往往会动态地单独分配元素，因此元素的地址之间不必存在任何关系。元素通过指针而不是位置/索引链接在一起。

---

这样我就不会忽略所问的问题：

无序集合只需要将元素组织到存储桶中即可。除了要求将具有相同哈希值的所有元素都放在同一存储桶中之外，没有其他要求。 （这确实表明[[not

暗示同一存储桶中的所有元素都具有相同的哈希值。）实际上，每个存储桶都可能实现为list，而存储桶的容器可能是vector因为重用代码很酷。同时，这是一个实现细节，因此从编译器到编译器，甚至从编译器版本到编译器版本都可以使用。没有任何保证。

std::unordered_set存储其内存的方式已定义为实现。只要满足要求，斯坦达特就不会在乎。

在VS版本中，它们将它们存储在std::list中（通过创建和管理其他数据提供快速访问）-因此每个元素还具有指向上一个的指针，而下一个则通过new存储（至少我记得这一点） std::list）。

Answer 1

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

Answer 2

而不是直接回答问题，我想谈谈“类型欺骗”的把戏。 （之所以用引号引起来，是因为所提供的代码未演示类型转换。也许针对该问题对代码进行了适当的简化。无论如何，*vec.begin()给出了int，因此&*vec.begin()是int*。进一步强制转换为void*然后又转换为int*是净无操作。）

Answer 3

std::unordered_set存储其内存的方式已定义为实现。只要满足要求，斯坦达特就不会在乎。