Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / C++

std::stable_sort — stabilné triedenie

std::stable_sort triedi rozsah a zachováva relatívne poradie prvkov, ktoré sú podľa porovnania ekvivalentné. Umožňuje usporiadať záznamy podľa kľúča bez zmeny pôvodného poradia záznamov s rovnakým kľúčom.

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

Syntax

#include <algorithm>

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

std::stable_sort deklarované v <algorithm> preusporiada prvky rozsahu [first, last) a vracia void. Preťaženie bez comp triedi vzostupne pomocou predvoleného porovnania; preťaženie s comp používa zadaný komparátor. Na rozdiel od std::sort zaručuje zachovanie relatívneho poradia ekvivalentných prvkov.

Ekvivalencia znamená !comp(a, b) && !comp(b, a), nie nevyhnutne a == b. Komparátor musí definovať striktné slabé usporiadanie: najmä comp(x, x) musí byť nepravdivé a usporiadanie aj z neho vyplývajúca ekvivalencia musia byť tranzitívne. Nepoužívajte <= namiesto < a nemeňte porovnávané prvky.

Vyžadujú sa iterátory s náhodným prístupom a prvky musia podporovať výmenu, konštrukciu presunom a priradenie presunom. Pre N = last - first je počet porovnaní O(N log N), ak je k dispozícii dostatok dodatočnej pamäte; inak je najviac O(N log² N). Triedenie mení vstup, ale nezaručuje konštantnú spotrebu pomocnej pamäte.

Príklad porovnáva iba key: B zostane pred D a A pred C. Je určený na spustenie s príznakom kompilátora C++23. Zobrazený kód bol spustený bez zmien v izolovanom prostredí a jeho výstup sa zhodoval s uvedeným výstupom. Toto overenie nepotvrdzuje kompatibilitu s produkčným behovým prostredím. Odkázaný aktuálny pracovný návrh môže obsahovať rozšírenia novšie než C++23; uvedené volania ich nepotrebujú.

Prí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ýsledok

1 B
1 D
2 A
2 C

Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.

Zdroje