为什么unordered_multimap没有lower_bound和upper_bound?

问题描述 投票:0回答:2

从multimap切换到unordered_multimap,我意识到没有相应的:

  • LOWER_BOUND
  • UPPER_BOUND

似乎显而易见的是,equal_range可以做出一个简单的等价物,但我想知道我是否遗漏了一些东西:这个选择的原因。

来自任何其他库,我会认为差异是一个简单的错误,但STL在这方面通常是非常正交的。

c++ stl
2个回答
8
投票

它就在名字中。 unordered_multimap。没有订单,因此,没有上/下关系。存储在unordred_*容器中的项(键)甚至不需要实现< / std::less,只需要哈希和相等操作。


2
投票

如果你查看std::lower_bound()std::upper_bound()文档,你可以看到它们对它们可以应用的范围提出了特殊要求:

范围[first,last]必须根据表达式!(value <element)或!comp(value,element)进行分区,即表达式为true的所有元素必须位于表达式为false的所有元素之前。完全排序的范围符合此标准。

由于std::map满足该标准,因此可以在其上使用这些泛型函数,但这种使用效率不高,因为这些泛型函数不知道地图的内部表示。所以std::map提供了自己的,更有效的变体(虽然不那么通用)。另一方面的std::unordered_map不符合标准,所以你不能在它上面应用那些泛型函数,所以对std::unorderd_map本身实现它们没有任何意义。

我虽然lower_bound返回带给定键的第一个迭代器,但这可能在无序容器上。

这就是std::find()所做的。 std::lower_bound()std::map::lower_bound()给你的位置,范围的元素不小于关键。您可以使用它来查找特定元素的事实是该行为的有用副作用,但不是这些函数的主要目的。

© www.soinside.com 2019 - 2024. All rights reserved.