<algorithm>头文件中，用于在指定范围内查找大于目标值的第一个元素。该函数的语法格式有 2 种，分别是：
//查找[first, last)区域中第一个大于 val 的元素。
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
const T& val);
//查找[first, last)区域中第一个不符合 comp 规则的元素
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
const T& val, Compare comp);
其中，first 和 last 都为正向迭代器，[first, last) 用于指定该函数的作用范围；val 用于执行目标值；comp 作用自定义查找规则，此参数可接收一个包含 2 个形参（第一个形参值始终为 val）且返回值为 bool 类型的函数，可以是普通函数，也可以是函数对象。
#include <iostream> // std::cout
#include <algorithm> // std::upper_bound
#include <vector> // std::vector
using namespace std;
//以普通函数的方式定义查找规则
bool mycomp(int i, int j) { return i > j; }
//以函数对象的形式定义查找规则
class mycomp2 {
public:
bool operator()(const int& i, const int& j) {
return i > j;
}
};
int main() {
int a[5] = { 1,2,3,4,5 };
//从 a 数组中找到第一个大于 3 的元素
int *p = upper_bound(a, a + 5, 3);
cout << "*p = " << *p << endl;
vector<int> myvector{ 4,5,3,1,2 };
//根据 mycomp2 规则，从 myvector 容器中找到第一个违背 mycomp2 规则的元素
vector<int>::iterator iter = upper_bound(myvector.begin(), myvector.end(), 3, mycomp2());
cout << "*iter = " << *iter;
return 0;
}
程序执行结果为：
*p = 4
*iter = 1
template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
ForwardIterator it;
iterator_traits<ForwardIterator>::difference_type count, step;
count = std::distance(first,last);
while (count>0)
{
it = first; step=count/2; std::advance (it,step);
if (!(val<*it)) // 或者 if (!comp(val,*it)), 对应第二种语法格式
{ first=++it; count-=step+1; }
else count=step;
}
return first;
}
本文链接：http://task.lmcjl.com/news/18611.html