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

Les entités apparentées à des fonctions décrites sur cette page sont des objets fonctions algorithmiques (informellement appelés niebloids), c'est-à-dire :

• Les listes d'arguments de template explicites ne peuvent pas être spécifiées lors de l'appel de l'une d'elles.
• Aucune d'entre elles n'est visible par la recherche dépendante des arguments.
• Lorsque l'une d'elles est trouvée par une recherche non qualifiée normale en tant que nom à gauche de l'opérateur d'appel de fonction, la recherche dépendante des arguments est inhibée.

Paramètres

Valeur de retour

Complexité

Étant donné N = ranges:: distance ( first, last ) , la complexité est au pire \(\scriptsize N\cdot\log{(N)}\) N·log(N) échanges, et seulement \(\scriptsize \mathcal{O}(N)\) 𝓞(N) échanges dans le cas où un tampon mémoire supplémentaire est utilisé. Exactement \(\scriptsize N\) N applications du prédicat pred et de la projection proj .

Notes

Cette fonction tente d'allouer un tampon temporaire. Si l'allocation échoue, l'algorithme moins efficace est choisi.

Implémentation possible

Cette implémentation n'utilise pas de tampon mémoire supplémentaire et peut donc être moins efficace. Voir également l'implémentation dans MSVC STL et 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 {};

Exemple

#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

Voir aussi