std::ranges::equal_range

template< std::forward_iterator I, std::sentinel_for<I> S,
          class T, class Proj = std::identity,
          std::indirect_strict_weak_order
              <const T*, std::projected<I, Proj>> Comp = ranges::less >
constexpr ranges::subrange<I> equal_range( I first, S last, const T& value,
                                           Comp comp = {}, Proj proj = {} );

template< std::forward_iterator I, std::sentinel_for<I> S,
          class Proj = std::identity,
          class T = std::projected_value_t<I, Proj>,
          std::indirect_strict_weak_order
              <const T*, std::projected<I, Proj>> Comp = ranges::less >
constexpr ranges::subrange<I> equal_range( I first, S last, const T& value,
                                           Comp comp = {}, Proj proj = {} );

template< ranges::forward_range R,
          class T, class Proj = std::identity,
          std::indirect_strict_weak_order
              <const T*, std::projected<ranges::iterator_t<R>,
                                        Proj>> Comp = ranges::less >
constexpr ranges::borrowed_subrange_t<R>
    equal_range( R&& r, const T& value, Comp comp = {}, Proj proj = {} );

template< ranges::forward_range R,
          class Proj = std::identity,
          class T = std::projected_value_t<ranges::iterator_t<R>, Proj>,
          std::indirect_strict_weak_order
              <const T*, std::projected<ranges::iterator_t<R>,
                                        Proj>> Comp = ranges::less >
constexpr ranges::borrowed_subrange_t<R>
    equal_range( R&& r, const T& value, Comp comp = {}, Proj proj = {} );

El rango [first, last) debe estar al menos parcialmente ordenado con respecto a value, es decir, debe satisfacer todos los siguientes requisitos:

• particionado con respecto a element < value o comp(element, value) (es decir, todos los elementos para los que la expresión es true preceden a todos los elementos para los que la expresión es false).
• particionado con respecto a !(value < element) o !comp(value, element).
• para todos los elementos, si element < value o comp(element, value) es true, entonces !(value < element) o !comp(value, element) también es true.

Un rango completamente ordenado cumple estos criterios.

La vista devuelta se construye a partir de dos iteradores, uno que apunta al primer elemento que es no menor que value y otro que apunta al primer elemento mayor que value. El primer iterador puede obtenerse alternativamente con std::ranges::lower_bound(), el segundo con std::ranges::upper_bound().

Las entidades similares a funciones descritas en esta página son objetos función de algoritmo (informalmente conocidos como niebloids), es decir:

• No se pueden especificar listas explícitas de argumentos de plantilla al llamar a ninguno de ellos.
• Ninguno de ellos es visible mediante búsqueda dependiente de argumentos.
• Cuando alguno de ellos se encuentra mediante búsqueda normal no calificada como el nombre a la izquierda del operador de llamada a función, se inhibe la búsqueda dependiente de argumentos.

Parámetros

Valor de retorno

std::ranges::subrange que contiene un par de iteradores que definen el rango deseado, el primero apunta al primer elemento que es no menor que value y el segundo apunta al primer elemento mayor que value.

Si no hay elementos no menores que value, el último iterador (iterador igual a last o ranges::end(r)) se devuelve como el primer elemento. De manera similar, si no hay elementos mayores que value, el último iterador se devuelve como el segundo elemento.

Complejidad

El número de comparaciones realizadas es logarítmico en la distancia entre first y last (a lo sumo 2 * log2(last - first) + O(1) comparaciones). Sin embargo, para un iterador que no modele random_access_iterator, el número de incrementos de iterador es lineal.

Posible implementación

struct equal_range_fn
{
    template<std::forward_iterator I, std::sentinel_for<I> S,
             class Proj = std::identity, class T = std::projected_value_t<I, Proj>,
             std::indirect_strict_weak_order
                 <const T*, std::projected<I, Proj>> Comp = ranges::less>
    constexpr ranges::subrange<I>
        operator()(I first, S last, const T& value, Comp comp = {}, Proj proj = {}) const
    {
        return ranges::subrange
        (
            ranges::lower_bound(first, last, value, std::ref(comp), std::ref(proj)),
            ranges::upper_bound(first, last, value, std::ref(comp), std::ref(proj))
        );
    }
 
    template<ranges::forward_range R, class Proj = std::identity,
             class T = std::projected_value_t<ranges::iterator_t<R>, Proj>,
             std::indirect_strict_weak_order
                 <const T*, std::projected<ranges::iterator_t<R>,
                                           Proj>> Comp = ranges::less>
    constexpr ranges::borrowed_subrange_t<R>
        operator()(R&& r, const T& value, Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r), value,
                       std::ref(comp), std::ref(proj));
    }
};
 
inline constexpr equal_range_fn equal_range;

Notas

Ejemplo

#include <algorithm>
#include <compare>
#include <complex>
#include <iostream>
#include <vector>

struct S
{
    int number {};
    char name {};
    // note: name is ignored by these comparison operators
    friend bool operator== (const S s1, const S s2) { return s1.number == s2.number; }
    friend auto operator<=>(const S s1, const S s2) { return s1.number <=> s2.number; }
    friend std::ostream& operator<<(std::ostream& os, S o)
    {
        return os << '{' << o.number << ", '" << o.name << "'}";
    }
};

void println(auto rem, const auto& v)
{
    for (std::cout << rem; const auto& e : v)
        std::cout << e << ' ';
    std::cout << '\n';
}

int main()
{
    // note: not ordered, only partitioned w.r.t. S defined below
    std::vector<S> vec
    {
        {1,'A'}, {2,'B'}, {2,'C'}, {2,'D'}, {4, 'D'}, {4,'G'}, {3,'F'}
    };
    
    const S value{2, '?'};
    
    namespace ranges = std::ranges;
    
    auto a = ranges::equal_range(vec, value);
    println("1. ", a);
    
    auto b = ranges::equal_range(vec.begin(), vec.end(), value);
    println("2. ", b);
    
    auto c = ranges::equal_range(vec, 'D', ranges::less {}, &S::name);
    println("3. ", c);
    
    auto d = ranges::equal_range(vec.begin(), vec.end(), 'D', ranges::less {}, &S::name);
    println("4. ", d);

    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 = ranges::equal_range(nums, {2, 0}, cmpz);
    #else
        auto p3 = ranges::equal_range(nums, CD{2, 0}, cmpz);
    #endif
    println("5. ", p3);
}

1. {2, 'B'} {2, 'C'} {2, 'D'}
2. {2, 'B'} {2, 'C'} {2, 'D'}
3. {2, 'D'} {4, 'D'}
4. {2, 'D'} {4, 'D'}
5. (2,2) (2,1)

Véase también