std::ranges:: equal_range

Der Bereich [ first , last ) muss mindestens teilweise geordnet sein in Bezug auf value , 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 gilt: wenn element < value oder comp ( element, value ) true ist, dann ist auch ! ( value < element ) oder ! comp ( value, element ) true .

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

Die zurückgegebene Ansicht wird aus zwei Iteratoren konstruiert, wobei einer auf das erste Element zeigt, das nicht kleiner als value ist, und ein anderer auf das erste Element zeigt, 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 funktionsähnlichen Entitäten sind Algorithm Function Objects (informell bekannt als Niebloids ), das heißt:

• Explizite Template-Argumentlisten können beim Aufruf keiner von ihnen angegeben werden.
• Keiner von ihnen ist sichtbar für argument-dependent lookup .
• Wenn einer von ihnen durch normal unqualified lookup als Name links vom Funktionsaufrufoperator gefunden wird, wird argument-dependent lookup unterdrückt.

Parameter

Rückgabewert

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

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

Komplexität

Die Anzahl der durchgeführten Vergleiche ist logarithmisch im Abstand zwischen first und last (höchstens 2 * log 2 (last - first) + O(1) Vergleiche). Für einen Iterator, der nicht random_access_iterator modelliert, ist die Anzahl der Iterator-Inkremente jedoch 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;

Hinweise

Beispiel

#include <algorithm>
#include <compare>
#include <complex>
#include <iostream>
#include <vector>
struct S
{
    int number {};
    char name {};
    // Hinweis: name wird von diesen Vergleichsoperatoren ignoriert
    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()
{
    // Hinweis: nicht sortiert, nur partitioniert bezüglich unten definiertem S
    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