C++ 易误用的标准库函数

标准库里有不少函数，签名朴素、名字“望文生义”，实际语义却和直觉差一截。用对了是利器，用错了编译能过、跑出错误结果还不报警。本系列收集这类“看着会、用着错”的函数，从二分查找家族的 lower_bound / upper_bound 开始。

前置概念：划分而非“已排序”

二分家族的前置条件比“整个区间升序”更宽松——它要求区间按给定比较被划分：

lower_bound：所有满足 elem < value 的元素都在不满足者之前。
upper_bound：所有满足 !(value < elem) 的元素都在满足者之前。

实际上几乎总是用完全有序的区间去喂它们；关键是：区间排序用的比较器，必须和 lower_bound/upper_bound 传入的比较器一致。混用 > 排序却用默认 < 查找，结果未定义。

`std::lower_bound`

定义

在已划分区间 [first, last) 中，返回指向第一个不小于 value 的元素的迭代器；即首个 !(elem < value) 的位置（默认比较下即 elem >= value）。

若所有元素都小于 value，返回 last。

template <class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first,
                      ForwardIt last,
                      const T& value);

template <class ForwardIt, class T, class Comp>
ForwardIt lower_bound(ForwardIt first,
                      ForwardIt last,
                      const T& value,
                      Comp comp);

复杂度：比较次数 O(log n)；迭代器为随机访问时整体 O(log n)，否则推进是 O(n)。

等价的直观理解

“把 value 插入并保持有序时，应插入的最靠前位置。”这也是为什么它常被当成“查找”来用——但查找语义和插入语义并不等价。

常见误用

① 把“找到插入点”当成“找到元素”。

lower_bound 找的是 >=，不是 ==。当 value 不存在时，它返回的是“value 本该在的位置”，指向的可能是大于 value 的元素，而非“没找到”。

std::vector<int> v{1, 2, 4, 5};      // 没有 3
auto it = std::lower_bound(
    v.begin(), v.end(), 3);
// it 指向 4，不是"没找到"，也不是 3

if (it != v.end()) {
  std::cout << *it;                  // 输出 4，误导！
}

② 不检查存在性就当命中用。

正确判等必须显式比较。默认 < 时：

1
2
3

auto it = std::lower_bound(
    v.begin(), v.end(), 3);
bool found = it != v.end() && *it == 3;

使用自定义比较器时，*it == value 可能不可用（例如只比较结构体的某个字段）。此时存在性判据是“既不 value < *it、又不 *it < value”，即：

1
2
3

bool found = it != v.end() && !comp(value, *it);
//       等价于：!(value < *it)，即 value <= *it
//       配合 lower_bound 的 *it >= value，得 *it == value

③ 对未排序区间使用。

前置条件不满足，结果是错的（不一定是 UB，但语义失效）。lower_bound 不会替你检查有序性。

④ 关联容器用了自由函数版本。

对 set/map/multiset/multimap 调用 std::lower_bound 是 O(n)（先构造迭代器路径再线性推进），应优先用成员函数 c.lower_bound(key)，它走红黑树是 O(log n)。

std::set<int> s{1, 2, 4, 5};

// 慢：自由函数版，O(n)
std::lower_bound(s.begin(), s.end(), 3);

// 快：成员函数版，O(log n)
s.lower_bound(3);

unordered_* 是哈希表，没有 lower_bound，调用自由函数版同样是错的（无序）。

`std::upper_bound`

定义

返回指向第一个大于 value 的元素的迭代器；即首个 value < elem 的位置（默认比较下即 elem > value）。

若所有元素都不大于 value，返回 last。

template <class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first,
                      ForwardIt last,
                      const T& value);

template <class ForwardIt, class T, class Comp>
ForwardIt upper_bound(ForwardIt first,
                      ForwardIt last,
                      const T& value,
                      Comp comp);

复杂度同 lower_bound。

常见误用

① 误以为返回“最后一个等于 value 的元素”。

它返回的是第一个 > value 的位置。要“最后一个 == value 的元素”，得 upper_bound(...) - 1，且仅当确实存在等于 value 的元素时才有意义。

② 误以为返回“最后一个 <= value 的位置”。

直觉上“上界”像 <=，实际是严格 >。这一条与 lower_bound 的 >= 形成对称，但极易记反。

③ 不检查存在性。

和 lower_bound 一样可能返回 last，也可能指向不等于 value 的元素。

std::vector<int> v{1, 2, 4, 5};      // 没有 3
auto it = std::upper_bound(
    v.begin(), v.end(), 3);
// it 指向 4（首个 > 3），并不代表"存在 3"

二者配合：`equal_range`

equal_range 一次返回 (lower_bound, upper_bound) 组成的半开区间 [lo, up)，正是所有等于 value 的元素的区间。

1 2	`auto [lo, up] = std::equal_range( v.begin(), v.end(), 3);`

由此衍生几个 O(log n) 的高效操作，远胜朴素写法：

