命名空间
变体
操作

std::equal_range

来自 cppreference.cn
< cpp‎ | algorithm
 
C++
 
算法库
受约束算法和范围上的算法 (C++20)
受约束算法，例如 ranges::copy, ranges::sort, ...
执行策略 (C++17)
排序和相关操作
分区操作
排序操作
二分搜索操作
(在已分区的范围上)
equal_range
集合操作 (在已排序的范围上)
合并操作 (在已排序的范围上)
堆操作
最小值/最大值操作
(C++11)
(C++17)
字典序比较操作
(C++20)
排列操作
C 库
数值操作
未初始化内存上的操作
 
定义于头文件 <algorithm>
(1)
template< class ForwardIt, class T >

std::pair<ForwardIt, ForwardIt>

    equal_range( ForwardIt first, ForwardIt last, const T& value );
 (constexpr since C++20)
(until C++26)
template< class ForwardIt, class T = typename std::iterator_traits

                                         <ForwardIt>::value_type >
constexpr std::pair<ForwardIt, ForwardIt>

    equal_range( ForwardIt first, ForwardIt last, const T& value );
 (since C++26)
(2)
template< class ForwardIt, class T, class Compare >

std::pair<ForwardIt, ForwardIt>
    equal_range( ForwardIt first, ForwardIt last,

                 const T& value, Compare comp );
 (constexpr since C++20)
(until C++26)
template< class ForwardIt, class T = typename std::iterator_traits

                                         <ForwardIt>::value_type,
          class Compare >
constexpr std::pair<ForwardIt, ForwardIt>
    equal_range( ForwardIt first, ForwardIt last,

                 const T& value, Compare comp );
 (since C++26)

返回一个范围，其中包含已分区范围 [first, last) 中所有等价于 value 的元素。

1) 等价性使用 operator< 检查

返回 std::lower_bound(first, last, value) 和 std::upper_bound(first, last, value) 的结果。

如果满足以下任何条件，则行为未定义

  • 对于 [first, last) 的任何元素 elem，bool(elem < value) 不意味着 !bool(value < elem)。
  • [first, last) 的元素 elem 没有关于表达式 bool(elem < value) 和 !bool(value < elem) 进行分区。
 (until C++20)

等价于 std::equal_range(first, last, value, std::less{})。

 (since C++20)
2) 等价性使用 comp 检查
返回 std::lower_bound(first, last, value, comp) 和 std::upper_bound(first, last, value, comp) 的结果。
如果满足以下任何条件，则行为未定义
  • 对于 [first, last) 的任何元素 elem，bool(comp(elem, value)) 不意味着 !bool(comp(value, elem))。
  • [first, last) 的元素 elem 没有关于表达式 bool(comp(elem, value)) 和 !bool(comp(value, elem)) 进行分区。

内容

[编辑] 参数

first, last - 定义要检查的元素范围的分区迭代器对
value - 要与之比较元素的的值
comp - 二元谓词，如果第一个参数在第二个参数之前排序，则返回 ​true。

谓词函数的签名应等效于以下内容

 bool pred(const Type1 &a, const Type2 &b);

虽然签名不需要具有 const &，但该函数不得修改传递给它的对象，并且必须能够接受类型为（可能是 const）Type1 和 Type2 的所有值，而与值类别无关（因此，不允许使用 Type1 &，也不允许使用 Type1，除非对于 Type1，移动等同于复制(自 C++11 起)）。
类型 Type1 和 Type2 必须是这样的：类型为 T 的对象可以隐式转换为 Type1 和 Type2，并且类型为 ForwardIt 的对象可以被解引用，然后隐式转换为 Type1 和 Type2。 ​

类型要求
-
ForwardIt 必须满足 LegacyForwardIterator 的要求。
-
Compare 必须满足 BinaryPredicate 的要求。它不需要满足 Compare。

[编辑] 返回值

一个 std::pair，包含一对迭代器，其中

  • first 是指向范围 [first, last) 中第一个不先于 value 排序的元素的迭代器（如果未找到此类元素，则为 last），并且
  • second 是指向范围 [first, last) 中第一个在 value 之后排序的元素的迭代器（如果未找到此类元素，则为 last）。

[编辑] 复杂度

给定 N 作为 std::distance(first, last)

1) 最多 2log2(N)+O(1) 次与 value 的比较，使用 operator<(直到 C++20)std::less{}(自 C++20 起)。
2) 最多 2log2(N)+O(1) 次比较器 comp 的应用。

但是，如果 ForwardIt 不是 LegacyRandomAccessIterator，则迭代器递增的次数与 N 成线性关系。 值得注意的是，std::set 和 std::multiset 迭代器不是随机访问的，因此应优先使用它们的成员函数 std::set::equal_range （或 std::multiset::equal_range）。

