Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

CKTIS / C++

std::partial_sort — seřazený začátek rozsahu

std::partial_sort vybere k nejmenších prvků a umístí je do seřazeného začátku rozsahu. Mění vstupní data, zatímco pořadí zbývajících prvků není specifikováno.

Verze: C++23; repository compiler flag, production runtime not attested

Syntaxe

#include <algorithm>
std::partial_sort(first, middle, last);
std::partial_sort(first, middle, last, comp);

std::partial_sort deklarované v <algorithm> vytvoří seřazených prvních k prvků, aniž by seřadilo celý rozsah. Pro k = middle - first umístí do [first, middle) prvky, které by se po úplném seřazení nacházely na začátku. Výchozí pořadí je vzestupné; přetížení s comp použije zadané uspořádání. Vrací void.

Algoritmus přeuspořádá prvky v původním rozsahu. Pořadí v [middle, last) není specifikováno: nepředpokládejte, že tato část zůstane beze změny nebo bude seřazena. Stabilita není zaručena, takže prvky ekvivalentní podle porovnání nemusí zachovat své vzájemné pořadí.

Jsou vyžadovány iterátory s náhodným přístupem a platné rozsahy [first, middle) a [middle, last). Prvky musí podporovat výměnu, konstrukci přesunem a přiřazení přesunem. Před vytvořením first + k zajistěte, že platí 0 <= k <= last - first. Komparátor musí definovat striktní slabé uspořádání; nepoužívejte <= místo <.

Pro N = last - first a k > 1 je počet porovnání přibližně N * log(k). Tento algoritmus použijte, když potřebujete seřazenou nejlepší podmnožinu dat. Při middle == last se seřadí celý rozsah. Příklad vypisuje pouze tři vybrané prvky, takže jeho výsledek nezávisí na nespecifikovaném pořadí zbytku.

Příklady

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

int main() {
    std::array<int, 6> values{8, 3, 7, 1, 5, 2};
    constexpr int k = 3;
    std::partial_sort(values.begin(), values.begin() + k, values.end());

    for (int i = 0; i < k; ++i) {
        if (i != 0) std::cout << ' ';
        std::cout << values[i];
    }
    std::cout << '\n';
}

Výsledek

1 2 3

Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.

Zdroje