CKTIS / C++
std::stable_sort — stabilno sortiranje
std::stable_sort sortira raspon i čuva relativni redoslijed elemenata koji su prema usporedbi ekvivalentni. Omogućuje sortiranje zapisa prema ključu bez promjene prethodnog redoslijeda zapisa s istim ključem.
Verzija: 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 u <algorithm>, preslaguje elemente raspona [first, last) i vraća void. Preopterećenje bez comp sortira uzlazno prema zadanoj usporedbi; ono s comp koristi zadani komparator. Za razliku od std::sort, jamči očuvanje relativnog redoslijeda ekvivalentnih elemenata.
Ekvivalentnost znači !comp(a, b) && !comp(b, a), a ne nužno a == b. Komparator mora definirati strogi slabi poredak: osobito comp(x, x) mora biti netočno, a i poredak i ekvivalentnost koja iz njega proizlazi moraju biti tranzitivni. Nemojte koristiti <= umjesto < niti mijenjati elemente koji se uspoređuju.
Potrebni su iteratori s nasumičnim pristupom, a elementi moraju podržavati zamjenu, konstrukciju premještanjem i dodjelu premještanjem. Za N = last - first, broj usporedbi iznosi O(N log N) ako je dostupno dovoljno dodatne memorije; u protivnom je najviše O(N log² N). Sortiranje mijenja ulaz, ali ne jamči konstantnu potrošnju pomoćne memorije.
Primjer uspoređuje samo key: B ostaje prije D, a A prije C. Namijenjen je pokretanju uz opciju prevoditelja za C++23. Prikazani kôd izvršen je bez izmjena u izoliranom okruženju, a dobiveni ispis podudarao se s navedenim. Ta provjera ne potvrđuje kompatibilnost s produkcijskim okruženjem za izvođenje. Povezani aktualni radni nacrt može sadržavati proširenja novija od C++23; prikazani pozivi ih ne zahtijevaju.
Primjeri
#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
Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.