std::ranges::stable_partition

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

template< ranges::bidirectional_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>>
ranges::borrowed_subrange_t<R>
    stable_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 die argumentabhängige Namenssuche sichtbar.
• Wenn eine von ihnen durch normale unqualifizierte Namenssuche als Name links vom Funktionsaufrufoperator gefunden wird, wird die argumentabhängige Namenssuche unterbunden.

Parameter

Rückgabewert

Komplexität

Gegeben N = ranges:: distance ( first, last ) , beträgt die Komplexität im schlimmsten Fall \(\scriptsize N\cdot\log{(N)}\) N·log(N) Vertauschungen, und nur \(\scriptsize \mathcal{O}(N)\) 𝓞(N) Vertauschungen, falls ein zusätzlicher Speicherpuffer verwendet wird. Genau \(\scriptsize N\) N Anwendungen des Prädikats pred und der Projektion proj .

Hinweise

Diese Funktion versucht, einen temporären Puffer zu allozieren. Falls die Allokation fehlschlägt, wird der weniger effiziente Algorithmus gewählt.

Mögliche Implementierung

Diese Implementierung verwendet keinen zusätzlichen Speicherpuffer und kann daher weniger effizient sein. Siehe auch die Implementierung in MSVC STL und libstdc++ .

struct stable_partition_fn
{
    template<std::bidirectional_iterator I, std::sentinel_for<I> S,
             class Proj = std::identity,
             std::indirect_unary_predicate<std::projected<I, Proj>> Pred>
    requires std::permutable<I>
    constexpr ranges::subrange<I>
        operator()(I first, S last, Pred pred, Proj proj = {}) const
    {
        first = ranges::find_if_not(first, last, pred, proj);
        I mid = first;
        while (mid != last)
        {
            mid = ranges::find_if(mid, last, pred, proj);
            if (mid == last)
                break;
            I last2 = ranges::find_if_not(mid, last, pred, proj);
            ranges::rotate(first, mid, last2);
            first = ranges::next(first, ranges::distance(mid, last2));
            mid = last2;
        }
        return {std::move(first), std::move(mid)};
    }
    template<ranges::bidirectional_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::move(pred), std::move(proj));
    }
};
inline constexpr stable_partition_fn stable_partition {};

Beispiel

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
namespace rng = std::ranges;
template<std::permutable I, std::sentinel_for<I> S>
constexpr void stable_sort(I first, S last)
{
    if (first == last)
        return;
    auto pivot = *rng::next(first, rng::distance(first, last) / 2, last);
    auto left = [pivot](const auto& em) { return em < pivot; };
    auto tail1 = rng::stable_partition(first, last, left);
    auto right = [pivot](const auto& em) { return !(pivot < em); };
    auto tail2 = rng::stable_partition(tail1, right);
    stable_sort(first, tail1.begin());
    stable_sort(tail2.begin(), tail2.end());
}
void print(const auto rem, auto first, auto last, bool end = true)
{
    std::cout << rem;
    for (; first != last; ++first)
        std::cout << *first << ' ';
    std::cout << (end ? "\n" : "");
}
int main()
{
    const auto original = {9, 6, 5, 2, 3, 1, 7, 8};
    std::vector<int> vi {};
    auto even = [](int x) { return 0 == (x % 2); };
    print("Original vector:\t", original.begin(), original.end(), "\n");
    vi = original;
    const auto ret1 = rng::stable_partition(vi, even);
    print("Stable partitioned:\t", vi.begin(), ret1.begin(), 0);
    print("│ ", ret1.begin(), ret1.end());
    vi = original;
    const auto ret2 = rng::partition(vi, even);
    print("Partitioned:\t\t", vi.begin(), ret2.begin(), 0);
    print("│ ", ret2.begin(), ret2.end());
    vi = {16, 30, 44, 30, 15, 24, 10, 18, 12, 35};
    print("Unsorted vector: ", vi.begin(), vi.end());
    stable_sort(rng::begin(vi), rng::end(vi));
    print("Sorted vector:   ", vi.begin(), vi.end());
}

Original vector:        9 6 5 2 3 1 7 8
Stable partitioned:     6 2 8 │ 9 5 3 1 7
Partitioned:            8 6 2 │ 5 3 1 7 9
Unsorted vector: 16 30 44 30 15 24 10 18 12 35
Sorted vector:   10 12 15 16 18 24 30 30 35 44

Siehe auch