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

Der Bereich [first, last) muss mindestens teilweise in Bezug auf value geordnet sein, d.h. er muss alle folgenden Anforderungen erfüllen:

• partitioniert in Bezug auf element < value oder comp(element, value) (d.h. alle Elemente, für die der Ausdruck true ist, stehen vor allen Elementen, für die der Ausdruck false ist).
• partitioniert in Bezug auf !(value < element) oder !comp(value, element).
• für alle Elemente, wenn element < value oder comp(element, value) true ist, dann ist !(value < element) oder !comp(value, element) auch true.

Ein vollständig sortierter Bereich erfüllt diese Kriterien.

Die zurückgegebene Ansicht wird aus zwei Iteratoren konstruiert, einer zeigt auf das erste Element, das nicht kleiner als value ist, und der andere auf das erste Element, das größer als value ist. Der erste Iterator kann alternativ mit std::ranges::lower_bound() erhalten werden, der zweite mit std::ranges::upper_bound().

Die auf dieser Seite beschriebenen funktionsartigen Entitäten sind Algorithmus-Funktionsobjekte (informell als Niebloids bekannt), das heißt:

• Explizite Vorlagenargumentlisten können beim Aufruf keiner von ihnen angegeben werden.
• Keine von ihnen ist für argumentabhängige Namenssuche sichtbar.
• Wenn einer von ihnen durch normale unqualifizierte Namenssuche als Name links vom Funktionsaufrufoperator gefunden wird, wird argumentabhängige Namenssuche unterbunden.

Parameter

Rückgabewert

std::ranges::subrange enthält ein Paar von Iteratoren, die den gewünschten Bereich definieren, der erste zeigt auf das erste Element, das nicht kleiner als value ist, und der zweite auf das erste Element, das größer als value ist.

Wenn es keine Elemente gibt, die nicht kleiner als value sind, wird der letzte Iterator (Iterator, der gleich last oder ranges::end(r) ist) als erstes Element zurückgegeben. Wenn es keine Elemente gibt, die größer als value sind, wird der letzte Iterator als zweites Element zurückgegeben.

Komplexität

Die Anzahl der durchgeführten Vergleiche ist logarithmisch zur Entfernung zwischen first und last (höchstens 2 * log2(last - first) + O(1) Vergleiche). Für einen Iterator, der kein random_access_iterator modelliert, ist die Anzahl der Iteratorinkremente linear.

Mögliche Implementierung

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;

Anmerkungen

Beispiel

#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)

Siehe auch