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.