stl中upper_bound和lower_bound之间的区别

Question

我在查看这些页面上的upper_bound和lower_bound算法如何在stl中工作:lower_bound,upper_bound,并且在这些页面上以相同的方式记录:lower_bound,upper_bound

查看链接中的代码,它们似乎对我做了完全相同的事情,只有以下几行不同(查看前两个链接中的代码):

lower_bound(第10行):

if (*it<val) {                 // or: if (comp(*it,val)), for version (2)

upper_bound(第10行):

 if (!(val<*it))                // or: if (!comp(val,*it)), for version (2) 

但肯定会逆转比较元素,然后将它们与假比较是双重否定,因此它们完全相同？

实际上是否存在差异,我只是没有看到,这是网站文档中的错误吗？如果是后者,那么正确的方法是什么？

Answer 1

value a a a b b b c c c
index 0 1 2 3 4 5 6 7 8
bound       l     u

其中l代表下限b,并u代表上限b.

因此,如果有一系列值与所使用的比较"相等",lower_bound那么首先upper_bound给出一个这样的值,给你一个接一个的结束.这是STL范围的正常模式[first, last).

Answer 2

lower_bound：

返回指向范围 [first,last) 中第一个元素的迭代器，该元素的比较值不小于 val。

upper_bound：

返回指向范围 [first,last) 中第一个元素的迭代器，该元素比较大于 val。

现在，不小于某物和大于某物是有区别的。

例如，如果你比较4and 5，你可以说

5 is _not less than_ 4
5 is _greater than_  4

但是，如果你比较你比较4和4：

4 is _not less than_    4
4 is _not greater than_ 4

Answer 3

一个简单的答案是不那么令人困惑的记住这一点的方法如下

std::lower_bound - 将迭代器返回到给定范围内的第一个元素，即 EQUAL_TO or Greater thanval。

std::upper_bound- 将迭代器返回到给定范围内的第一个元素，即Greater than val。