std::equal_range

在头文件中定义 `<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)) 被划分。

[编辑] 参数

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

[编辑] 复杂度

假设 $\scriptsize N$ $N$ 为 std::distance(first, last)

1) 使用 operator<(直到 C++20)std::less{}(自 C++20 起) 与 value 进行最多

2log 2 (N)+O(1)

次比较。

2) 对比较器 comp 进行最多

2log 2 (N)+O(1)

次应用。

但是，如果 ForwardIt 不是 LegacyRandomAccessIterator，则迭代器增量的次数与 $\scriptsize N$ $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	允许最多进行 $\scriptsize 2\log_{2}(N)+1$ $2log 2 (N)+1$ 次比较这是不可实现的^[1]	已修正为 $\scriptsize 2\log_{2}(N)+O(1)$ $2log 2 (N)+O(1)$

↑ 对单元素范围应用 equal_range 需要 2 次比较，但复杂度要求最多允许 1 次比较。

[编辑] 参见

lower_bound	返回指向第一个不小于给定值的元素的迭代器 (函数模板) [编辑]
upper_bound	返回指向第一个大于某个值的元素的迭代器 (函数模板) [编辑]
binary_search	确定某个元素是否存在于部分有序范围内 (函数模板) [编辑]
partition	将一个元素范围划分为两组 (函数模板) [编辑]
equal	确定两个元素集是否相同 (函数模板) [编辑]
equal_range	返回与特定键匹配的元素范围 (`std::set<Key,Compare,Allocator>` 的公有成员函数) [编辑]
equal_range	返回与特定键匹配的元素范围 (`std::multiset<Key,Compare,Allocator>` 的公有成员函数) [编辑]
ranges::equal_range (C++20)	返回与特定键匹配的元素范围 (niebloid)[编辑]

[1] 对单元素范围应用 equal_range 需要 2 次比较，但复杂度要求最多允许 1 次比较。

[1]

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

cppreference.com

命名空间

变体

视图

操作