std::set和std::unordered_set如何使用emplace()就地构造元素？

Question

两种容器的文档都说明emplace()函数可以原地构造元素。但在元素构造之前，它们如何知道新元素的位置呢？

例如，unordered_set按照哈希值放置元素。在元素被构造之前，它如何知道该元素的哈希值呢？

我想也许emplace函数的目的是要接受右值参数，计算新元素的位置并移动对象。但是，insert()也能做同样的事情。

- Sweeney Todd

Answer 1

规范中未明确说明其工作原理，但通常情况下，将从参数构建数据结构内部节点对象（rb-tree节点或包含值的哈希桶节点），然后将该节点链接到数据结构中（对于set是链接到rb-tree中，对于unordered_set是链接到哈希桶中）。如果该值已经存在（即未添加），则会销毁该节点对象。

- Chris Dodd

---

那么数据结构基本上是保留指向对象的指针，而不像std::vector一样持有对象，这是正确的吗？如果是这种情况，我还有另一个问题：在树重新平衡/重新散列的情况下，我知道迭代器被使无效了，但实际元素的指针呢？它们是否仍然有效？ - Sweeney Todd

@SweeneyTodd 如果你有另一个问题，请将其作为另一个问题提出 - 或者在这种情况下只需阅读 https://dev59.com/OGw15IYBdhLWcg3wuuGn（是的，它们确实可以）。 - Lightness Races in Orbit

数据结构（用于集合的二叉树，用于无序集合的开放式哈希表）涉及大量指向内部节点对象的指针。请阅读相关资料以了解更多信息——红黑树，带分离链接的开放式哈希表。不要被“开放地址法”意味着“闭散列”的事实所困惑。 - Chris Dodd

@SweeneyTodd：“在树的重新平衡/重新散列的情况下，我知道迭代器会失效”--这是错误的；根据规范（23.2.4.1.9）：“插入和emplace成员不应影响容器的迭代器和引用的有效性，而erase成员只应使被删除元素的迭代器和引用无效。” - Chris Dodd

@ChrisDodd 我认为这是针对 std::set 的。对于 unordered_set，在此处声明 "如果由于插入而发生重新哈希，则所有迭代器都将无效。"：(https://en.cppreference.com/w/cpp/container/unordered_set/insert) - Sweeney Todd