std:: partial_sort

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

Die Reihenfolge gleicher Elemente ist nicht garantiert erhalten. Die Reihenfolge der verbleibenden Elemente im Bereich [ middle , last ) ist nicht spezifiziert.

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 als Teil des Algorithmus aufgerufenen Funktion eine Exception wirft und ExecutionPolicy einer der Standard-Policies ist, wird std::terminate aufgerufen. Für jede andere ExecutionPolicy ist das Verhalten implementierungsdefiniert.
• Wenn der Algorithmus keinen Speicher allokieren kann, wird std::bad_alloc geworfen.

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 select zur Auswahl der kleinsten Elemente und heap sort zum Sortieren der ausgewählten Elemente im Heap in aufsteigender Reihenfolge.

Um Elemente auszuwählen, 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 Sort 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