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 );

Ordnet Elemente so um, dass der Bereich [first, middle) die sortierten middle − first kleinsten Elemente im Bereich [first, last) enthält.

Die Reihenfolge gleicher Elemente wird nicht garantiert beibehalten. Die Reihenfolge der verbleibenden Elemente im Bereich [middle, last) ist unspezifiziert.

Wenn eine der folgenden Bedingungen erfüllt ist, ist das Verhalten undefiniert:

• [first, middle) oder [middle, last) ist kein gültiger Bereich.

Parameter

Komplexität

Gegeben \(\scriptsize M\)M als middle - first, \(\scriptsize N\)N als last - first:

Ausnahmen

Die Überladungen mit einem Template-Parameter namens ExecutionPolicy melden Fehler wie folgt:

• Wenn die Ausführung einer im Rahmen des Algorithmus aufgerufenen Funktion eine Ausnahme auslöst und ExecutionPolicy eine der Standardrichtlinien ist, wird std::terminate aufgerufen. Für jede andere ExecutionPolicy ist das Verhalten implementierungsdefiniert.
• Wenn der Algorithmus keinen Speicher zuweisen kann, wird std::bad_alloc ausgelöst.

Mögliche Implementierung

Siehe auch die Implementierungen in libstdc++ und 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);
}

Hinweise

Algorithmus

Der verwendete Algorithmus ist typischerweise Heap-Auswahl zur Auswahl der kleinsten Elemente und Heap-Sortierung zum Sortieren der ausgewählten Elemente im Heap in aufsteigender Reihenfolge.

Zur Auswahl der Elemente wird ein Heap verwendet (siehe heap). Zum Beispiel wird für operator< als Vergleichsfunktion ein Max-Heap verwendet, um die middle − first kleinsten Elemente auszuwählen.

Heap-Sortierung wird nach der Auswahl verwendet, um die [first, middle) ausgewählten Elemente zu sortieren (siehe std::sort_heap).

Verwendungszweck

std::partial_sort Algorithmen sind für kleine konstante Anzahlen von [first, middle) ausgewählten Elementen vorgesehen.

Beispiel

#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
        ^----------

Fehlerberichte

Die folgenden verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.

Siehe auch