用地图提取和重新插入的限制性规则的原理 [英] Rationale of restrictive rules for extract and re-insert with map

问题描述

自C ++ 17起，关联容器支持提取节点及其节点重新插入（可能插入相同类型的另一个容器中）。 extract（key）返回的对象是 node_handle ，仅可移动，并且对于地图容器具有成员函数

Since C++17, associative containers support the extraction of a node and its re-insertion (possibly into another container of the same type). The object returned by extract(key) is a node_handle, which is move-only and for map containers has member functions

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

不仅可以更改映射类型，还可以更改键。这可用于更改键，而无需重新分配（示例取自 map :: extract（） ）的文档：

which allow to alter not only the mapped type, but also the key. This can be used to change the key without re-allocation (example taken from the documentation for 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 :: extract（）取消链接树中的节点，并通过节点句柄返回指向该树的指针，接管该树所有权。在 map :: insert（）之后，该节点重新链接到树中，所有权再次由地图接管。

As far as I understand, map is implemented as binary-search tree, while map::extract() un-links a node from the tree and returns a pointer to it via the node-handle, which takes over the ownership. Upon map::insert(), the node is re-linked into the tree and ownership is taken over by the map again.

因此，未重新分配，移动节点（以及存储的密钥和 mapped_type ） ，或在此过程中复制。 标准说（我的照明很高）：

Thus, the node (and the stored key and mapped_type) are not re-allocated, moved, or copied in the process. The standard says (my high lighting):

提取成员仅使迭代器对已删除元素无效；
指针和对已删除元素的引用仍然有效。但是，当
元素由node_­type拥有而
通过此类指针和引用访问该元素时，则是未定义行为。如果成功插入元素，则对由node_type拥有的元素获得的引用和
指针将是
无效。

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.

我的问题 ：( 1）使UB通过其地址访问提取的元素，以及（2）在插入所取地址时使之无效的背后原理是什么？在提取状态下？

My question: what is the rationale behind (1) making it UB to access an extracted element by its address and (2) invalidating upon insertion the address taken in the extracted state?

恕我直言，这种提取和插入惯用法可以始终保持元素地址有效（直到销毁，如果从未重新插入元素，则可能会在销毁地图之前发生）。以下代码

IMHO, this extract-and-insert idiom can be implemented in a way that keeps the address of the element valid at all times (until destruction, which may occur before map-destruction if the element is never re-inserted). The following code

#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 ）并给出输出

compiles (with gcc 8.2.0 using -std=c++17) and gives output

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

如预期的那样（对于 std :: string 代替 immovable_string 和/或 unordered_map 而不是 map ）。

as expected (the same results are obtained for std::string in place of immovable_string and/or unordered_map instead of map).

编辑

请注意，我不是在询问有关与修改 key （地图存储 pair< const Key，T> ）。

Note that I'm not asking about issues related to modifying the key (map stores pair<const Key,T>).

我的问题仅是关于通过指针或引用访问映射元素的限制。如果不移动/复制元素，即如果其地址始终保持有效（实际上是由标准指定的），则提取并插入惯用语的整个思想仅使有意义。在处于提取状态UB时呈现对元素的访问似乎很奇怪，并且使提取和插入机制的作用不大：考虑多线程代码，其中一个线程访问元素，而另一个线程提取并重新执行-插入它。这可以在没有任何问题的情况下实现，但可能会引起UB-为什么？

My question is solely about restrictions for access to the mapped element via pointers or references. The whole idea of the extract-and-insert idiom makes only sense if the element is not moved/copied, i.e. if its address remains valid at all times (which in fact is specified by the standard). Rendering access to the element whilst in the extracted state UB seems strange and renders the extract-and-insert mechanism less useful: think about multi-threaded code with one thread accessing an element whilst another extracts and re-inserts it. This can be implemented w/o any issue yet may invoke UB -- WHY?

这里是UB方案（IMHO非常合适，无需UB）：

Here is a UB scenario (which IMHO is perfectly fine, no UB required):

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（） 失败，句柄被销毁并且地址无效。显而易见，但是用户可以做些事情。

Of course, if the insert() fails, the handle is destroyed and the address invalidated. That's obvious, but the user can to something about that.

推荐答案

我认为提取系统的主要细微之处在于 map< K，T> 的 value_type 是 pair< const K，T> —注意 const ！

I think the predominant subtlety in the "extraction" system is that the value_type of a map<K, T> is pair<const K, T> — note the const!

修改const对象会导致未定义的行为，因此您必须非常小心，不要修改已知是const的东西。虽然节点是任何映射的一部分，但键是const。提取机制的魔力（以及花这么长时间指定的原因）是在提取节点时 ，关键是 not const。

Modifying a const object causes undefined behaviour, so you need to be very careful not to modify something that's known to be const. While the node is part of any map, the key is const. The "magic" of the extraction machinery (and the reason it took so long to specify) is that while the node is extracted, the key is not const.

这基本上要求您认真研究问题，并说服自己 pair< const K，T> 被解释为 pair< K，T> （请记住， pair 是允许用户使用的模板专攻！）。因此，为避免可能会损坏const对象，必须对任何节点的插入状态和提取状态进行清晰的排序。

This basically requires you to look at the problem really hard and convince yourself that a pair<const K, T> can sometimes be interpreted as a pair<K, T> (and bear in mind that pair is a template that users are permitted to specialize!). So to avoid any potential for const objects being modified, there must be a clear sequencing of inserted and extracted states for any node.

有专门的标准措辞可以帮助您进行专业化问题在[container.node.overview] p4中：

There is standard wording to help with the specialization issue in [container.node.overview]p4:

如果用户定义的专业化对 pair< const Key，T> 或 pair< Key，T> 存在c $ c> c $ c> Key 是
容器的 key_type ，而 T 是容器的 mapped_type ，涉及节点句柄的操作行为是不确定的。

If a user-defined specialization of pair exists for pair<const Key, T> or pair<Key, T>, where Key is the container’s key_type and T is the container’s mapped_type, the behavior of operations involving node handles is undefined.

这篇关于用地图提取和重新插入的限制性规则的原理的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！