Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

std::stable_sort — sortowanie stabilne

std::stable_sort sortuje zakres, zachowując względną kolejność elementów równoważnych według porównania. Pozwala uporządkować rekordy według klucza bez zmiany wcześniejszej kolejności rekordów o tym samym kluczu.

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

Składnia

#include <algorithm>

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

std::stable_sort z nagłówka <algorithm> przestawia elementy zakresu [first, last) i zwraca void. Wersja bez comp sortuje rosnąco według domyślnego porównania; wersja z comp używa podanego komparatora. W przeciwieństwie do std::sort gwarantuje zachowanie względnej kolejności elementów równoważnych.

Równoważność oznacza !comp(a, b) && !comp(b, a), a niekoniecznie a == b. Komparator musi definiować ścisły słaby porządek: w szczególności comp(x, x) musi być fałszem, a porządek i wynikająca z niego równoważność muszą być przechodnie. Nie używaj <= zamiast < ani nie modyfikuj porównywanych elementów.

Wymagane są iteratory o dostępie swobodnym oraz elementy obsługujące zamianę, konstrukcję przez przeniesienie i przypisanie przez przeniesienie. Dla N = last - first liczba porównań wynosi O(N log N), jeśli dostępna jest wystarczająca dodatkowa pamięć; w przeciwnym razie wynosi najwyżej O(N log² N). Sortowanie modyfikuje wejście, ale nie gwarantuje stałego zużycia pamięci pomocniczej.

W przykładzie porównywany jest tylko key: B pozostaje przed D, a A przed C. Przykład jest przeznaczony do uruchomienia z flagą C++23. Pokazany kod uruchomiono bez zmian w odizolowanym środowisku i potwierdzono zgodność wyniku z podanym. Ta weryfikacja nie potwierdza zgodności ze środowiskiem uruchomieniowym produkcji. Podany bieżący szkic standardu może zawierać rozszerzenia późniejsze niż C++23; pokazane wywołania ich nie wymagają.

Przykłady

#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';
    }
}

Wynik

1 B
1 D
2 A
2 C

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła