命名空间
变体
操作

std::equal_range

来自 cppreference.cn
< cpp‎ | 算法
 
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 );
 (C++20 起为 constexpr)
（直到 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 );
 (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 );
 (C++20 起为 constexpr)
（直到 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 );
 (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) 分区。
 (C++20 前)

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

 (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)) 分区。

目录

[edit] 参数

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

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

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

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

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

[edit] 返回值

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

  • first 是指向范围 [first, last) 中第一个不早于 value 的元素的迭代器（如果未找到此类元素，则为 last），以及
  • second 是指向范围 [first, last) 中第一个晚于 value 的元素的迭代器（如果未找到此类元素，则为 last）。

[edit] 复杂度

给定 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）。

[edit] 注意

尽管 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 调用的结果可以作为 first 参数用于 std::upper_bound 调用。

特性测试宏 值 标准 特性
__cpp_lib_algorithm_default_value_type 202403 (C++26) 算法的列表初始化 (1,2)

[edit] 可能的实现

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));
}

[edit] 示例

运行此代码
#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)

[edit] 缺陷报告

下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。

缺陷报告 应用于 发布时的行为 正确的行为
LWG 270 C++98 Compare 需要满足 比较，且 T 需要
是 可小于比较的（需要严格弱序）		 只需要分区；
允许异构比较
LWG 384 C++98 最多允许 2log2(N)+1 次比较
这是无法实现的[1]		 修正为 2log2(N)+O(1)
  1. ↑ 将 equal_range 应用于单个元素的范围需要 2 次比较，但复杂度要求最多只允许 1 次比较。

[edit] 参阅

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