Namespaces
Variants

std:: sort

From cppreference.net
C++
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy , ranges::sort , ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
(C++17)
Search operations
Modifying sequence operations
Copy operations
(C++11)
(C++11)
(C++11)
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17) (C++11)
(C++20) (C++20)
Sampling operations
(C++17)

Sorting and related operations
Partitioning operations
Sorting operations
Binary search operations
(on partitioned ranges)
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
Minimum/maximum operations
Lexicographical comparison operations
(C++20)
Permutation operations
C library
Numeric operations
Operations on uninitialized memory
Definiert im Header <algorithm>
template < class RandomIt >
void sort ( RandomIt first, RandomIt last ) ;
(1) (constexpr seit C++20)
template < class ExecutionPolicy, class RandomIt >

void sort ( ExecutionPolicy && policy,

RandomIt first, RandomIt last ) ;
(2) (seit C++17)
template < class RandomIt, class Compare >
void sort ( RandomIt first, RandomIt last, Compare comp ) ;
(3) (constexpr seit C++20)
template < class ExecutionPolicy, class RandomIt, class Compare >

void sort ( ExecutionPolicy && policy,

RandomIt first, RandomIt last, Compare comp ) ;
(4) (seit C++17)

Sortiert die Elemente im Bereich [ first , last ) in nicht-absteigender Reihenfolge. Die Reihenfolge gleicher Elemente ist nicht garantiert erhalten.

1) Elemente sind sortiert bezüglich operator < (bis C++20) std:: less { } (seit C++20) .
3) Elemente werden bezüglich comp sortiert.
2,4) Gleich wie (1,3) , aber ausgeführt gemäß policy .
Diese Überladungen nehmen nur dann an der Überladungsauflösung teil, wenn alle folgenden Bedingungen erfüllt sind:

std:: is_execution_policy_v < std:: decay_t < ExecutionPolicy >> ist true .

(bis C++20)

std:: is_execution_policy_v < std:: remove_cvref_t < ExecutionPolicy >> ist true .

(seit C++20)

Wenn eine der folgenden Bedingungen erfüllt ist, ist das Verhalten undefiniert:

(bis C++11)
(seit C++11)

Inhaltsverzeichnis

Parameter

first, last - das Paar von Iteratoren, das den Bereich der zu sortierenden Elemente definiert
policy - die zu verwendende Ausführungsrichtlinie
comp - Vergleichsfunktionsobjekt (d.h. ein Objekt, das die Anforderungen von Compare erfüllt), das ​ true zurückgibt, wenn das erste Argument kleiner als (d.h. vor dem zweiten geordnet ist) das zweite ist.

Die Signatur der Vergleichsfunktion sollte äquivalent zu Folgendem sein:

bool cmp ( const Type1 & a, const Type2 & b ) ;

Obwohl die Signatur kein const & benötigt, darf die Funktion die übergebenen Objekte nicht modifizieren und muss alle Werte des Typs (möglicherweise const) Type1 und Type2 unabhängig von der Wertkategorie akzeptieren können (daher ist Type1& nicht erlaubt , ebenso wenig wie Type1 , es sei denn, für Type1 ist eine Verschiebung äquivalent zu einer Kopie (seit C++11) ).
Die Typen Type1 und Type2 müssen so beschaffen sein, dass ein Objekt vom Typ RandomIt dereferenziert und dann implizit in beide konvertiert werden kann. ​

Typanforderungen
-
RandomIt muss die Anforderungen von LegacyRandomAccessIterator erfüllen.
-
Compare muss die Anforderungen von Compare erfüllen.

Komplexität

Gegeben N als last - first :

1,2) O(N·log(N)) Vergleiche mit operator < (bis C++20) std:: less { } (seit C++20) .
3,4) O(N·log(N)) Anwendungen des Comparators comp .

Ausnahmen

Die Überladungen mit einem Template-Parameter namens ExecutionPolicy melden Fehler wie folgt:

  • Wenn die Ausführung einer als Teil des Algorithmus aufgerufenen Funktion eine Exception wirft und ExecutionPolicy einer der Standard-Policies ist, wird std::terminate aufgerufen. Für jede andere ExecutionPolicy ist das Verhalten implementierungsdefiniert.
  • Wenn der Algorithmus keinen Speicher allokieren kann, wird std::bad_alloc geworfen.

Mögliche Implementierung

Siehe auch die Implementierungen in libstdc++ und libc++ .

Hinweise

Vor LWG713 erlaubte die Komplexitätsanforderung die Implementierung von sort() ausschließlich mit Quicksort , was im schlimmsten Fall O(N 2
) Vergleiche benötigen könnte.

Introsort kann alle Fälle mit O(N·log(N)) Vergleichen bewältigen (ohne zusätzlichen Overhead im Durchschnittsfall zu verursachen) und wird daher üblicherweise für die Implementierung von sort() verwendet.

libc++ hat die korrigierte Zeitkomplexitätsanforderung bis LLVM 14 nicht implementiert.

Beispiel

Diesen Code ausführen 
#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");
}

Ausgabe: 

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
**Übersetzungshinweise:** - HTML-Tags und Attribute wurden unverändert belassen - Code innerhalb der ` 
` und `` Tags wurde nicht übersetzt
- C++-spezifische Begriffe (wie "function object", "lambda expression") wurden beibehalten
- Nur die umgebenden deutschen Textelemente wurden übersetzt
- Die Übersetzung folgt professionellen technischen Standards

Fehlerberichte

Die folgenden verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.

DR Angewendet auf Verhalten wie veröffentlicht Korrektes Verhalten
LWG 713 C++98 die O(N·log(N)) Zeitkomplexität war nur im Durchschnitt erforderlich sie ist für den Worst-Case erforderlich

Siehe auch

sortiert die ersten N Elemente eines Bereichs
(Funktions-Template)
sortiert einen Bereich von Elementen unter Beibehaltung der Reihenfolge gleicher Elemente
(Funktions-Template)
(C++20)
sortiert einen Bereich in aufsteigender Reihenfolge
(Algorithmus-Funktionsobjekt)