CKTIS / C++
std::stable_sort — stabilno urejanje
std::stable_sort uredi obseg in ohrani relativni vrstni red elementov, ki so glede na primerjavo enakovredni. Omogoča urejanje zapisov po ključu, ne da bi spremenili predhodni vrstni red zapisov z enakim ključem.
Različica: C++23; repository compiler flag, production runtime not attested
Sintaksa
#include <algorithm>
std::stable_sort(first, last);
std::stable_sort(first, last, comp);std::stable_sort, deklariran v <algorithm>, prerazporedi elemente obsega [first, last) in vrne void. Preobremenitev brez comp uredi elemente naraščajoče s privzeto primerjavo; preobremenitev z comp uporabi podani primerjalnik. V nasprotju s std::sort zagotavlja ohranitev relativnega vrstnega reda enakovrednih elementov.
Enakovrednost pomeni !comp(a, b) && !comp(b, a), ne nujno a == b. Primerjalnik mora določati strogo šibko urejenost: zlasti mora biti comp(x, x) neresničen, tako urejenost kot iz nje izpeljana enakovrednost pa morata biti tranzitivni. Namesto < ne uporabljajte <= in ne spreminjajte primerjanih elementov.
Potrebni so iteratorji z naključnim dostopom, elementi pa morajo podpirati zamenjavo, konstrukcijo s premikom in prirejanje s premikom. Za N = last - first je število primerjav O(N log N), če je na voljo dovolj dodatnega pomnilnika; sicer je največ O(N log² N). Urejanje spremeni vhod, vendar ne zagotavlja konstantne porabe pomožnega pomnilnika.
Primer primerja samo key: B ostane pred D, A pa pred C. Namenjen je izvajanju z zastavico prevajalnika C++23. Prikazana koda je bila brez sprememb izvedena v izoliranem okolju, njen izpis pa se je ujemal z navedenim. To preverjanje ne potrjuje združljivosti s produkcijskim izvajalnim okoljem. Povezani trenutni delovni osnutek lahko vsebuje razširitve, ki so novejše od C++23; prikazani klici jih ne potrebujejo.
Primeri
#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';
}
}
Rezultat
1 B 1 D 2 A 2 C
Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.