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

Question

我知道如何使用std::unordered_map::emplace,但我该如何使用emplace_hint？cplusplus和cppreference都没有提供一组示例来说明我们如何知道放置元素的位置.

任何人都可以提供一些有关这方面的信息,或者提供一些示例/插图,告诉我们什么时候可以知道布置元素应该去哪里？

Answer 1

有什么可能unordered_map与提示有关？好吧,如果迭代器使用与emplace_hint要求插入的元素相同的键来寻址一个元素,那么它可能会很快失败 - 只是一个关键的比较,没有任何散列或在该桶中的任何散列碰撞元素列表中摸索.但是如果密钥不匹配,那么提示是无用的,因为任何其他密钥 - 无论如何"接近"值 - 应该(概率地)在一个完全不相关的桶(给定通常被认为是"好"的哈希函数) ),所以时间本来会浪费在一个关键的比较上只是为了重新开始,好像它是正常的emplace.

当你插入预先排序的元素时,这可能很有用,旨在删除过程中的大量重复项,但是关键是如此之大,以至于将迭代器保留为刚插入的元素比复制更容易.密钥,或者散列函数可能特别慢.

另一个好处unordered_map::emplace_hint是更好的API兼容性map::emplace_hint,因此代码可以切换容器类型并且emplace_hint不会破坏编译,尽管它们最终可能比代码切换emplace()为关闭但不同的关键提示更慢用一个map可能没用unordered_map.