std::ranges::equal_range

< cpp‎ | algorithm‎ | ranges
 
C++
 
算法库
有制约算法及范围上的算法 (C++20)
有制约算法： std::ranges::copy, std::ranges::sort, ...
执行策略 (C++17)
不修改序列的操作
(C++11)(C++11)(C++11)
(C++17)
修改序列的操作
未初始化存储上的操作
划分操作
排序操作
(C++11)
(C++11)
二分搜索操作
集合操作（在已排序范围上）
堆操作
(C++11)
(C++11)
最小/最大操作
(C++11)
(C++11)
(C++17)

排列
数值运算
C 库
 
有制约算法
不修改序列的操作
修改序列的操作
未初始化存储上的操作
划分操作
排序操作
二分搜索操作
ranges::equal_range
集合操作（在已排序范围上）
堆操作
最小/最大操作
排列
 
定义于头文件 <algorithm>
调用签名
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 ranges::subrange<I>

equal_range(I first, S last, const T& value, Comp comp = {}, Proj proj = {});
 (1) (C++20 起)
template< std::forward_range R, class T, class Proj = std::identity,

          std::indirect_strict_weak_order<
              const T*,
              std::projected<std::iterator_t<R>, Proj>> Comp = ranges::less >
constexpr ranges::borrowed_subrange_t<R>

equal_range(R&& r, const T& value, Comp comp = {}, Proj proj = {});
 (2) (C++20 起)
1) 返回范围 [first, last) 中含有所有等价于 value 的元素的范围的视图。

范围 [first, last) 必须至少相对于 value 有序，即它必须满足下列所有要求：

  • 已相对 element < value 或 comp(element, value) 划分（即所有令该表达式为 true 的元素必须前趋所有令此表达式为 false 的元素）
  • 已相对 !(value < element) 或 !comp(value, element) 划分
  • 对于所有元素，若 element < value 或 comp(element, value) 为 true ，则 !(value < element) 或 !comp(value, element) 亦为 true

完全排序的范围满足这些判别标准。

返回的视图从二个迭代器构造，第一个指向首个不小于 value 的元素，而第二个指向首个大于 value 的元素。可替而用 std::ranges::lower_bound() 获得第一迭代器，用 std::ranges::upper_bound() 获得第二迭代器。

2) 同 (1) ，但以 r 为源范围，如同以 ranges::begin(r) 为 first 并以 ranges::end(r) 为 last 。

此页面上描述的仿函数实体是 niebloid ，即：

实际上，它们能以函数对象，或以某些特殊编译器扩展实现。

参数

first, last - 要检验的元素范围
r - 要检验的元素范围
value - 要比较的元素
comp - 第一参数是否小于（即先序于）第二个
proj - 应用到元素的投影

返回值

含有定义所需范围的迭代器对的 std::ranges::subrange ，第一迭代器指向首个不小于 value 的元素而第二迭代器指向首个大于 value 的元素。

若无元素小于 value ，则返回尾迭代器（等于 last 或 ranges::end(r) 的迭代器）作为第一迭代器。类似地若无元素大于 value ，则返回尾迭代器作为第二迭代器。

复杂度

进行的比较次数与 first 与 last 间的距离成对数（至多 2 * log
2(last - first) + O(1) 次比较）。然而，对于不实现 random_access_iterator 的迭代器，迭代器自增次数为线性。

可能的实现

struct equal_range_fn {
    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 ranges::subrange<I>
    operator()(I first, S last, const T& value, Comp comp = {}, Proj proj = {}) const
    {
        return ranges::subrange(
            ranges::lower_bound(first, last, value, std::ref(comp), std::ref(proj)),
            ranges::upper_bound(first, last, value, std::ref(comp), std::ref(proj)));
    }
 
    template< ranges::forward_range R, class T, class Proj = std::identity,
              std::indirect_strict_weak_order<
                  const T*,
                  std::projected<std::ranges::iterator_t<R>, Proj>> Comp = ranges::less >
    constexpr ranges::borrowed_subrange_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 equal_range_fn equal_range;

示例

运行此代码
#include <algorithm>
#include <compare>
#include <vector>
#include <iostream>
 
struct S
{
    int number;
    char name;
    // 注：这些比较运算符忽略名称
    friend bool operator==  ( const S s1, const S s2 ) { return s1.number == s2.number; }
    friend auto operator<=> ( const S s1, const S s2 ) { return s1.number <=> s2.number; }
};
 
int main()
{
    // 注：非有序，仅按照定义如下的 S 划分
    std::vector<S> vec = { {1,'A'}, {2,'B'}, {2,'C'}, {2,'D'}, {4, 'D'}, {4,'G'}, {3,'F'} };
 
    S value = {2, '?'};
 
    namespace ranges = std::ranges;
 
    {
        auto p = ranges::equal_range(vec, value);
 
        for ( auto i : p )
            std::cout << i.name << ' ';
    }
    {
        auto p = ranges::equal_range(vec.begin(), vec.end(), value);
 
        for ( auto i = p.begin(); i != p.end(); ++i )
            std::cout << i->name << ' ';
    }
 
    std::cout << '\n';
 
    {
        auto p = ranges::equal_range(vec, 'D', ranges::less{}, &S::name);
 
        for ( auto i : p )
            std::cout << i.name << ' ';
    }
    {
        auto p = ranges::equal_range(vec.begin(),vec.end(), 'D', ranges::less{}, &S::name);
 
        for ( auto i = p.begin(); i != p.end(); ++i )
            std::cout << i->name << ' ';
    }
}

输出： 

B C D B C D
D D D D


参阅

(C++20)
 返回指向首个不小于给定值的元素的迭代器
(niebloid)
(C++20)
 返回指向首个大于某值的元素的迭代器
(niebloid)
(C++20)
 确定元素是否存在于某范围中
(niebloid)
(C++20)
 将范围中的元素分为二组
(niebloid)
返回匹配特定键值的元素范围
(函数模板)