C++中std::upper

C++中std::upper_bound用法解析

在C++标准模板库（STL）的算法工具箱里，upper_bound() 绝对算得上是一把精准的“探针”。它的核心任务很明确：在一个已经排好序的区间 [first, last) 内，帮你快速定位到第一个**严格大于**指定值 value 的那个元素。这个函数会直接返回指向该元素的迭代器，其高效的二分查找机制，让它成为处理有序数据时的首选工具之一。

1. 函数的标准语法形式

我们先来看看它的标准签名，理解其形式是正确使用的前提：

template
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);

2. 核心行为与返回值

简单来说，它会在给定的范围 [first, last) 内，搜索第一个使得“元素值大于 val”成立的位置。找到后，便返回指向该位置的迭代器，这个迭代器的类型与传入的 first、last 保持一致。如果范围内没有这样的元素，它会返回 last，也就是区间的“尾后”迭代器。

3. 典型应用一：在标准容器中使用

对于 std::vector、std::array 这类顺序容器，结合它们自带的 begin() 和 end() 迭代器来调用 upper_bound()，是再自然不过的事情。由于容器本身有序，这个操作能在 O(log n) 的时间复杂度内完成定位，效率非常高。

马上学习“C++免费学习笔记（深入）”：

#include
#include
#include
using namespace std;
int main() {
vector v = {1, 2, 3, 4, 5};
// 查找第一个大于3的元素
auto it = upper_bound(v.begin(), v.end(), 3);
if (it != v.end()) {
cout << *it << endl; // 输出：4
}
return 0;
}

举个例子，如果想查找 vector 中首个大于数值 3 的元素所处的下标（索引），可以这样操作：

int idx = upper_bound(v.begin(), v.end(), 3) - v.begin();
cout << idx << endl; // 输出：3

输出结果为 3，这对应着值为 4 的元素在 vector 中的位置，完全符合“第一个大于3”的预期，逻辑正确。

4. 典型应用二：在普通数组中使用

那么，如何对最基础的普通数组执行相同的查找操作呢？原理其实相通，只是传递的迭代器变成了指针。可以采用下面这种等效的写法：

#include
#include
using namespace std;
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
// 查找第一个大于25的元素
int* p = upper_bound(arr, arr + n, 25);
if (p != arr + n) {
cout << *p << endl; // 输出：30
}
return 0;
}

最终输出值为 30，因为它是数组中第一个大于 25 的数。结果准确，逻辑成立。

不仅如此，upper_bound() 同样支持对数组的任意子区间进行精准查找。比如，你只想在数组的某一段里搜索，完全没问题。一个非常常用的表达式是这样的：int pos = upper_bound(a + l, a + r, m) - a;

这条语句的用途是获取数组 a 中，在子区间 [l, r) 内第一个大于 m 的元素，其在整个数组中的位置索引。这里，a 代表数组的起始地址（指针），而 l 与 r 则分别限定了查找区间的左闭右开边界。这种写法在算法竞赛和需要处理局部数据的场景中尤为常见。