c++ - 什么时候使用 std::unordered_map::emplace_hint？

Question

我知道如何使用 std::unordered_map::emplace，但如何使用 emplace_hint？都不是cplusplus也不cppreference提供一组示例来说明我们如何知道将元素放在哪里。

任何人都可以提供一些这方面的信息或提供一些示例/说明，说明我们什么时候可以知道放置的元素应该放在哪里吗？

Answer 1

unordered_map 可以做什么可能与提示有关吗？好吧，如果迭代器使用与 emplace_hint 的元素相同的键来寻址一个元素。已被要求插入，然后它可能会很快失败 - 只是一个键比较，没有任何散列或在该桶中的任何散列冲突元素列表中摸索。但是，如果 key 不匹配，那么提示将无用，因为任何其他 key - 无论值多么“接近” - 应该(概率)位于完全不相关的桶中(考虑到通常被认为是“好”的哈希函数), 所以时间会被浪费在一个关键的比较上，只是不得不重新开始，就好像它是一个正常的 emplace .

当您插入预先按键排序的元素时，这可能很有用，目的是在过程中删除大量重复项，但键是如此之大，因此将迭代器保留到刚刚插入的元素比 key 的拷贝，或者哈希函数可能特别慢。

unordered_map::emplace_hint 的另一个好处与 map::emplace_hint 的 API 兼容性更好，因此代码可以切换容器类型并具有 emplace_hint这不会破坏编译，尽管它们最终可能会比代码切换到 emplace() 时慢作为有助于 map 的接近但不同的关键提示可能对 unordered_map 没用.

---

刚刚使用 GCC 10.2 g++ -E输出以查看它是否执行上述操作。 emplace_hint调用 _M_insert_multi_node(...)其中有这一行:

__node_base* __prev = __builtin_expect(__hint != nullptr, false)
                      && this->_M_equals(__k, __code, __hint)
                      ? __hint
                      : _M_find_before_node(__bkt, __k, __code);

以上，__k是可以插入的键，__code是哈希码，__hint是提示迭代器/指针； _M_equals(...)返回:

return _Equal_hash_code<__node_type>::_S_equals(__c, *__n) &&
       _M_eq()(__k, this->_M_extract()(__n->_M_v()));

因此，在使用提示迭代器。这是它使用提示的唯一情况。想象一下，桶在逻辑上有一些碰撞元素与键 K1、K2、K3、K4 链接在一起，你的提示迭代器指向 K4，但你试图用 K2 插入一个拷贝:因为迭代器仅向前，你必须使用 _M_find_before_node(...)比您的提示指向的更早到达链中的碰撞元素。 _M_find_before_node(...)之后您可以从 K1 向前扫描以查看要插入的键 - K2 - 是否已经存在于在桶中发生碰撞的元素中。

(当已知键比较成本低时，可以通过跳过散列比较来改进实现，但是使用类型特征正确设置条件会有点痛苦——你怎么知道哪些键相等函数是成本低的? 对于小型、标准布局、普通可复制类型或类似类型，至少在使用默认 std::equals<> 比较....实例化无序容器时可以假设如此。