std::partial_sort

template< class RandomIt >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last );

template< class ExecutionPolicy, class RandomIt >
void partial_sort( ExecutionPolicy&& policy,
                   RandomIt first, RandomIt middle, RandomIt last );

template< class RandomIt, class Compare >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last,
                   Compare comp );

template< class ExecutionPolicy, class RandomIt, class Compare >
void partial_sort( ExecutionPolicy&& policy,
                   RandomIt first, RandomIt middle, RandomIt last,
                   Compare comp );

Réorganise les éléments de telle sorte que la plage [first, middle) contienne les middle − first plus petits éléments triés de la plage [first, last).

L’ordre des éléments égaux n’est pas garanti d’être préservé. L’ordre des éléments restants dans la plage [middle, last) n’est pas spécifié.

Si l’une des conditions suivantes est satisfaite, le comportement est indéfini :

• [first, middle) ou [middle, last) n’est pas une plage valide.

Paramètres

Complexité

Étant donné \(\scriptsize M\)M comme middle - first, \(\scriptsize N\)N comme last - first:

Exceptions

Les surcharges avec un paramètre template nommé ExecutionPolicy signalent les erreurs comme suit :

• Si l’exécution d’une fonction appelée dans le cadre de l’algorithme lève une exception et que ExecutionPolicy fait partie des politiques standard, std::terminate est appelé. Pour toute autre ExecutionPolicy, le comportement est défini par l’implémentation.
• Si l’algorithme ne peut pas allouer de mémoire, std::bad_alloc est levée.

Implémentation possible

Voir aussi les implémentations dans libstdc++ et libc++.

template<typename RandomIt>
constexpr //< since C++20
void partial_sort(RandomIt first, RandomIt middle, RandomIt last)
{
    typedef typename std::iterator_traits<RandomIt>::value_type VT;
    std::partial_sort(first, middle, last, std::less<VT>());
}

namespace impl
{
    template<typename RandomIt, typename Compare>
    constexpr //< since C++20
    void sift_down(RandomIt first, RandomIt last, const Compare& comp)
    {
        // sift down element at “first”
        const auto length = static_cast<std::size_t>(last - first);
        std::size_t current = 0;
        std::size_t next = 2;
        while (next < length)
        {
            if (comp(*(first + next), *(first + (next - 1))))
                --next;
            if (!comp(*(first + current), *(first + next)))
                return;
            std::iter_swap(first + current, first + next);
            current = next;
            next = 2 * current + 2;
        }
        --next;
        if (next < length && comp(*(first + current), *(first + next)))
            std::iter_swap(first + current, first + next);
    }

    template<typename RandomIt, typename Compare>
    constexpr //< since C++20
    void heap_select(RandomIt first, RandomIt middle, RandomIt last, const Compare& comp)
    {
        std::make_heap(first, middle, comp);
        for (auto i = middle; i != last; ++i)
        {
            if (comp(*i, *first))
            {
                std::iter_swap(first, i);
                sift_down(first, middle, comp);
            }
        }
    }
} // namespace impl

template<typename RandomIt, typename Compare>
constexpr //< since C++20
void partial_sort(RandomIt first, RandomIt middle, RandomIt last, Compare comp)
{
    impl::heap_select(first, middle, last, comp);
    std::sort_heap(first, middle, comp);
}

Notes

Algorithme

L’algorithme utilisé est typiquement heap select pour sélectionner les plus petits éléments, et heap sort pour trier les éléments sélectionnés dans le tas par ordre croissant.

Pour sélectionner les éléments, un tas est utilisé (voir heap). Par exemple, pour operator< comme fonction de comparaison, un max‑heap est utilisé pour sélectionner les middle − first plus petits éléments.

Heap sort est utilisé après la sélection pour trier les [first, middle) éléments sélectionnés (voir std::sort_heap).

Utilisation prévue

std::partial_sortLes algorithmes sont destinés à être utilisés pour des nombres constants faibles[first, middle) d’éléments sélectionnés.

Exemple

#include <algorithm>
#include <array>
#include <functional>
#include <iostream>

void print(const auto& s, int middle)
{
    for (int a : s)
        std::cout << a << ' ';
    std::cout << '\n';
    if (middle > 0)
    {
        while (middle-- > 0)
            std::cout << "--";
        std::cout << '^';
    }
    else if (middle < 0)
    {
        for (auto i = s.size() + middle; --i; std::cout << "  ")
        {}
        
        for (std::cout << '^'; middle++ < 0; std::cout << "--")
        {}
    }
    std::cout << '\n';
};

int main()
{
    std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
    print(s, 0);
    std::partial_sort(s.begin(), s.begin() + 3, s.end());
    print(s, 3);
    std::partial_sort(s.rbegin(), s.rbegin() + 4, s.rend());
    print(s, -4);
    std::partial_sort(s.rbegin(), s.rbegin() + 5, s.rend(), std::greater{});
    print(s, -5);
}

5 7 4 2 8 6 1 9 0 3

0 1 2 7 8 6 5 9 4 3
------^
4 5 6 7 8 9 3 2 1 0
          ^--------
4 3 2 1 0 5 6 7 8 9
        ^----------

Rapports de défauts

Les rapports de défauts modifiant le comportement suivants ont été appliqués rétroactivement aux normes C++ publiées précédemment.

Voir aussi