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

CKTIS / C++

std::stable_sort — stabilní řazení

std::stable_sort seřadí rozsah a zachová relativní pořadí prvků, které jsou podle porovnání ekvivalentní. Umožňuje řadit záznamy podle klíče, aniž by se změnilo původní pořadí záznamů se stejným klíčem.

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

Syntaxe

#include <algorithm>

std::stable_sort(first, last);
std::stable_sort(first, last, comp);

std::stable_sort deklarované v <algorithm> přeuspořádá prvky rozsahu [first, last) a vrací void. Přetížení bez comp řadí vzestupně pomocí výchozího porovnání; přetížení s comp používá zadaný komparátor. Na rozdíl od std::sort zaručuje zachování relativního pořadí ekvivalentních prvků.

Ekvivalence znamená !comp(a, b) && !comp(b, a), nikoli nutně a == b. Komparátor musí definovat striktní slabé uspořádání: zejména musí být comp(x, x) nepravdivé a uspořádání i z něj odvozená ekvivalence musí být tranzitivní. Nepoužívejte <= místo < a neměňte porovnávané prvky.

Jsou vyžadovány iterátory s náhodným přístupem a prvky musí podporovat výměnu, konstrukci přesunem a přiřazení přesunem. Pro N = last - first je počet porovnání O(N log N), pokud je k dispozici dostatek dodatečné paměti; jinak je nejvýše O(N log² N). Řazení mění vstup, ale nezaručuje konstantní spotřebu pomocné paměti.

Příklad porovnává pouze key: B zůstane před D a A před C. Je určen ke spuštění s příznakem překladače C++23. Zobrazený kód byl spuštěn beze změn v izolovaném prostředí a jeho výstup odpovídal uvedenému výstupu. Toto ověření nepotvrzuje kompatibilitu s produkčním běhovým prostředím. Odkázaný aktuální pracovní návrh může obsahovat rozšíření novější než C++23; uvedená volání je nevyžadují.

Příklady

#include <algorithm>
#include <iostream>
#include <vector>

struct Item {
    int key;
    char id;
};

int main() {
    std::vector<Item> items{{2, 'A'}, {1, 'B'}, {2, 'C'}, {1, 'D'}};

    std::stable_sort(items.begin(), items.end(),
        [](const Item& a, const Item& b) {
            return a.key < b.key;
        });

    for (const Item& item : items) {
        std::cout << item.key << ' ' << item.id << '\n';
    }
}

Výsledek

1 B
1 D
2 A
2 C

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