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

Question

从C++ 17开始,关联容器支持节点的提取及其重新插入(可能进入另一个相同类型的容器).返回的对象extract(key)是node_handle,它是仅移动的,而映射容器具有成员函数

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

它不仅可以改变映射类型,还可以改变密钥.这可用于更改密钥而无需重新分配(例如,从文档中获取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()从树中取消链接节点,并通过node-handle返回指向它的指针,后者接管所有权.之后map::insert(),节点重新链接到树中,并且所有权将再次由地图接管.

因此,在该过程中不重新分配,移动或复制节点(以及存储的key和mapped_type).该标准说(我的高光):

提取成员仅使删除元素的迭代器无效; 指针和对已删除元素的引用仍然有效.但是,当元素由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和/或unordered_map代替获得相同的结果map).

---

编辑

请注意,我不是在询问与修改key(map商店pair<const Key,T>)相关的问题.

我的问题仅仅是通过指针或引用访问映射元素的限制.如果元素没有被移动/复制,即它的地址始终有效(实际上是由标准指定),那么提取和插入习语的整个想法才有意义.在提取状态下呈现对元素的访问UB似乎很奇怪并且使得提取和插入机制不那么有用:考虑多线程代码,其中一个线程访问元素,而另一个线程提取并重新插入它.这可以在没有任何问题的情况下实施,但可以调用UB - 为什么？

这是一个UB场景(IMHO非常好,不需要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则销毁并且地址无效.这很明显,但用户可以对此有所了解.

Answer 1

我认为,在"提取"系统的主要微妙的是,value_type的map<K, T>是pair<const K, T>-注意const!

修改const对象会导致未定义的行为,因此您需要非常小心,不要修改已知为const的内容.虽然节点是任何映射的一部分,但键是const.提取机制的"神奇"(以及它指定这么长时间的原因)是在提取节点时,键不是常量.

这基本上要求你真正努力地看待问题,并使自己相信a pair<const K, T>有时可以解释为a pair<K, T>(并记住这pair是一个允许用户专门化的模板!).因此,为了避免修改const对象的任何可能性,必须对任何节点的插入和提取状态进行明确排序.

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

如果一个用户定义的专业化pair存在pair<const Key, T>或pair<Key, T>,其中Key是容器的key_type和T是容器的mapped_type,涉及节点处理操作的行为是不确定的.

Answer 2

我只是在跟进 Kerrek SB 的回答，希望能更详细地解释这个问题（因此更有说服力）。所采用的有问题（P0083R3）纸的修订3提及std::pair<const Key, Mapped>VSstd::pair<Key, Mapped>难题，且“这些之间的转化可以安全地使用类似于由所使用的技术来实现std::launder对提取和重新插入。”

IOW、提取和重新插入通过调用“实现‘魔术’”（这是论文中的明确措辞）来解决容器代码本身中任何可能的别名问题，并且只要用户代码遵守，就可以避免与类型双关相关的优化你提到的限制。

这就提出了一个问题，即为什么不能将这种“魔法”扩展到涵盖用户代码Mapped通过在节点仍属于容器时获得的指针访问分离节点元素的情况。这样做的原因是，实现这种“魔法”的范围远大于实现仅适用于节点提取和插入的有限魔法的范围。

例如，简单地考虑这个函数：

int f(std::pair<const int, int> &a, const std::pair<int, int> &b)
{
    a.second = 5;
    return b.second;
}

根据对类型别名的限制，允许实现假设a并且b不能驻留在相同的内存位置。因此，实现也允许假设a.second和b.second不驻留在相同的内存位置，即使它们具有相同的类型。因此，实现有权一些非常基本的代码生成自由，如执行的负载b.second店前a.second，而无需实际的比较的地址a和b第一。

现在假设地图拼接的限制不是你说的。然后，可以执行以下操作：

int g()
{
    std::map<int, int> m{{1, 1}};
    auto &r = m[1];
    auto node = m.extract(1);
    return f(r, node.value());
}

由于类型双关限制，显然这是 UB。现在，等等，我知道你想抗议，因为：

1. 在node_type一个std::map没有value()方法。
2. 即使是这样，它也node_type应该是std::launder（或大致等效的）值。

然而，这些要点并没有提供实际的补救措施。就第一点而言，请考虑这个小变化：

int f(std::pair<const int, int> &a, const int &b)
{
    a.second = 5;
    return b;
}

int g()
{
    std::map<int, int> m{{1, 1}};
    auto &r = m[1];
    auto node = m.extract(1);
    return f(r, node.mapped());
}

现在，窥视孔优化f并没有给编译器足够的信息来排除混叠。然而，让我们假设编译器能够内联两个node.mapped()（因此，编译器可以建立，它返回一个参考second的std::pair<int, int>），和f。突然之间，编译器可能会再次感到有权进行危险的优化。

但是洗钱呢？首先，这在这里并不适用，因为有关的信息extract和在其中进行的洗钱可能位于与 完全不同的翻译单元中node_type::mapped()。这里需要强调的是：在规范的严格限制下，可以在提取过程中进行清洗，不必每次调用 时都进行value()，这也是我在开头提供的报价中明确表达的意图。然而，主要问题是洗钱不能在这里阻止 UB，即使它是在内部完成的node_type::mapped()。事实上，以下代码具有未定义的行为（示例假设sizeof(int) <= sizeof(float)）：

float g()
{
    float value = 0.0f; // deliberate separate initialization, see below
    value = 3.14f;
    int *intp = std::launder(reinterpret_cast<int *>(&value));
    *intp = 1;
    return value + *intp;
}

这是因为usingstd::launder根本不授予用户键入双关语的权限。相反，std::launder只允许重复使用的内存value通过建立之间一生相依float，在生活中&value，最初的int，此前住在这里std::launder。事实上，就标准而言，value而*intp不可能是活的同时，正是因为他们具有指针不兼容的类型和相同的内存位置。

（这里std::launder确实实现了例如防止重新排序value = 3.14f;to after *intp = 1。简单地说，编译器不允许重新排序写入之后的内容std::launder，也不允许从清洗过的指针读取之前的内容std::launder，除非它可以证明内存位置确实如此实际上不重叠，即使涉及指针不兼容的类型也是如此。我使用了单独的赋值，以便我可以更清楚地说明这一点。）

这最终归结为，为了安全地支持您设想的用法，实现必须在论文中提到的基础上添加额外的魔法（后者在很大程度上已经实现，因为它至少与的影响std::launder）。这不仅会造成额外的工作量，而且还可能在用户自愿遵守标准化限制的情况下产生阻止某些优化的副作用。在标准化 C++ 或几乎任何东西的过程中，专家们试图权衡预计成本与某些或至少可能的好处，这样的判断调用一直在进行。如果您仍需要了解更多信息，您可能必须直接联系一些 CWG 成员，因为这是提出应用这些限制的请求的地方，如上面链接的文件中所述。

希望这有助于澄清一些事情，即使您仍然不同意所采取的决议。

最后，我强烈建议您观看一些关于 C++ UB 的精彩演讲（如果您还没有看过的话），例如Piotr Padlewski 的Undefined Behavior is Awesome，或Chandler Carruth 的Garbage In, Garbage Out...。