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) (constexpr начиная с C++20)
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) (constexpr начиная с C++20)
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`, если первый аргумент упорядочен перед вторым. Сигнатура функции-предиката должна быть эквивалентна следующей: boolpred(constType1&a,constType2&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) Не более \(\scriptsize 2\log_{2}(N)+O(1)\)2log₂(N)+O(1) сравнений с value с использованием operator<(до C++20)std::less{}(начиная с C++20).

2) Не более \(\scriptsize 2\log_{2}(N)+O(1)\)2log₂(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)); }

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₂(N)+1 сравнений, что невозможно реализовать^[1]	исправлено на \(\scriptsize 2\log_{2}(N)+O(1)\)2log₂(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)	находит с помощью двоичного поиска диапазон элементов, соответствующих заданному значению (функциональный объект алгоритма)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/equal_range