Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

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.

Viri