Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

CKTIS / C++

std::stable_sort — tri stable

std::stable_sort trie une plage tout en préservant l’ordre relatif des éléments équivalents selon la comparaison. Il permet de classer des enregistrements par clé sans modifier l’ordre antérieur des enregistrements ayant la même clé.

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

Syntaxe

#include <algorithm>

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

std::stable_sort, déclaré dans <algorithm>, réorganise les éléments de [first, last) et renvoie void. La surcharge sans comp effectue un tri croissant avec la comparaison par défaut ; celle avec comp utilise le comparateur fourni. Contrairement à std::sort, elle garantit la préservation de l’ordre relatif des éléments équivalents.

L’équivalence signifie !comp(a, b) && !comp(b, a), et pas nécessairement a == b. Le comparateur doit définir un ordre strict faible : en particulier, comp(x, x) doit être faux, et l’ordre ainsi que l’équivalence qui en découle doivent être transitifs. N’utilisez pas <= à la place de < et ne modifiez pas les éléments comparés.

Des itérateurs à accès aléatoire sont nécessaires, et les éléments doivent permettre l’échange, la construction par déplacement et l’affectation par déplacement. Pour N = last - first, le nombre de comparaisons est O(N log N) si suffisamment de mémoire supplémentaire est disponible ; sinon, il est au plus de O(N log² N). Le tri modifie l’entrée, mais ne garantit pas une utilisation constante de la mémoire auxiliaire.

L’exemple compare uniquement key : B reste avant D, et A avant C. Il est prévu pour être exécuté avec une option de compilateur C++23. Le code présenté a été exécuté sans modification dans un environnement isolé, et la sortie obtenue correspondait à la sortie indiquée. Cette vérification n’atteste pas la compatibilité avec l’environnement d’exécution en production. Le projet de norme actuel lié peut contenir des extensions postérieures à C++23 ; les appels présentés n’en ont pas besoin.

Exemples

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

Résultat

1 B
1 D
2 A
2 C

Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.

Sources