Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

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.

Izvori