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`, если первый аргумент упорядочен перед вторым. Сигнатура функции предиката должна быть эквивалентна следующей: `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	возвращает диапазон элементов, соответствующих заданному ключу (public-метод класса `std::set<Key,Compare,Allocator>`)
equal_range	возвращает диапазон элементов, соответствующих заданному ключу (public-метод класса `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)
Технические спецификации
Индекс символов
Внешние библиотеки

ru.cppreference.net

Namespaces

Variants