带有提示的std :: unordered_map插入

Question

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

std::unordered_map也有类似insert的提示功能.提示有什么作用？我不清楚如何使用另一个"提示"迭代器来加速哈希映射插入.

如果使用它,什么是适当的"提示".在std::map,通常通过调用lower_bound地图找到提示.

Answer 1

这是一个接口兼容性问题.基本上,设计是考虑到界面std::map.

换句话说,因为std::unordered_map它没有差异,所以提供或不提供提示.

此处评论的其他信息:

接口兼容性非常重要,因为它能够快速/轻松地切换map并unordered_map提供无痛过渡的宝贵灵活性,因为性能通常是选择其中一个的决定性因素.

+1是的,接口兼容性对于通用代码非常重要(例如,容器是模板参数:`template <class Map>`).能够快速/轻松地在`map`和`unordered_map`之间切换是非常重要的,因为性能通常是选择一个而不是另一个的决定性因素. (7认同)
@HowardHinnant:如OP所指出的,一个提示通常通过调用映射:: LOWER_BOUND()获得的,并且unordered_map不具有此方法(COS它是没有意义的无序容器).这是不是仍然没有提供接口兼容性？ (5认同)
@HowardHinnant：清晰度不应该比方便更重要吗？在这种情况下，便利性很小，因为只是为您提供了更兼容的界面。我相信困惑的人们试图意识到如何使用该提示参数所花费的总时间比真正需要在 map 和 unordered_map 之间切换的人所获得的时间要多。当然，这是我的主观意见。 (2认同)

Answer 2

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

我认为这里的要点是，如果提示指向正确的项目...也就是说，键已经在 unordered_map 中，那么插入将看到这一点（通过将提示处的值与传入的值进行比较），并且不需要计算哈希值。如果键不在unordered_map中，我认为这种情况下不会有任何改进。 (2认同)