std::sort

template< class RandomIt >
void sort( RandomIt first, RandomIt last );

template< class ExecutionPolicy, class RandomIt >
void sort( ExecutionPolicy&& policy,
           RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

template< class ExecutionPolicy, class RandomIt, class Compare >
void sort( ExecutionPolicy&& policy,
           RandomIt first, RandomIt last, Compare comp );

Trie les éléments dans la plage [first, last) dans l'ordre non décroissant. L'ordre des éléments égaux n'est pas garanti d'être conservé.

Si l'une des conditions suivantes est satisfaite, le comportement est indéfini :

Paramètres

Complexité

Étant donné \(\scriptsize N\) N comme last - first :

Exceptions

Les surcharges avec un paramètre de modèle nommé ExecutionPolicy signalent les erreurs comme suit :

• Si l'exécution d'une fonction invoquée dans le cadre de l'algorithme lève une exception et que ExecutionPolicy fait partie des politiques standard , std::terminate est appelé. Pour tout autre ExecutionPolicy , le comportement est défini par l'implémentation.
• Si l'algorithme ne parvient pas à allouer de la mémoire, std::bad_alloc est levé.

Implémentation possible

Voir également les implémentations dans libstdc++ et libc++ .

Notes

Avant LWG713 , l'exigence de complexité permettait à sort() d'être implémenté en utilisant uniquement Quicksort , ce qui pouvait nécessiter \(\scriptsize O(N^2)\) O(N 2
) comparaisons dans le pire cas.

Introsort peut traiter tous les cas avec \(\scriptsize O(N \cdot \log(N))\) O(N·log(N)) comparaisons (sans entraîner de surcharge supplémentaire dans le cas moyen), et est donc généralement utilisé pour implémenter sort() .

libc++ n'a pas implémenté l'exigence corrigée de complexité temporelle jusqu'à LLVM 14 .

Exemple

#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
#include <string_view>
int main()
{
    std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
    auto print = [&s](std::string_view const rem)
    {
        for (auto a : s)
            std::cout << a << ' ';
        std::cout << ": " << rem << '\n';
    };
    std::sort(s.begin(), s.end());
    print("sorted with the default operator<");
    std::sort(s.begin(), s.end(), std::greater<int>());
    print("sorted with the standard library compare function object");
    struct
    {
        bool operator()(int a, int b) const { return a < b; }
    }
    customLess;
    std::sort(s.begin(), s.end(), customLess);
    print("sorted with a custom function object");
    std::sort(s.begin(), s.end(), [](int a, int b)
                                  {
                                      return a > b;
                                  });
    print("sorted with a lambda expression");
}

0 1 2 3 4 5 6 7 8 9 : sorted with the default operator<
9 8 7 6 5 4 3 2 1 0 : sorted with the standard library compare function object
0 1 2 3 4 5 6 7 8 9 : sorted with a custom function object
9 8 7 6 5 4 3 2 1 0 : sorted with a lambda expression

Rapports de défauts

Les rapports de défauts modifiant le comportement suivants ont été appliqués rétroactivement aux normes C++ précédemment publiées.

Voir aussi