CKTIS / C++
std::stable_sort — стабилно сортиране
std::stable_sort сортира диапазон, като запазва относителния ред на елементите, еквивалентни според сравнението. Позволява да подреждате записи по ключ, без да променяте предишния ред на записите с еднакъв ключ.
Версия: C++23; repository compiler flag, production runtime not attested
Синтаксис
#include <algorithm>
std::stable_sort(first, last);
std::stable_sort(first, last, comp);std::stable_sort, декларирана в <algorithm>, пренарежда елементите в [first, last) и връща void. Версията без comp сортира във възходящ ред чрез сравнението по подразбиране; версията с comp използва предоставения компаратор. За разлика от std::sort, тя гарантира запазването на относителния ред на еквивалентните елементи.
Еквивалентност означава !comp(a, b) && !comp(b, a), а не непременно a == b. Компараторът трябва да задава строго слабо нареждане: по-специално comp(x, x) трябва да е невярно, а както нареждането, така и произтичащата от него еквивалентност трябва да са транзитивни. Не използвайте <= вместо < и не променяйте сравняваните елементи.
Необходими са итератори с произволен достъп, а елементите трябва да поддържат разместване, конструиране чрез преместване и присвояване чрез преместване. За N = last - first броят на сравненията е O(N log N), когато има достатъчно допълнителна памет; в противен случай е най-много O(N log² N). Сортирането променя входните данни, но не гарантира постоянно потребление на помощна памет.
Примерът сравнява само key: B остава преди D, а A преди C. Предназначен е за изпълнение с флаг на компилатора за C++23. Показаният код е изпълнен без промени в изолирана среда и полученият изход съвпада с посочения. Тази проверка не удостоверява съвместимост с продукционната среда за изпълнение. Свързаният актуален работен проект може да съдържа разширения след C++23; показаните извиквания не се нуждаят от тях.
Примери
#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';
}
}
Резултат
1 B 1 D 2 A 2 C
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.