c++ - 带有提示的 std::unordered_map 插入

Question

std::map有一个insert方法采用“提示”迭代器，如果提示正确，该迭代器会将插入时间从 log(n) 减少到恒定时间。很明显这是如何工作的，因为容器可以确保新添加的项目具有小于提示的键并且具有大于提示之前的项目的键。否则提示是错误的，它会执行正常的插入。

std::unordered_map也有类似insert的with提示功能。如果有的话，提示有什么作用？对我来说，如何使用另一个“提示”迭代器来加速哈希映射插入并不明显。

如果使用，什么是适当的“提示”。在std::map中，通常通过调用lower_bound地图来找到提示。

Answer 1

这是一个接口兼容性问题。基本上，设计是在考虑std::map.

换句话说，因为std::unordered_map它没有区别，所以提供或不提供提示。

此处评论的其他信息：

界面兼容性非常重要，因为能够快速/轻松地在两者之间切换map并unordered_map提供无痛转换的宝贵灵活性，因为性能通常是选择一个而不是另一个的决定因素。

Answer 2

该提示允许无序映射实现首先进行值比较以查看提示是否有效。这避免了必须执行比比较操作更昂贵的哈希函数。