База знанияИзпитен център
BGБългарски
Избери език13

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

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници