使用 std::map::extract 修改密钥

Question

我的实现使用 std::map 来存储数据。当我开始我的代码时，它似乎是最好的选择。现在我不得不更改地图内所有对象的键值。

问题是每个对象都指向地图内的另一个对象：

class AND : public node{
    vector <node*> inputs;
    vector <node*> outputs;
}

地图声明如下：

map<unsigned int, AND> all_ANDs;

我的问题是： 如果我使用 C++17 中的 map::extract 来修改 all_ANDs 映射中的键值，我的指针（例如属性输入中的那些）一直指向正确的地方？

换句话说：如果我用extract改变"first"元素的值，"second"的地址会保持不变吗？

我从 this link 注意到字符串 "papaya" 保持不变（并且工作正常）。但我想确定指针。

Answer 1

是您已经在帖子中引用的 reference 明确指出 没有任何元素被复制或移动 。（这假设您的代码片段中的 node 不引用 map::node_type）。

map-node的insert操作也是如此（修改key后）：

If the insertion is successful, pointers and references to the element obtained while it is held in the node handle are invalidated, and pointers and references obtained to that element before it was extracted become valid. (since C++17)

但是，访问 extract()ion 和 re-insert()ion 之间的对象具有未定义的行为，并且在提取状态下获取的地址用途有限。引用自标准：

The extract members invalidate only iterators to the removed element; pointers and references to the removed element remain valid. However, accessing the element through such pointers and references while the element is owned by a node_type is undefined behavior. References and pointers to an element obtained while it is owned by a node_type are invalidated if the element is successfully inserted.

说明

本质上，map<> 被实现为一个节点树，每个节点包含一个 key 和 T（向用户公开为 pair<const Key, T>）。节点（通常）分配在堆上，对象的地址与节点的地址相关。 map::extract() 取消节点与其树的链接和 returns 一个 节点句柄 （一个对象持有指向地图节点的指针），但 AFAIK 节点本身是不会重新分配、移动或复制。在 map::insert(handle) 后，节点根据其（新）键重新链接到树中。同样，这不涉及节点的重新分配、移动或复制。

备注

以上是草图。事情的实际完成方式可能更复杂，并且实现也已定义。正如所解释的 here node_handle 确实允许通过成员函数
更改密钥
Key &node_handle::key() const;

未指定这是如何在引擎盖下完成的，我推测该实现使用联合或某些强制转换来允许这样做。当然，地图必须向用户呈现 pair<const Key,T> 以防止他们更改密钥并因此破坏地图，但这对于从地图中提取的元素没有任何关系。

Answer 2

您的 map 包含实际的 AND 对象，而不是指向对象的指针。因此，如果存储在 vector 中的 AND* 指针指向 map 的 AND 对象，那么一旦这些对象是 已从 map.

中删除

然而，提取只是从map中取消指定节点的链接，该节点及其键和值在内存中仍然有效。可以将节点重新插入到 map 中，而不会影响节点的键和值的地址。在这方面，vectors 中的指针将不会变为无效（尽管在节点与容器分离时取消引用它们是未定义的）。

另一种选择是将 map 更改为保存 AND* 指针。或者更好的是，考虑在 map 中使用 std::shared_ptr<AND> 并在 vector 中使用 std::shared_ptr<node>，而不是原始指针。那么 map 条目是擦除还是提取都无关紧要，AND 对象将保持有效，因为只要有对它们的有效 shared_ptr 引用。

Answer 3

我上面的回答解决了您的直接问题。但是，正如我在评论中所建议的那样，这似乎是 XY problem。我怀疑的是：

您有一些 AND 对象的结构，这些对象通过它们的 inputs 和 outputs 字段相互链接。这种联系不能被任何重新分配破坏，所以你不能将它们存储在不断增长的 vector<AND> 中并重新分配。
您还想根据一些 key 对这些对象进行排序，因此将它们存储在 map<Key,AND> 中，这确实在增长时不会重新分配。
您现在想根据另一个键对它们进行排序（and/or 更改所有键）。

（如果您实际上对排序不感兴趣，而只是想通过键查找对象，则应该使用 unordered_map 而不是 map，它支持 find()在 O(n) 而不是 O(log(n)) 操作中。）

我建议您使用不同的数据布局：

您存储 AND 对象的方式允许在不重新分配的情况下增加它们的数量。这里一个明显的选择是 deque<AND>，因为

insertion and deletion at either end of a deque never invalidates pointers or references to the rest of the elements

您还可以使 AND 不可复制和不可移动，确保一旦分配它们的地址永远不会改变（并且指向它们的指针在销毁之前保持有效）。
您可以通过实际处理指向存储对象的指针来支持任何按键查找或按键排序操作，方法是对 pair<key,AND*> 的向量进行排序或使用一个 map<key,AND*> 或 unordered_map<key,AND*>。您甚至可以同时为每个对象设置多个键（每个对象都有一个映射）。
当您必须重新输入所有对象时，只需忘记旧映射并制作一个新映射：因为映射只存储指针而不存储对象，所以这不会影响您的链接。

使用 std::map::extract 修改密钥

Using std::map::extract to modify key

c++

pointers

extract

stdmap