使用地图提取和重新插入的限制性规则的基本原理

从 C++17 开始，关联容器 https://en.cppreference.com/w/cpp/container支持节点的提取及其重新插入（可能插入到相同类型的另一个容器中）。返回的对象extract(key) is a 节点句柄 https://en.cppreference.com/w/cpp/container/node_handle，它是仅移动的并且对于地图容器来说具有成员函数

key_type &key() const;
mapped_type &mapped() const;

它不仅允许改变映射类型，还允许改变键。这可用于更改密钥无需重新分配（示例取自的文档map::extract() https://en.cppreference.com/w/cpp/container/map/extract):

std::map<int, std::string> map{{1,"mango"}, {2,"papaya"}, {3,"guava"}};
auto handle = map.extract(2);
handle.key() = 4;
map.insert(move(handle));

据我所理解，map被实现为二叉搜索树，而map::extract()取消节点与树的链接，并通过节点句柄返回指向该节点的指针，该句柄接管所有权。之上map::insert()，该节点重新链接到树中，并且所有权再次由映射接管。

因此，节点（以及存储的key and mapped_type）在此过程中不会重新分配、移动或复制。这标准说 http://eel.is/c++draft/associative.reqmts#10（我的高光）：

extract 成员仅使已删除元素的迭代器无效； 指向已删除元素的指针和引用仍然有效。然而， 通过此类指针和引用访问元素，而 元素由 node_type 拥有未定义的行为。参考文献和 指向由 node_type 拥有的元素的指针是无效的如果元素插入成功。

我的问题：(1) 使 UB 通过其地址访问提取的元素以及 (2) 在插入时使在提取状态中获取的地址无效，背后的基本原理是什么？

恕我直言，这种提取和插入惯用法可以通过一种始终保持元素地址有效的方式来实现（直到销毁，如果元素从未重新插入，则可能会在映射销毁之前发生）。下面的代码

#include <map>
#include <string>
#include <iostream>

struct immovable_string : std::string
{
    immovable_string(const char*s) : std::string(s) {}
    immovable_string() = default;
    immovable_string(immovable_string const&) = delete;
    immovable_string(immovable_string &&) = delete;
    immovable_string&operator=(immovable_string const&) = delete;
    immovable_string&operator=(immovable_string &&) = delete;
};

int main()
{
    std::map<int,immovable_string> map;

    map.emplace(1,"mango");
    map.emplace(2,"papaya");
    map.emplace(3,"guava");

    std::cout << "initially:     "
              << " address=" << std::addressof(map[2])
              << " value=" << map[2] <<'\n';

    auto handle = map.extract(2);

    std::cout << "after extract: "
              << " address=" << std::addressof(handle.mapped())
              << " value=" << handle.mapped() <<'\n';

    handle.key() = 4;
    map.insert(move(handle));

    std::cout << "after insert:  "
              << " address=" << std::addressof(map[4])
              << " value=" << map[4] <<'\n';
}

编译（使用 gcc 8.2.0-std=c++17）并给出输出

initially:      address=0x7f9e06c02738 value=papaya
after extract:  address=0x7f9e06c02738 value=papaya
after insert:   address=0x7f9e06c02738 value=papaya

正如预期的那样（获得了相同的结果std::string代替immovable_string and/or unordered_map代替map).

Edit

请注意，我是不问关于修改相关问题key (map stores pair<const Key,T>).

我的问题只是关于通过指针或引用访问映射元素的限制。提取和插入习惯用法的整个思想使得only检测元素是否未被移动/复制，即其地址是否始终保持有效（实际上是由标准指定的）。在提取状态 UB 下渲染对元素的访问似乎很奇怪并且使得提取和插入机制不再那么有用：考虑一下多线程代码，一个线程访问一个元素，而另一个线程提取并重新插入它。这可以在没有任何问题的情况下实现，但可能会调用 UB --WHY?

这是一个 UB 场景（恕我直言，完全没问题，不需要 UB）：

void somefunc(object*ptr) { ptr->do_something(); }
void re_key(map<int,object> &M, int oldKey, int newKey)
{
    if(M.find(0)!=M.end() && M.find(newKey)==M.end()) {
        auto handle = M.extract(0);
        handle.key() = newKey;
        M.insert(std::move(handle));
    }
}

map<int,object> M = fillMap();
auto ptr = addressof(M[0]);     // takes initial address
thread t1(somefunc,ptr);        // uses said address to access object
thread t2(re_key,M,7);          // extracts and inserts an object 

当然，如果insert()失败，则handle被破坏，地址失效。这是显而易见的，但用户可以对此做一些事情。

我认为“提取”系统的主要微妙之处在于value_type of a map<K, T> is pair<const K, T>— 注意const!

修改 const 对象会导致未定义的行为，因此您需要非常小心，不要修改已知为 const 的内容。虽然节点是任何映射的一部分，但键是常量。提取机械的“魔力”（以及花了这么长时间来指定的原因）在于当节点被提取时，关键是not const.

这基本上要求你认真地看待问题并说服自己pair<const K, T>有时可以解释为pair<K, T>（并记住pair是一个允许用户专门化的模板！）。因此，为了避免 const 对象被修改的任何可能性，任何节点的插入和提取状态都必须有明确的顺序。

[container.node.overview]p4 中有标准措辞可以帮助解决专业化问题：

如果用户定义的专业化pair存在于pair<const Key, T> or pair<Key, T>, where Key是个 容器的key_type and T是容器的mapped_type，涉及节点句柄的操作的行为是未定义的。