前一阵，后辈问了我一个问题：
1
2
3
4
5
6
7
8
9
10
11
12
| #include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> a = {1, 2, 3, 4, 5, 6};
auto p = lower_bound(a.begin(), a.end(), 3, greater<int>());
cout << *p << endl;
return 0;
}
|
为什么这段代码为什么执行结果为0？
确实，从直观思考上来说，返回结果确实有些诡异。一时间我也不太理解。
我的第一反应是比较 p与 a.end()的位置关系，发现 p=a.end()。也就是说，函数并没有在容器中找到比a大的元素，这并不符合预期的执行结果。
遇事不决翻文档，于是我找到了这篇文章。其中详细介绍了 upper_bound函数的原型与定义，其中介绍中的这句话解决了这个问题：
范围 [first, last) 必须已相对于表达式 !(value < element) 或 !comp(value, element) 划分，即所有令此表达式为 true 的元素必须前趋所有令此表达式为 false 的元素。完全排序的范围满足此判别标准。
除了常提到的序列有序前提以外，lower_bound对重载的比较关系也有一定的要求，这也就导致了上例中 lower_bound函数不符合预期的执行。
参考其给出了函数可能的实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| template<class ForwardIt, class T, class Compare>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
ForwardIt it;
typename std::iterator_traits<ForwardIt>::difference_type count, step;
count = std::distance(first,last);
while (count > 0) {
it = first;
step = count / 2;
std::advance(it, step);
if (!comp(value, *it)) {
first = ++it;
count -= step + 1;
}
else
count = step;
}
return first;
}
|
也对应了介绍中的说法，当采用上例的函数模版重载大小关系，会使迭代器 it不断向后迭代，直至与 a.end()重合。
所以，要使运行结果正确，可以对函数传递 a的反向迭代器 a.rbegin()与 a.rend()。即：
1
2
3
4
5
6
7
8
9
10
11
12
| #include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> a = {1, 2, 3, 4, 5, 6};
auto p = lower_bound(a.rbegin(), a.rend(), 3, greater<int>());
cout << *p << endl;
return 0;
}
|
或者使用 reverse函数先对序列进行反转，当然，这样会造成性能损失。