Standardalgorithmen statt selbst gebauter Schleifen#

Daten sammeln und verarbeiten · Lektion 31 von 60

Voraussetzungen: Iteratoren. Lernziel: Du sortierst, suchst und summierst mit passenden Bibliotheksfunktionen.

Die Standardbibliothek bietet wiederverwendbare Algorithmen, also festgelegte Verarbeitungsverfahren. Sie arbeiten häufig auf Iteratorbereichen und sind dadurch für mehrere Container nutzbar.

1#include <algorithm>2#include <iostream>3#include <numeric>4#include <vector>5 6int main() {7    std::vector<int> werte{4, 1, 3, 1};8    std::sort(werte.begin(), werte.end());9    const auto treffer = std::find(werte.begin(), werte.end(), 3);10    const long long summe = std::accumulate(werte.begin(), werte.end(), 0LL);11    std::cout << "Gefunden: " << std::boolalpha12              << (treffer != werte.end()) << '\n';13    std::cout << "Summe: " << summe << '\n';14}

sort ordnet den Vector aufsteigend. find sucht den ersten gleichen Wert. accumulate aus <numeric> summiert hier ausgehend von 0LL. Dieser Anfangswert bestimmt auch den Akkumulatortyp. Ein Akkumulator sammelt ein fortlaufend berechnetes Ergebnis. Mit einfachem 0 würde zunächst in int gerechnet.

Aufwand verstehen#

Komplexität beschreibt, wie der Arbeitsaufwand mit der Datenmenge wächst. O-Notation beschreibt dabei Größenordnungen. Ein lineares O(n)-Verfahren muss bei doppelter Elementanzahl ungefähr entsprechend mehr Elemente betrachten. find sucht linear; sort benötigt eine Größenordnung von n log n Vergleichen.

Binäre Suche halbiert wiederholt den Suchbereich und benötigt eine passend sortierte Folge. std::binary_search auf unsortierten Daten ist kein gültiger Ersatz für find. Dokumentiere solche Vorbedingungen, also Anforderungen, die vor dem Aufruf erfüllt sein müssen.

Entfernen und Prädikate#

std::remove löscht bei einem Vector nicht selbst die Elemente aus dem Container. Es schiebt zu behaltende Elemente nach vorne und liefert ein neues logisches Ende. Danach entfernt erase den übrigen Bereich. Das heißt Erase-remove idiom, ein verbreitetes Verwendungsmuster. C++20 bietet dafür außerdem std::erase bei passenden Containern.

Ein Prädikat ist eine Funktion, die einen Wahrheitswert liefert, etwa „ist diese Zahl gerade?“. Algorithmen wie count_if verwenden ein solches Kriterium. Unter Lambdas formulierst du es direkt am Aufruf.

Übung#

Wieso brauchst du trotz long long summe im Beispiel den Anfangswert 0LL?

Weiterlernen#

Zurück: Iteratoren und gültige Bereiche · Kursübersicht · Weiter: Speicher, Adressen und Lebensdauer