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.