需求	正确写法	常见错误写法
是否存在	`lo != up`	用 `lower_bound` 后不判等
等于 value 的个数	`up - lo`	`std::count`（O(n)）
第一个等于 value 的位置	`lo`（若 `lo != up`）	`lower_bound` 不判等
最后一个等于 value 的位置	`up - 1`（若 `lo != up`）	直接取 `upper_bound`
删除所有等于 value 的元素	`v.erase(lo, up)`	循环 `erase`

对 multiset/multimap，成员 equal_range 同样是 O(log n)，是“按键取区间”的标准姿势。

一张图看清边界

对有序序列 {1, 2, 3, 3, 3, 5, 7} 查找 value = 3：

下标:  0  1  2  3  4  5  6
值:    1  2  3  3  3  5  7
             ^        ^
           lower     upper

  lower_bound → 下标 2，首个 >= 3（第一个 3）
  upper_bound → 下标 5，首个 > 3（值 5）
  equal_range → [下标 2, 下标 5) = 三个 3

lower_bound 指向左边界（首个 >=，即第一个 3），upper_bound 指向右边界之后（首个 >，即值 5）。
二者之差（up - lo）即等于 value 的元素个数。
若 value = 4（不存在）：lower_bound 与 upper_bound 都指向 5，equal_range 为空区间 lo == up，据此判断“不存在”。

边界情形：全大于 / 全小于 / 空区间

这三种极端情形最容易被“成功路径”的惯性带偏，逐一拆开看。

全小于 value（value 比谁都大）

没有任何元素 >= value，lower_bound 与 upper_bound 都返回 end()，equal_range 为空。

std::vector<int> v{1, 2, 3};        // 全小于 10
auto it = std::lower_bound(
    v.begin(), v.end(), 10);
// it == v.end()

*it;                          // UB！不可解引用 end
bool found = it != v.end()
            && *it == 10;     // false，短路保证安全

陷阱：解引用 end() 是未定义行为。判等前必须先判 it != last，且靠 && 短路避免越界。

全大于 value（value 比谁都小）

第一个元素就已经 >= value，lower_bound 与 upper_bound 都返回 begin()，equal_range 为空。这是最隐蔽的坑：迭代器完全有效、it != end() 成立，但它指向的元素大于 value，并不等于 value。

std::vector<int> v{5, 6, 7};        // 全大于 2
auto it = std::lower_bound(
    v.begin(), v.end(), 2);
// it == v.begin()，有效但指向 5

if (it != v.end()) {          // 成立，容易误判为“找到了”
  std::cout << *it;           // 输出 5，不是 2
}

bool found = it != v.end()
            && *it == 2;      // false，必须再判等

只判 it != end() 就当命中，会拿到一个错误的值还不报警。这是 lower_bound 最常见的真实事故。

空区间

first == last，三个函数都返回 first（也就是 last），equal_range 为空。和“全小于”一样，解引用即 UB。

std::vector<int> v;            // 空
auto it = std::lower_bound(
    v.begin(), v.end(), 3);
// it == v.begin() == v.end()

三种情形一览

情形	`lower_bound`	`upper_bound`	`equal_range`	解引用返回值
全 `< value`	`end`	`end`	`[end, end)` 空	UB（end 不可解引用）
全 `> value`	`begin`	`begin`	`[begin, begin)` 空	有效，但 `*it != value`
空区间	`first`(=`last`)	`first`	`[first, first)` 空	UB
value 存在	首个 `==`	首个 `>`	非空	安全，`*it == value`

结论：用 `equal_range` 判存在最稳

三种极端情形下 equal_range 都返回空区间，而 value 存在时区间非空。因此 lo != up 是唯一不需要解引用、不依赖比较器细节就能判存在的方式，比 lower_bound 后判等更不易错：

auto [lo, up] = std::equal_range(
    v.begin(), v.end(), value);
if (lo != up) {               // 存在，且 *lo 即首个命中
  // 安全使用 *lo
}

若坚持用 lower_bound，判等模板固定为 it != last && *it == value（默认比较）或 it != last && !comp(value, *it)（自定义比较），缺一不可。

速查表

函数	返回指向	默认比较语义	value 不存在时
`lower_bound`	首个不小于 value	`elem >= value`（`!(elem<value)`）	指向首个 `> value` 的元素，或 `end`
`upper_bound`	首个大于 value	`elem > value`（`value<elem`）	与 lower_bound 重合，指向首个 `> value` 的元素，或 `end`
`equal_range`	`[lower, upper)`	上述两者	空区间，`lo == up`

判等口诀

存在性：lower_bound 后必须判等——it != last && *it == value（默认比较）；自定义比较用 it != last && !comp(value, *it)。equal_range 则看 lo != up。
比较器一致性：排序、查找用同一套 comp。
容器选型：关联容器用成员函数版；无序容器根本不该用二分家族。

后续将陆续补充 std::remove/erase 的“假删除”、std::unique 的“仅去相邻”、std::bind 与 std::function 的开销陷阱、std::async 的“忘了等”等同样容易踩坑的函数。