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

Question

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

谁能提供一些关于这方面的信息或给出一些示例/说明我们何时可能知道放置的元素应该去哪里？

Answer 1

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

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

unordered_map::emplace_hint 的另一个好处|与 map::emplace_hint 更好的 API 兼容性，因此代码可以切换容器类型并具有emplace_hint s 不会破坏编译，尽管它们最终可能比代码切换到 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是可以插入的 key ，__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<> 比较实例化无序容器时可以假设是这样。)。