std::equal_range

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

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

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

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

Возвращает диапазон, содержащий все элементы, эквивалентные value в диапазоне [first, last).

Диапазон [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.

Полностью отсортированный диапазон удовлетворяет этим критериям.

Возвращаемый диапазон определяется двумя итераторами, один из которых указывает на первый элемент, который не меньше value, а другой — на первый элемент, больший value. Первый итератор можно альтернативно получить с помощью std::lower_bound(), второй — с помощью std::upper_bound().

Первый вариант использует оператор < для сравнения элементов, второй вариант использует заданную функцию сравнения comp.

Параметры

Возвращаемое значение

A std::pair , содержащий пару итераторов, определяющих требуемый диапазон. Первый указывает на первый элемент, который не меньше value, а второй — на первый элемент, больший value.

Если нет элементов, не меньших value, last возвращается в качестве первого элемента. Аналогично, если нет элементов, больших value, last возвращается в качестве второго элемента.

Сложность

Количество выполненных сравнений логарифмично по отношению к расстоянию между first и last (не более 2 * log₂(last - first) + O(1) сравнений). Однако для не-LegacyRandomAccessIterators количество инкрементов итераторов линейно. Отметим, что std::set и std::multiset итераторы не являются случайным доступом, и поэтому предпочтительнее использовать их члены std::set::equal_range (соответственно std::multiset::equal_range).

Возможная реализация

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

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

Пример

#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 << ' ';
    std::cout << '\n';
}

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

Отчеты об ошибках

Следующие отчёты об ошибках, меняющие поведение, были применены ретроактивно к ранее опубликованным стандартам C++.

1. Применение equal_range к диапазону из одного элемента требует 2 сравнений, но согласно требованиям к сложности допускается не более 1 сравнения.

См. также