std::upper_bound 返回第一个大于给定值的元素位置，不查找相等或“不大于”的元素；例如在{1,2,2,3,4}中查2时指向3（索引3），要求范围已按相同比较规则升序排序。
std::upper_bound 返回的是「第一个大于」的位置
它不找相等的元素，也不找“刚好不大于”的位置——它只认准一个条件：!(value 不成立的那个起点。换句话说，返回的是所有满足 <code>element > value 的第一个迭代器。
常见错误是把它和 std::lower_bound 搞混：比如在 {1,2,2,3,4} 里查 2，std::lower_bound 指向第一个 2（索引 1），而 std::upper_bound 指向 3（索引 3）。这正是插入重复元素时“插在相同元素之后”的边界。
- 必须保证输入范围已按相同比较规则升序排序，否则行为未定义
- 默认用
比较，若自定义比较函数（如 <code>std::greater<int></int>），整个逻辑要反过来理解 - 返回值可能等于
end()，检查前务必判断，否则解引用会崩溃
怎么用 std::upper_bound 插入新元素不破坏顺序
典型场景：维护一个有序 std::vector，每次插入都保持升序，且允许重复——这时 std::upper_bound 给出的位置，就是新元素该塞进去的地方（插在所有相同元素之后）。
示例：往 vec = {1,2,2,2,3} 插入 2，用 std::upper_bound(vec.begin(), vec.end(), 2) 得到指向 3 的迭代器，vec.insert(it, 2) 后变成 {1,2,2,2,2,3}。
立即学习“C++免费学习笔记（深入）”；
- 别直接用
push_back再排序——O(n log n)，而upper_bound + insert是 O(n)，查找部分仅 O(log n) -
std::set或std::multiset虽自动有序，但不支持随机访问；若你需要下标或频繁切片，还是得用 vector + 手动维护 - 对
std::deque同样适用，但insert在中间性能差，慎用
传错比较函数会导致 upper_bound 完全失效
如果你用 std::sort(vec.begin(), vec.end(), std::greater<int>())</int> 排成降序，再直接调 std::upper_bound(vec.begin(), vec.end(), x)（没传第三个参数），结果毫无意义——因为默认仍按 查，和排序依据不一致。
正确做法是显式传同样的比较器：std::upper_bound(vec.begin(), vec.end(), x, std::greater<int>())</int>。此时它找的是「第一个小于 x」的位置（因 greater 下，“大于”逻辑被重定义）。
- 编译器不会报错，运行时返回看似合理的迭代器，但位置大概率错——这是最隐蔽的坑
- lambda 比较器也一样：排序和查找必须用同一个 lambda 实例（或语义完全一致的副本）
- 用
auto it = ...接收时，注意迭代器类型与容器匹配，别跨容器混用
在 map/set 中没有 upper_bound 成员函数？其实有，但用法不同
std::map 和 std::set 确实提供了 upper_bound 成员函数，但它不是算法，而是关联容器特化版本：时间复杂度 O(log n)，且不接受自定义比较器参数（直接用容器构造时的比较器）。
例如：my_map.upper_bound(key) 返回第一个键严格大于 key 的 iterator；而算法版 std::upper_bound(my_map.begin(), my_map.end(), ...) 不仅多此一举，还可能因 pair 比较逻辑出错（默认按 first 再按 second）。
- 对
std::map/std::set，永远优先用成员函数upper_bound，别用std::upper_bound算法 -
std::unordered_map没有upper_bound——它根本无序，没法定义“上界” - 成员函数返回
iterator，算法版返回任意迭代器类型（如vector::iterator），不能混赋值
真正容易被忽略的是：upper_bound 的“大于”是严格大于，且依赖你提供的比较关系是否满足严格弱序。哪怕只在一个边缘 case 里违反（比如自定义比较函数对相等对象返回 true），整个查找就不可靠——这种 bug 往往只在特定数据组合下暴露，很难复现。
