std::equal_range

定义于头文件 `<algorithm>`
template< class ForwardIt, class T > std::pair<ForwardIt, ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value );	(1)	(C++26 前) (自 C++20 起为 constexpr)
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 );	(1)		(自 C++26 起)
template< class ForwardIt, class T, class Compare > std::pair<ForwardIt, ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value, Compare comp );	(2)	(C++26 前) (自 C++20 起为 constexpr)
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 );	(2)		(自 C++26 起)

返回一个范围，包含所有与 value 等价且在划分范围 [first, last) 中的元素。

1) 等价性使用 operator< 检查：

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

若满足以下任何条件，则行为未定义：

对于任何元素 elem 在 [first, last) 中，bool(elem < value) 不蕴含 !bool(value < elem)。
元素 elem 在 [first, last) 中未按表达式划分为 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) 的结果。

若满足以下任何条件，则行为未定义：

对于任何元素 elem 在 [first, last) 中，bool(comp(elem, value)) 不蕴含 !bool(comp(value, elem))。
元素 elem 在 [first, last) 中未按表达式划分为 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) 最多

2log 2 (N)+O(1)

次比较与 value 使用 operator<(C++20 前)std::less{}(自 C++20 起)。

2) 最多

2log 2 (N)+O(1)

次比较器的应用 comp。

然而，如果 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 调用的结果用作 first 在 std::upper_bound 调用中的参数。

功能特性测试宏	值	标准	特性
`__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	用二分搜索查找首个不小于给定值的元素（函数模板 & 算法函数对象）
ranges::lower_bound (C++20)	用二分搜索查找首个不小于给定值的元素（函数模板 & 算法函数对象）
upper_bound	用二分搜索查找首个大于给定值的元素（函数模板 & 算法函数对象）
ranges::upper_bound (C++20)	用二分搜索查找首个大于给定值的元素（函数模板 & 算法函数对象）
binary_search	用二分搜索确定元素是否存在于范围中（函数模板 & 算法函数对象）
ranges::binary_search (C++20)	用二分搜索确定元素是否存在于范围中（函数模板 & 算法函数对象）
partition	将元素范围划分为两组（函数模板 & 算法函数对象）
ranges::partition (C++20)	将元素范围划分为两组（函数模板 & 算法函数对象）
equal	确定两个元素集合是否相同（函数模板 & 算法函数对象）
ranges::equal (C++20)	确定两个元素集合是否相同（函数模板 & 算法函数对象）
equal_range	返回匹配特定键的元素范围（`std::set<Key,Compare,Allocator>` 的公开成员函数）
equal_range	返回匹配特定键的元素范围（`std::multiset<Key,Compare,Allocator>` 的公开成员函数）
ranges::equal_range (C++20)	用二分搜索查找与给定值匹配的元素范围（算法函数对象）

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

[1]

编译器支持
独立环境与托管环境
语言
标准库
标准库头文件
具名要求
功能特性测试宏 (C++20)
语言支持库
概念库 (C++20)
诊断库
内存管理库
元编程库 (C++11)
通用工具库
容器库
迭代器库
范围库 (C++20)
算法库
字符串库
文本处理库
数值库
日期和时间库
输入/输出库
文件系统库 (C++17)
并发支持库 (C++11)
执行控制库 (C++26)
技术规范
符号索引
外部库

zh.cppreference.net

Namespaces

Variants

std::equal_range

目录

参数

返回值

复杂度

注解

可能的实现

示例

缺陷报告

参阅