std :: unordered_map insert with hint [英] std::unordered_map insert with hint

问题描述

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

std :: unordered_map 也有类似的 insert 使用hint函数。什么，如果有什么，提示做什么？对于我来说，如何使用另一个提示迭代器来加速哈希映射插入并不明显。

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

解决方案

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

换句话说，对于 std :: unordered_map ，它没有提供或不提供提示。 p>

此处评论的其他信息：

界面兼容性非常重要，因为能够在 map 和 unordered_map 之间快速/轻松切换，提供了无痛转换的宝贵灵活性，因为性能往往是决定因素在选择其中一个。

std::map has an insert method that takes a "hint" iterator that will reduce the insertion time from log(n) to constant time if the hint is correct. Its pretty obvious how this would work, since the container could just make sure the newly added item has a key that is less than the hint and has a key that is greater than the item before the hint. Otherwise the hint was wrong and it performs a normal insert.

std::unordered_map also has a similar insert with hint function. What, if anything, does the hint do? Its not obvious to me how another a "hint" iterator could be used to speed up a hash map insertion.

If it is used, what is an appropriate "hint". In std::map, the hint is typically found by calling lower_bound on the map.

解决方案

It is an interface compatibility issue. Basically, the design is done considering the interface of std::map.

In other words, for std::unordered_map it does not differ a hint is provided or not.

Additional Information from the comments here:

The interface compatibility is very important because being able to quickly/easily switch between map and unordered_map provides the valuable flexibility of painlessly transition since performance is often the deciding factor in choosing one over the other.

这篇关于std :: unordered_map insert with hint的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！