[编辑] 注意

尽管 std::equal_range 仅要求 [first, last) 被分区，但此算法通常用于 [first, last) 已排序的情况，以便二分搜索对于任何 value 都有效。

除了 std::lower_bound 和 std::upper_bound 的要求之外，std::equal_range 还要求 operator< 或 comp 是不对称的（即，a < b 和 b < a 始终具有不同的结果）。

因此，二分搜索的中间结果可以由 std::lower_bound 和 std::upper_bound 共享。 例如，std::lower_bound 调用的结果可以用作 std::upper_bound 调用中 first 参数。

特性测试 宏 值 Std 特性
__cpp_lib_algorithm_default_value_type 202403 (C++26) 列表初始化 用于算法 (1,2)

[编辑] 可能的实现

equal_range (1) 
template<class ForwardIt,
         class T = typename std::iterator_traits<ForwardIt>::value_type>
constexpr std::pair<ForwardIt, ForwardIt> 
    equal_range(ForwardIt first, ForwardIt last, const T& value)
{
    return std::equal_range(first, last, value, std::less{});
}
equal_range (2) 
template<class ForwardIt,
         class T = typename std::iterator_traits<ForwardIt>::value_type,
         class Compare>
constexpr std::pair<ForwardIt, ForwardIt>
    equal_range(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    return std::make_pair(std::lower_bound(first, last, value, comp),
                          std::upper_bound(first, last, value, comp));
}

[编辑] 示例

运行此代码
#include <algorithm>
#include <complex>
#include <iostream>
#include <vector>
 
struct S
{
    int number;
    char name;
    // note: name is ignored by this comparison operator
    bool operator<(const S& s) const { return number < s.number; }
};
 
struct Comp
{
    bool operator()(const S& s, int i) const { return s.number < i; }
    bool operator()(int i, const S& s) const { return i < s.number; }
};
 
int main()
{
    // note: not ordered, only partitioned w.r.t. S defined below
    const std::vector<S> vec{{1, 'A'}, {2, 'B'}, {2, 'C'},
                             {2, 'D'}, {4, 'G'}, {3, 'F'}};
    const S value{2, '?'};
 
    std::cout << "Compare using S::operator<(): ";
    const auto p = std::equal_range(vec.begin(), vec.end(), value);
 
    for (auto it = p.first; it != p.second; ++it)
        std::cout << it->name << ' ';
    std::cout << '\n';
 
    std::cout << "Using heterogeneous comparison: ";
    const auto p2 = std::equal_range(vec.begin(), vec.end(), 2, Comp{});
 
    for (auto it = p2.first; it != p2.second; ++it)
        std::cout << it->name << ' ';
    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 p3 = std::equal_range(nums.cbegin(), nums.cend(), {2, 0}, cmpz);
    #else
        auto p3 = std::equal_range(nums.cbegin(), nums.cend(), CD{2, 0}, cmpz);
    #endif
 
    for (auto it = p3.first; it != p3.second; ++it)
        std::cout << *it << ' ';
    std::cout << '\n';
}

输出

Compare using S::operator<(): B C D 
Using heterogeneous comparison: B C D
(2,2) (2, 1)

[编辑] 缺陷报告

以下行为变更缺陷报告已追溯应用于先前发布的 C++ 标准。

DR 应用于 已发布的行为 正确的行为
LWG 270 C++98 Compare 需要满足 Compare，并且 T 是必需的
为 LessThanComparable (需要严格弱序)		 仅需要分区；
允许异构比较
LWG 384 C++98 最多允许 2log2(N)+1 次比较
是不可实现的[1]		 更正为 2log2(N)+O(1)
  1. ↑ 将 equal_range 应用于单元素范围需要 2 次比较，但复杂性要求最多允许 1 次比较。

[编辑] 参见

 返回指向第一个不小于给定值的元素的迭代器
(函数模板) [编辑]
 返回指向第一个大于某个值的元素的迭代器
(函数模板) [编辑]
 确定元素是否存在于部分排序的范围中
(函数模板) [编辑]
 将元素范围划分为两组
(函数模板) [编辑]
 确定两组元素是否相同
(函数模板) [编辑]
 返回与特定键匹配的元素范围
(std::set<Key,Compare,Allocator> 的公共成员函数) [编辑]
 返回与特定键匹配的元素范围
(std::multiset<Key,Compare,Allocator> 的公共成员函数) [编辑]
(C++20)
 返回与特定键匹配的元素范围
(算法函数对象)[编辑]
Retrieved from "https://cppreference.cn/mwiki/index.php?title=cpp/algorithm/equal_range&oldid=180598"