std::lower_bound 与 upper_bound：自定义比较器参数顺序相反的坑

在按时间戳升序的序列里取 [start, end] 区间——日志、遥测数据、缓存切片里再常见不过的需求。标准库的 std::lower_bound 和 std::upper_bound 正好一对：前者找第一个 >= start 的元素，后者找第一个 > end 的元素。但给它们传自定义比较器时有一个非常容易踩的坑：两个算法调用比较器的参数顺序相反。这篇文章把这个约定讲清楚，并复盘一个真实写错的例子。

两个算法的调用约定

按 cppreference 的描述，比较器 comp 都要求是"第一个参数排在第二个参数之前"的谓词，但算法内部传参顺序不同：

算法	谓词形式	默认语义	返回
lower_bound	comp(element, value)	element < value	第一个 element >= value
upper_bound	comp(value, element)	value < element	第一个 element > value

cppreference 对 lower_bound 的前置条件原文是：元素必须按表达式 bool comp(e, value) 划分（partitioned），否则行为未定义；upper_bound 对应的是 bool comp(value, e)。

也就是说，lower_bound 里元素在前、查找值在后，upper_bound 里查找值在前、元素在后。默认比较器 operator< 恰好两种顺序都能表达，所以不传比较器时感知不到差异；一旦换成自定义 lambda，参数顺序就必须分别对待。

正确写法

对一个按 timestamp 升序的元素序列取区间：

struct Sample {
    uint64_t timestamp;
    // ... 其他字段
};

// lower_bound: comp(element, value) —— 元素在前，查找值在后
// 返回第一个 timestamp >= start 的迭代器
auto first = std::lower_bound(samples.begin(), samples.end(), start,
    [](const Sample &e, uint64_t v){
        return e.timestamp < v;
    });

// upper_bound: comp(value, element) —— 查找值在前，元素在后
// 返回第一个 timestamp > end 的迭代器
auto last = std::upper_bound(samples.begin(), samples.end(), end,
    [](uint64_t v, const Sample &e){
        return v < e.timestamp;
    });

// [first, last) 即 timestamp 落在 [start, end] 内的区间

两个 lambda 的比较方向都照抄默认语义（e < v / v < e），只是形参顺序跟着算法约定走。

复盘一个典型错误

出错的版本想走捷径——两个算法复用同一个 lambda：

// 错误示例
auto first = std::lower_bound(samples.begin(), samples.end(), start,
    [](const Sample &e, uint64_t v){
        return v < e.timestamp;      // 方向反了
    });

auto last = std::upper_bound(samples.begin(), samples.end(), end,
    [](const Sample &e, uint64_t v){ // 形参顺序不匹配，编译失败
        return v < e.timestamp;
    });

两处错误：

1. lower_bound 处方向反了。comp(e, v) 写成 v < e.timestamp，含义变成"大于查找值的元素排在前面"。对升序序列，这根本不满足划分前提，按标准是未定义行为——实际二分下来返回的是靠近序列前端的位置，静默给出错误结果。
2. upper_bound 处编译不过。算法按 comp(value, element) 传参，第一个实参是 uint64_t 的查找值，绑定不到 const Sample& 形参上，直接编译错误。

第一个错误尤其危险：它不报错，只在大数据量下才能看出取出的区间不对。

记忆方式

两个算法都可以记成"返回第一个使 comp 为 true 的位置"，区别只在谓词的参数顺序：

• lower_bound：comp(e, value)——和"找下界"的方向一致，元素主动去和值比较；
• upper_bound：comp(value, e)——值主动去和元素比较。

更简单的实践建议：不要复用同一个 lambda。按各自约定各写各的，比较方向照抄默认 less 的两种表达式，写错的机会小得多。

小结

lower_bound 的比较器约定是 comp(element, value)，upper_bound 是 comp(value, element)，方向相反。复用同一个 lambda 传给两个算法，轻则方向反掉得到静默错误结果，重则编译失败。各写各的、照抄默认语义的表达式，是最稳妥的做法。