std::equal_range() 算法

自 C++20 起

// (1)
template< class ForwardIt, class T >
constexpr std::pair<ForwardIt, ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value );

// (2)
template< class ForwardIt, class T, class Compare >
constexpr std::pair<ForwardIt, ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value, Compare comp );

直到 C++20

// (1)
template< class ForwardIt, class T >
std::pair<ForwardIt, ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value );

// (2)
template< class ForwardIt, class T, class Compare >
std::pair<ForwardIt, ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value, Compare comp );

返回在范围 [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

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

返回的视图由两个迭代器构造而成：

1. 指向第一个不小于 value 的元素。
2. 指向第一个大于 value 的元素。

第一个迭代器可以通过 std::ranges::lower_bound() 获得，第二个迭代器可以通过 std::ranges::upper_bound() 获得。

• (1) 使用 operator< 比较元素。
• (2) 使用给定的比较函数 comp。

参数

first last	要检查的部分有序范围。
值	用于比较元素的 `value`。
comp	比较函数对象（即满足 Compare 要求的对象）。比较函数的签名应等同于以下内容： bool cmp(const Type1 &a, const Type2 &b); 签名不需要有 `const&`，但不得修改参数。 必须接受 Type 和 Type2（可能是 const）的所有值，无论值类别如何（因此不允许使用 Type1&，除非对于 Type1 移动等同于复制，否则也不允许使用 Type1 (C++11 起)） `Type1` 和 `Type2` 类型必须是 `RandomIt` 类型的对象可以隐式转换为它们两者的类型。

类型要求

ForwardIt	LegacyForwardIterator
Compare	BinaryPredicate

`Compare` 不要求满足 Compare。

返回值

一个包含定义所需范围的迭代器对的 std::pair

1. 指向第一个不小于 value 的元素。
2. 指向第一个大于 value 的元素。

如果没有元素不小于 value，则 last 作为第一个元素返回。
同样，如果没有元素大于 value，则 last 作为第二个元素返回。

复杂度

执行的比较次数与 first 和 last 之间的距离呈对数关系（最多 `log^2(last - first) + O(1)` 次比较）。

然而，对于非 LegacyRandomAccessIterators，迭代器增量次数是线性的。

值得注意的是，std::map、std::multimap、std::set 和 std::multiset 的迭代器不是随机访问的，因此应优先使用它们的成员 equal_range() 函数。

异常

(无)

可能的实现

equal_range (1)

template<class ForwardIt, class T>
std::pair<ForwardIt, ForwardIt>
    equal_range(ForwardIt first, ForwardIt last, const T& value)
{
    return std::make_pair(std::lower_bound(first, last, value),
                          std::upper_bound(first, last, value));
}

equal_range (2)

template<class ForwardIt, class T, class Compare>
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));
}

示例

Main.cpp

#include <algorithm>
#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 i = p.first; i != p.second; ++i)
        std::cout << i->name << ' ';

    std::cout << "\n" "Using heterogeneous comparison: ";
    const auto p2 = std::equal_range(vec.begin(), vec.end(), 2, Comp{});

    for (auto i = p2.first; i != p2.second; ++i)
        std::cout << i->name << ' ';
}

输出

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