比较函数（<或<=）对lower_bound和upper_bound的影响及结果解析

首先看示例C++代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
        vector<int> v = {0, 1, 2, 3, 3, 3, 3, 3, 4, 5, 6, 7};

        auto it1 = lower_bound(v.begin(), v.end(), 3, [](int a, int b) {return a < b;});
        auto it2 = lower_bound(v.begin(), v.end(), 3, [](int a, int b) {return a <= b;});
        auto it3 = upper_bound(v.begin(), v.end(), 3, [](int a, int b) {return a < b;});
        auto it4 = upper_bound(v.begin(), v.end(), 3, [](int a, int b) {return a <= b;});

        cout << distance(v.begin(), it1) << endl;
        cout << distance(v.begin(), it2) << endl;
        cout << distance(v.begin(), it3) << endl;
        cout << distance(v.begin(), it4) << endl;

        return 0;
}

程序运行结果：

3
8
8
3

结果解释 #

要理解结果，必须明确lower_bound和upper_bound的核心逻辑，以及自定义比较函数的参数含义：

• lower_bound：返回第一个不满足comp(element, val)的元素迭代器。所有在该迭代器之前的元素，都满足comp(element, val)（即应该排在val前面）。
• upper_bound：返回第一个满足comp(val, element)的元素迭代器。该迭代器及之后的元素，都满足comp(val, element)（即val应该排在这些元素前面）。
• 自定义比较函数comp(a, b)的含义是：a应该排在b前面时返回true。

逐个分析四个迭代器：

1. it1（lower_bound + a < b）
   comp逻辑是element < 3，lower_bound找第一个不满足该条件的元素，也就是第一个element >= 3的元素。数组中第一个3在索引3，所以输出3。

2. it2（lower_bound + a <= b）
   comp逻辑是element <= 3，lower_bound找第一个不满足该条件的元素，也就是第一个element > 3的元素。数组中第一个大于3的是4，在索引8，所以输出8。

3. it3（upper_bound + a < b）
   comp逻辑是a < b，upper_bound找第一个满足3 < element的元素，也就是第一个element > 3的元素，即索引8的4，所以输出8。

4. it4（upper_bound + a <= b）
   comp逻辑是a <= b，upper_bound找第一个满足3 <= element的元素，也就是第一个element >= 3的元素，即索引3的3，所以输出3。

问题解答 #

1. 使用<的lower_bound是否始终等价于使用<=的upper_bound？ #

是的。

• lower_bound(first, last, val, [](a,b){return a < b;})：找第一个element >= val的位置。
• upper_bound(first, last, val, [](a,b){return a <= b;})：找第一个满足val <= element的位置，也就是第一个element >= val的位置。
  只要数组按照对应比较规则有序，两者结果完全一致。

2. 使用<=的lower_bound是否始终等价于使用<的upper_bound？ #

是的。

• lower_bound(first, last, val, [](a,b){return a <= b;})：找第一个element > val的位置。
• upper_bound(first, last, val, [](a,b){return a < b;})：找第一个满足val < element的位置，也就是第一个element > val的位置。
  只要数组按照对应比较规则有序，两者结果完全一致。

内容的提问来源于stack exchange，提问作者ThunderPhoenix