lower_bound()的一个未预期的执行行为

前一阵,后辈问了我一个问题:

 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?

确实,从直观思考上来说,返回结果确实有些诡异。一时间我也不太理解。

我的第一反应是比较 pa.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函数先对序列进行反转,当然,这样会造成性能损失。