std::ranges::upper_bound

在头文件 `<algorithm>` 中定义
调用签名
	(1)
template< std::forward_iterator I, std::sentinel_for<I> S, class T, class Proj = std::identity, std::indirect_strict_weak_order <const T*, std::projected<I, Proj>> Comp = ranges::less > constexpr I upper_bound( I first, S last, const T& value, Comp comp = {}, Proj proj = {} );			(自 C++20) (直到 C++26)
template< std::forward_iterator I, std::sentinel_for<I> S, class Proj = std::identity, class T = std::projected_value_t<I, Proj>, std::indirect_strict_weak_order <const T*, std::projected<I, Proj>> Comp = ranges::less > constexpr I upper_bound( I first, S last, const T& value, Comp comp = {}, Proj proj = {} );			(自 C++26)
		(2)
template< ranges::forward_range R, class T, class Proj = std::identity, std::indirect_strict_weak_order <const T*, std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less > constexpr ranges::borrowed_iterator_t<R> upper_bound( R&& r, const T& value, Comp comp = {}, Proj proj = {} );				(自 C++20) (直到 C++26)
template< ranges::forward_range R, class Proj = std::identity, class T = std::projected_value_t<ranges::iterator_t<R>, Proj>, std::indirect_strict_weak_order <const T*, std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less > constexpr ranges::borrowed_iterator_t<R> upper_bound( R&& r, const T& value, Comp comp = {}, Proj proj = {} );				(自 C++26)

1) 返回一个指向范围[first, last)中第一个大于value的元素的迭代器，如果未找到这样的元素，则返回last。范围[first, last)必须根据表达式或!comp(value, element)进行分区，即所有表达式为true的元素必须位于所有表达式为false的元素之前。完全排序的范围满足此条件。

2) 与(1)相同，但使用r作为源范围，就好像使用ranges::begin(r)作为first，并使用ranges::end(r)作为last。

此页面上描述的类似函数的实体是niebloids，即

调用它们时不能指定显式模板参数列表。
它们都不可见于参数依赖查找。
当它们中的任何一个通过正常非限定查找作为函数调用运算符左侧的名称找到时，参数依赖查找将被禁止。

在实践中，它们可以实现为函数对象，或者使用特殊的编译器扩展。

[edit] 参数

first, last	-	定义要检查的部分有序范围的迭代器-哨兵
r	-	要检查的部分有序范围
value	-	与元素进行比较的值
pred	-	要应用于投影元素的谓词
proj	-	要应用于元素的投影

[edit] 返回值

指向第一个大于value的元素的迭代器，如果未找到这样的元素，则返回last。

[edit] 复杂度

比较和投影应用的次数在first和last之间的距离的对数内（最多 $log 2 (last - first) + O(1)$ 次比较和投影应用）。但是，对于不建模random_access_iterator的迭代器，迭代器增量的次数是线性的。

[edit] 可能的实现

struct upper_bound_fn
{
    template<std::forward_iterator I, std::sentinel_for<I> S,
             class Proj = std::identity, class T = std::projected_value_t<I, Proj>,
             std::indirect_strict_weak_order
                 <const T*, std::projected<I, Proj>> Comp = ranges::less>
    constexpr I operator()(I first, S last, const T& value,
                           Comp comp = {}, Proj proj = {}) const
    {
        I it;
        std::iter_difference_t<I> count, step;
        count = ranges::distance(first, last);
 
        while (count > 0)
        {
            it = first; 
            step = count / 2;
            ranges::advance(it, step, last);
            if (!comp(value, std::invoke(proj, *it)))
            {
                first = ++it;
                count -= step + 1;
            }
            else
                count = step;
        }
        return first;
    }
 
    template<ranges::forward_range R, class Proj = std::identity,
             class T = std::projected_value_t<ranges::iterator_t<R>, Proj>,
             std::indirect_strict_weak_order
                 <const T*, std::projected<ranges::iterator_t<R>,
                                           Proj>> Comp = ranges::less>
    constexpr ranges::borrowed_iterator_t<R>
        operator()(R&& r, const T& value, Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r), value,
                       std::ref(comp), std::ref(proj));
    }
};
 
inline constexpr upper_bound_fn upper_bound;

[edit] 注意事项

功能测试宏	值	Std	功能
`__cpp_lib_algorithm_default_value_type`	202403	(C++26)	算法的列表初始化 (1,2)

[edit] 示例

运行此代码

#include <algorithm>
#include <cassert>
#include <complex>
#include <iostream>
#include <iterator>
#include <vector>
 
int main()
{
    namespace ranges = std::ranges;
 
    std::vector<int> data{1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6};
 
    {
        auto lower = ranges::lower_bound(data.begin(), data.end(), 4);
        auto upper = ranges::upper_bound(data.begin(), data.end(), 4);
 
        ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
        std::cout << '\n';
    }
    {
        auto lower = ranges::lower_bound(data, 3);
        auto upper = ranges::upper_bound(data, 3);
 
        ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
        std::cout << '\n';
    }
 
    using CD = std::complex<double>;
    std::vector<CD> nums{{1, 0}, {2, 2}, {2, 1}, {3, 0}, {3, 1}};
    auto cmpz = [](CD x, CD y) { return x.real() < y.real(); };
    #ifdef __cpp_lib_algorithm_default_value_type
        auto it = ranges::upper_bound(nums, {2, 0}, cmpz);
    #else
        auto it = ranges::upper_bound(nums, CD{2, 0}, cmpz);
    #endif
    assert((*it == CD{3, 0}));
}

输出

4 4 4 
3 3 3 3

[edit] 另请参阅

ranges::equal_range (C++20)	返回匹配特定键的元素范围 (niebloid)[edit]
ranges::lower_bound (C++20)	返回指向第一个不小于给定值的元素的迭代器 (niebloid)[edit]
ranges::partition (C++20)	将元素范围划分为两组 (niebloid)[edit]
upper_bound	返回指向第一个大于某个值的元素的迭代器 (函数模板) [edit]

编译器支持
独立和宿主
语言
标准库
标准库头文件
命名要求
功能测试宏 (C++20)
语言支持库
概念库 (C++20)
元编程库 (C++11)
诊断库
通用实用程序库
字符串库
容器库
迭代器库
范围库 (C++20)
算法库
数值库
本地化库
输入/输出库
文件系统库 (C++17)
正则表达式库 (C++11)
并发支持库 (C++11)
执行支持库 (C++26)
技术规范
符号索引
外部库

cppreference.com

命名空间

变体

视图

操作