std::ranges::partition

template< std::permutable I, std::sentinel_for<I> S, class Proj = std::identity,
          std::indirect_unary_predicate<std::projected<I, Proj>> Pred >
constexpr ranges::subrange<I>
    partition( I first, S last, Pred pred, Proj proj = {} );

template< ranges::forward_range R, class Proj = std::identity,
          std::indirect_unary_predicate<
              std::projected<ranges::iterator_t<R>, Proj>> Pred >
requires std::permutable<ranges::iterator_t<R>>
constexpr ranges::borrowed_subrange_t<R>
    partition( R&& r, Pred pred, Proj proj = {} );

Die auf dieser Seite beschriebenen funktionsähnlichen 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 irgendeine von ihnen durch normale unqualifizierte Namenssuche als Name links vom Funktionsaufrufoperator gefunden wird, wird argumentabhängige Namenssuche unterdrückt.

Parameter

Rückgabewert

Ein Teilbereich, der mit einem Iterator zum ersten Element der zweiten Gruppe beginnt und mit einem Iterator endet, der gleich last ist. (2) gibt std::ranges::dangling zurück, falls r ein R-Wert eines Nicht- borrowed_range -Typs ist.

Komplexität

Gegeben N = ranges:: distance ( first, last ) , genau N Anwendungen des Prädikats und der Projektion. Höchstens N / 2 Vertauschungen, falls I das Konzept ranges::bidirectional_iterator modelliert, andernfalls höchstens N Vertauschungen.

Mögliche Implementierung

struct partition_fn
{
    template<std::permutable I, std::sentinel_for<I> S, class Proj = std::identity,
             std::indirect_unary_predicate<std::projected<I, Proj>> Pred>
    constexpr ranges::subrange<I>
        operator()(I first, S last, Pred pred, Proj proj = {}) const
    {
        first = ranges::find_if_not(first, last, std::ref(pred), std::ref(proj));
        if (first == last)
            return {first, first};
        for (auto i = ranges::next(first); i != last; ++i)
        {
            if (std::invoke(pred, std::invoke(proj, *i)))
            {
                ranges::iter_swap(i, first);
                ++first;
            }
        }
        return {std::move(first), std::move(last)};
    }
    template<ranges::forward_range R, class Proj = std::identity,
             std::indirect_unary_predicate<
                 std::projected<ranges::iterator_t<R>, Proj>> Pred>
    requires std::permutable<ranges::iterator_t<R>>
    constexpr ranges::borrowed_subrange_t<R>
        operator()(R&& r, Pred pred, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r),
                       std::ref(pred), std::ref(proj));
    }
};
inline constexpr partition_fn partition;

Beispiel

#include <algorithm>
#include <forward_list>
#include <functional>
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>
namespace ranges = std::ranges;
template<class I, std::sentinel_for<I> S, class Cmp = ranges::less>
requires std::sortable<I, Cmp>
void quicksort(I first, S last, Cmp cmp = Cmp {})
{
    using reference = std::iter_reference_t<I>;
    if (first == last)
        return;
    auto size = ranges::distance(first, last);
    auto pivot = ranges::next(first, size - 1);
    ranges::iter_swap(pivot, ranges::next(first, size / 2));
    auto tail = ranges::partition(first, pivot, [=](reference em)
    {
        return std::invoke(cmp, em, *pivot); // em < pivot
    });
    ranges::iter_swap(pivot, tail.begin());
    quicksort(first, tail.begin(), std::ref(cmp));
    quicksort(ranges::next(tail.begin()), last, std::ref(cmp));
}
int main()
{
    std::ostream_iterator<int> cout {std::cout, " "};
    std::vector<int> v {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::cout << "Ursprünglicher Vektor:  \t";
    ranges::copy(v, cout);
    auto tail = ranges::Partition(v, [](int i) { return i % 2 == 0; });
    std::cout << "\nPartitioned vector: \t";
    ranges::copy(ranges::begin(v), ranges::begin(tail), cout);
    std::cout << "│ ";
    ranges::copy(tail, cout);
    std::forward_list<int> fl {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92};
    std::cout << "\nUnsortierte Liste: \t\t";
    ranges::copy(fl, cout);
    quicksort(ranges::begin(fl), ranges::end(fl), ranges::greater {});
    std::cout << "\nQuick-sortierte Liste: \t";
    ranges::copy(fl, cout);
    std::cout << '\n';
}

Ursprünglicher Vektor:  0 1 2 3 4 5 6 7 8 9
Partitionierter Vektor: 0 8 2 6 4 │ 5 3 7 1 9
Unsortierte Liste:      1 30 -4 3 5 -4 1 6 -8 2 -5 64 1 92
Quick-sortierte Liste:  92 64 30 6 5 3 2 1 1 1 -4 -4 -5 -8

Siehe auch