使用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"的地址将保持不变？

我从这个链接中注意到字符串"papaya"保持不变(并且优雅地工作).但我想确定一下指针.

Answer 1

YES 的参考你在你的帖子已经引用明确指出,没有单元复制或移动.(这假设node在您的代码段中没有引用map::node_type).

这适用于map-node的insert操作(在修改其键之后):

如果插入成功,则在节点句柄中保存的元素的指针和引用无效,并且在提取该元素之前获得的指针和引用变为有效.(自C++ 17起)

然而,在extract()离子和insert()离子之间访问对象具有未定义的行为,并且在提取状态下获取其地址的用途有限.引用标准:

提取成员仅使删除元素的迭代器无效; 指针和对已删除元素的引用仍然有效.但是,当元素由node_type拥有时,通过这样的指针和引用访问元素是未定义的行为.如果元素成功插入,则在node_type拥有的元素的引用和指针无效.

说明

本质上,a map<>实现为节点树,每个节点都包含a key和T(pair<const Key, T>对用户公开).节点(通常)分配在堆上,对象的地址与节点的地址相关.map::extract()从其树中取消链接节点并返回节点句柄(包含指向地图节点的指针的对象),但AFAIK不重新分配,移动或复制节点本身.之后map::insert(handle),根据其(新)密钥将节点重新链接到树中.同样,这不涉及节点的重新分配,移动或复制.

备注

以上是草图.如何实际完成工作可能更复杂,也可以定义实现.作为解释这里一个node_handle也允许通过改变成员函数的关键

Key &node_handle::key() const;

如何在引擎盖下完成此操作并未指定,我推测实现使用union或某些强制转换来允许此操作.当然,地图必须呈现给用户a pair<const Key,T>以防止他们更改密钥并因此破坏地图,但是这对于从地图中提取的元素不是任何问题.