前一阵，后辈问了我一个问题：

#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函数不符合预期的执行。

参考其给出了函数可能的实现：

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()。即：

#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函数先对序列进行反转，当然，这样会造成性能损失。