记录编程学习
0%

C++ lower_bound 与upper_bound函数的使用

发表于 分类于

这一篇文档主要是对C++ STL里面的两个函数：lower_bound( )函数与upper_bound( )函数的简单使用的一个介绍，包括调用默认比较函数和自定义比较函数的用法。自定义比较函数主要是lambda表达式。

函数简介

lower_bound( )函数与upper_bound( )函数都是基于二分搜索操作的函数，其操作对象是有序的。lower_bound( )函数返回指向第一个不小于给定值的元素的迭代器，upper_bound( )函数返回指向第一个大于给定值的元素的迭代器。关于这两个函数更具体的声明和描述，可以查看cppreference网站中有关 lower_bound( ) 和upper_bound( )的描述。这里主要介绍一下这两个函数的使用。主要是使用默认的比较函数，以及自己构造比较函数的有关用法。

使用默认的比较函数

lower_bound函数

对lower_bound函数而言，其默认的比较函数是operator<。下面是一个简单的示例。例子中，data中存储的是按照非严格递增的方式存储的数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> data = { 1, 2, 4, 5, 5, 6 };
    for (int i = 0; i < 8; i++)
    {
        auto iter = lower_bound(data.begin(), data.end(), i);
        if (iter != data.end())
        {
            cout << "首个不小于" << i << "的元素的索引为：" << distance(data.begin(), iter);
            cout << " 该元素为：" << *iter << '\n';
        }
        else
        {
            cout << "data中不存在不小于" << i << "的元素\n";
        }
    }

}
1
2
3
4
5
6
7
8
首个不小于0的元素的索引为：0 该元素为：1 
首个不小于1的元素的索引为：0 该元素为：1
首个不小于2的元素的索引为：1 该元素为：2
首个不小于3的元素的索引为：2 该元素为：4
首个不小于4的元素的索引为：2 该元素为：4
首个不小于5的元素的索引为：3 该元素为：5
首个不小于6的元素的索引为：5 该元素为：6
data中不存在不小于7的元素

upper_bound函数

不同于lower_bound函数，upper_bound函数返回的是指向第一个大于给定值的元素的迭代器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> data = { 1, 2, 4, 5, 5, 6 };
    for (int i = 0; i < 8; i++)
    {
        auto iter = upper_bound(data.begin(), data.end(), i);
        if (iter != data.end())
        {
            cout << "首个大于" << i << "的元素的索引为：" << distance(data.begin(), iter);
            cout << " 该元素为：" << *iter << '\n';
        }
        else
        {
            cout << "data中不存在大于" << i << "的元素\n";
        }
    }

}

1
2
3
4
5
6
7
8
首个大于0的元素的索引为：0 该元素为：1
首个大于1的元素的索引为：1 该元素为：2 
首个大于2的元素的索引为：2 该元素为：4    
首个大于3的元素的索引为：2 该元素为：4       
首个大于4的元素的索引为：3 该元素为：5                
首个大于5的元素的索引为：5 该元素为：6                  
data中不存在大于6的元素                         
data中不存在大于7的元素

使用自定义的比较函数

自定义的比较函数，可以是自己重载的operator<函数，也可以是仿函数，纯比较函数，或者lambda表达式。下面，我采用lambda进行说明。

现在假设我们定义了一个自己的类Integer。然后我们使用lambda表达式作为自定义的比较函数。自定义的类如下：

1
2
3
4
5
6
7
8
struct Integer
{
    int value_=0;
    Integer() = default;
    Integer(int value) :value_(value)
    {}

};

观察下面的代码。代码中使用了自定义的lambda表达式，其输出结果和上面的lower_bound函数的结果一样。同样的，我们也可以使用upper_bound函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
{
    vector<Integer> data{ {1},{2},{4},{5},{5},{6} };
    for (int i = 0; i < 8; i++)
    {
        auto iter = lower_bound(data.begin(), data.end(), Integer(i), 
            [](const Integer& val, const Integer& ele)
            {
                return val.value_ < ele.value_;
            }
        );
        if (iter != data.end())
        {
            cout << "首个不小于" << i << "的元素的索引为：" << distance(data.begin(), iter);
            cout << " 该元素为：" << iter->value_ << '\n';
        }
        else
        {
            cout << "data中不存在不小于" << i << "的元素\n";
        }
    }

}

在这个例子中，我们用Integer对象和int比较的时候，将int构造了一个临时的Integer对象。但是如果我们直接让这两者比较呢？这里需要注意：在这种情况下，lower_bound函数和upper_bound函数中lambda表达式的写法有所不同。

1
2
3
4
5
6
7
8
9
10
11
      auto lower = lower_bound(data.begin(), data.end(), i, [](const Integer& ele,int val)
          {
              return ele.value_<val;
          }
      );
//注意参数的顺序
      auto upper = upper_bound(data.begin(), data.end(), i, [](int val, const Integer& ele)
          {
              return val < ele.value_;
          }
      );

可以发现，在lower_bound中，我们应该把int类型的参数放在第二个参数的位置，在调用的时候，val=i。而upper_bound则是相反的。