c++ - C++：关于“有效指针和引用”的说明

Question

我很难理解这种对 stl 无序地图实现的描述：

C++ 的标准模板库 (STL) 通过 std::unordered_map 和 std::unordered_set 提供哈希表。该标准保证了引用的稳定性：哈希表中键和值的引用和指针必须保持有效，直到相应的键被删除。实际上，这意味着条目必须是间接的且单独分配的，这会增加大量 CPU 开销。

两个问题：

1. 当作者说“对键和值的引用和指针......必须保持有效”时，这是否意味着在我插入一个项目后，指针和引用必须在整个程序中存在？当我使用“new”在堆上分配对象并且指向它的指针超出范围并且不再有效时。鉴于哈希表引用了堆上的对象，我不确定为什么引用/指针需要保持有效。

2. “间接和单独分配”条目如何“增加大量 CPU 开销”？

标签： c++memorystlunordered-mapunordered-set

Answer 1

当作者说“对键和值的引用和指针......必须保持有效”时，这是否意味着在我插入一个项目后，指针和引用必须在整个程序中存在？

不。这意味着如果您获取映射中对象的地址，或将引用绑定到此类对象，则该指针或该引用不得因为添加或删除映射中不相关的元素而变得悬空。这是实施的要求std::unordered_map。

这与 eg 的std::vector行为方式不同。向向量添加元素可能会导致它重新分配，并且所有先前获得的指针和对元素的引用都处于悬空状态。

当我使用new在堆上分配对象并且指向它的指针超出范围并且不再有效时。

不，指针不复存在，具有相同值的其他指针仍然指向您new编辑的对象。

“间接和单独分配”条目如何“增加大量 CPU 开销”？

现代 CPU 在访问内存中相邻的东西方面要快得多。例如，他们在被要求之前开始加载稍后的元素。如果目标地址不遵循简单的模式，这种预测就更难了。

您链接的文章强调了标准委员会做出的std::unordered_map不适合作者目的的设计选择。他们编写了一对与 具有相同公共成员（具有相同含义）的类std::unordered_map，作为“插入式”替代品。