std::ranges:: stable_partition

Les entités de type fonction décrites sur cette page sont des algorithm function objects (informellement appelées 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'entre elles.
• Aucune d'entre elles n'est visible pour la recherche dépendante des arguments .
• Lorsque l'une d'entre elles est trouvée par la recherche non qualifiée normale comme 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