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) 

但肯定反转比较的元素，然后将它们与 false 进行比较是双重否定，因此它们做了完全相同的事情？

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

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

一个简单的答案是，并且不太令人困惑的记住方法如下

std::lower_bound

- 将迭代器返回到给定范围内的第一个元素，即

EQUAL_TO or Greater than

val。

std::upper_bound

- 将迭代器返回到给定范围内的第一个元素，即

Greater than val

。

Answer 3

lower_bound

：

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

upper_bound

：

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

现在不小于某物和大于某物之间存在区别。

例如，如果你比较

4

和

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 4

来自 vscode 的简单回答

lower_bound：找到第一个可以在不改变顺序的情况下插入val的位置

upper_bound：找到可以在不改变顺序的情况下插入val的最后一个位置

Answer 5

简单的答案是 [ lower_bound, upper_bound )

s.lower_bound(t) 将返回迭代器到集合中的第一个元素 v 使得 v >= t
s.upper_bound(t) 将迭代器返回到集合中的第一个元素 v，使得 v > t。

当我们经常为STL集或图调用xxxxx_bound时，
我们经常希望找到某个范围内的数据。

我在这里分享了 lower_bound 和 upper_bound 样本的一些用法。 这样每个人都可以轻松使用并记住它。

迭代 [A, B) 中的所有值

set<int> s = {0,1,2,10,11,12,15};
int A=1, B=11;
for(auto iter = s.lower_bound(A); iter != s.lower_bound(B); iter++) {
    cout<<*iter<<"\t";
}

结果

1       2       10

它显示集合 s 中的所有 v 满足 1 < v <= 11 又名 [1, 11) 中的所有 v

迭代 [A, B] 中的所有值

set<int> s = {0,1,2,10,11,12,15};
int A=1, B=11;
for(auto iter = s.lower_bound(A); iter != s.upper_bound(B); iter++) {
    cout<<*iter<<"\t";
}

结果

1       2       10      11

它显示集合 s 中的所有 v 满足 1 <= v <= 11 又名 [1, 11] 中的所有 v

迭代 (A, B) 中的所有值

set<int> s = {0,1,2,10,11,12,15};
int A=1, B=11;
for(auto iter = s.upper_bound(A); iter != s.lower_bound(B); iter++) {
    cout<<*iter<<"\t";
}

结果

2       10

它显示集合 s 中的所有 v 满足 1 < v < 11 又名 (1, 11) 中的所有 v

迭代 (A, B] 中的所有值

set<int> s = {0,1,2,10,11,12,15};
int A=1, B=11;
for(auto iter = s.upper_bound(A); iter != s.upper_bound(B); iter++) {
    cout<<*iter<<"\t";
}

结果

2       10      11

它显示集合 s 中的所有 v 满足 1 < v <= 11 又名 (1, 11]

中的所有 v

Answer 6

想想有序字符串中的插入点。

您可以在所有其他 2 之前插入 2，或者在所有其他 2 之后插入 2。

例如

          l        u
          v        v
[1, 1, 1, 2, 2, 2, 3, 3, 3]