Sortieren von Vektoren in C++

Um einen std::vector in C++ zu sortieren, rufe std::sort mit den Iteratoren begin() und end() des Vektors auf. Standardmäßig werden die Elemente anhand von operator< geordnet. Für einen Typ mit einer anderen Sortierreihenfolge übergibst du einen Vergleicher, der angibt, ob sein erstes Argument vor seinem zweiten stehen soll.

Einen Vektor mit std::sort sortieren

std::sort ordnet die Elemente im halboffenen Bereich vom ersten Iterator bis, aber ohne den letzten Iterator neu an. Ein std::vector stellt die von diesem Algorithmus benötigten Iteratoren mit wahlfreiem Zugriff bereit. Binde <algorithm> für std::sort ein; das Beispiel verwendet außerdem <iostream> für die Ausgabe und <vector> für den Container. Ohne ein Vergleichsargument verwendet der Algorithmus die Standardreihenfolge des Elementtyps, die häufig durch operator< ausgedrückt wird.

Führe dieses Beispiel aus. Die Ausgabe zeigt sortierte Zahlen.

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> values{8, 3, 6, 1, 5};
  std::sort(values.begin(), values.end());

  for (std::size_t index = 0; index < values.size(); ++index) {
    if (index != 0) {
      std::cout << ' ';
    }
    std::cout << values[index];
  }
  std::cout << '\n';
}

1 3 5 6 8

Verwende für den gesamten Vektor denselben Iteratorbereich. Wenn nur ein Teil sortiert werden soll, übergib Iteratoren, die diesen Teil begrenzen. Der Bereich muss gültig sein; sein letzter Iterator ist nicht eingeschlossen. Die Standardreihenfolge eignet sich für Zahlen und für Typen, deren definierte Reihenfolge deinen Anforderungen entspricht. Bei Datensätzen kannst du mit einem Vergleicher gezielt ein Feld auswählen.

Datensätze mit einem Lambda-Vergleicher sortieren

Ein Lambda hält eine kurze Vergleichsregel direkt neben dem Sortieraufruf, der sie verwendet. In diesem Beispiel werden Task-Datensätze nach ihrem Feld priority geordnet. Der Vergleicher erhält zwei Datensätze und gibt true zurück, wenn der erste vor dem zweiten stehen soll. Seine Parameter sind konstante Referenzen, da der Vergleich keinen der beiden Datensätze ändern muss.

Führe dieses Beispiel aus. Die englischen Aufgabennamen in der Ausgabe bleiben unverändert.

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

struct Task {
  std::string name;
  int priority;
};

int main() {
  std::vector<Task> tasks{{"write", 3}, {"review", 1}, {"build", 2}};
  std::sort(tasks.begin(), tasks.end(),
            [](const Task& left, const Task& right) {
              return left.priority < right.priority;
            });

  for (const Task& task : tasks) {
    std::cout << task.name << ':' << task.priority << '\n';
  }
}

review:1
build:2
write:3

Die Vergleichsregel muss eine strenge schwache Ordnung festlegen: Sie muss sich konsistent verhalten, und kein Element gilt als vor sich selbst stehend. Der Vergleich eines ganzzahligen Feldes mit < sortiert priority aufsteigend. Werden die Operanden vertauscht, ändert sich die Richtung. Wenn du std::sort erneut mit einem anderen Vergleicher aufrufst, ordnet dieser Aufruf den aktuellen Bereich nach der neuen Regel; aufeinanderfolgende Aufrufe verbinden ihre Kriterien nicht zu einer Sortierung nach mehreren Feldern. Wenn mehrere Kriterien gelten sollen, formuliere die vollständige Regel in einem einzigen Vergleicher.

Einen benannten Vergleicher für wiederverwendbare Regeln nutzen

Wenn dieselbe Regel an mehreren Stellen gebraucht wird, gib ihr einen Namen. Ein Funktionsobjekt mit einem const-Aufrufoperator lässt sich wie ein Lambda an std::sort übergeben. Dieses Beispiel sortiert Aufgaben nach Namen, sodass sich der Vergleicher überall dort wiederverwenden lässt, wo diese Regel benötigt wird.

Führe dieses Beispiel aus. Die englischen Aufgabennamen in der Ausgabe bleiben unverändert.

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

struct Task {
  std::string name;
  int priority;
};

struct ByName {
  bool operator()(const Task& left, const Task& right) const {
    return left.name < right.name;
  }
};

int main() {
  std::vector<Task> tasks{{"write", 3}, {"review", 1}, {"build", 2}};
  std::sort(tasks.begin(), tasks.end(), ByName{});

  for (const Task& task : tasks) {
    std::cout << task.name << ':' << task.priority << '\n';
  }
}

build:2
review:1
write:3

Ein benannter Vergleicher ist sinnvoll, wenn seine Logik einen aussagekräftigen Namen verdient oder in mehreren Sortieraufrufen verwendet werden soll. Achte darauf, dass seine Sortierreihenfolge zu den Daten passt, und verwende für schreibgeschützte Vergleiche Parameter vom Typ konstante Referenz. Für einen einmaligen Vergleich anhand eines Feldes ist ein Lambda meist direkter. In beiden Fällen bestimmt der Vergleicher die Reihenfolge; die Standardreihenfolge mit operator< kommt nur dann zum Einsatz, wenn kein Vergleicher übergeben wird.