Ausführbare C++-Docs: Algorithmen

Q: Wie prüfe ich in C++, ob ein Wert in einem vector vorhanden ist?

Verwende std::find: auto it = find(v.begin(), v.end(), target);. Ist it == v.end(), ist der Wert nicht vorhanden; andernfalls zeigt it auf die erste Übereinstimmung. Um statt eines exakten Werts eine Bedingung zu prüfen, verwende std::any_of mit einem Prädikat.

Schleifen, die du nicht schreiben musst

Auf der vorherigen Seite hast du gesehen, dass jeder Container Iteratoren ausgibt - leichtgewichtige Cursor mit begin() und end(). Diese Abstraktion ist der ganze Grund, warum die Standardalgorithmen existieren. Statt jedes Mal eine rohe for-Schleife zu schreiben, wenn du Daten durchsuchen, zählen oder transformieren willst, rufst du eine benannte Funktion aus <algorithm> auf und übergibst ihr einen Bereich.

Ein Bereich besteht nur aus zwei Iteratoren: wo gestartet und eins hinter dem Punkt, an dem gestoppt wird. Da jeder Algorithmus dieselbe Iterator-Sprache spricht, funktioniert dasselbe find auf einem vector, einem string oder einem einfachen Array.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {4, 8, 15, 16, 23, 42};

    // Ist 16 im Bereich [begin, end)?
    auto it = find(v.begin(), v.end(), 16);

    if (it != v.end())
        cout << "found " << *it << " at index " << (it - v.begin()) << "\n";
    else
        cout << "not found\n";
    return 0;
}

Das Muster, das du verinnerlichen solltest: Ein suchender Algorithmus gibt den end()-Iterator zurück, um „nichts gefunden" zu bedeuten. Vergleiche das Ergebnis immer mit end(), bevor du es dereferenzierst - das Dereferenzieren von end() ist undefiniertes Verhalten.

Zählen und Prüfen mit Prädikaten

Viele Algorithmen nehmen ein Prädikat entgegen - eine Funktion (meist eine Lambda), die für jedes Element ein bool zurückgibt. count_if zählt Treffer; all_of, any_of und none_of beantworten Ja/Nein-Fragen über den gesamten Bereich.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> scores = {42, 88, 17, 95, 63, 71};

    int passed = count_if(scores.begin(), scores.end(),
                          [](int s) { return s >= 60; });

    bool allPositive = all_of(scores.begin(), scores.end(),
                              [](int s) { return s > 0; });

    bool anyPerfect = any_of(scores.begin(), scores.end(),
                             [](int s) { return s == 100; });

    cout << passed << " passed\n";          // 4 bestanden
    cout << "all positive? " << allPositive << "\n";  // 1
    cout << "any perfect? " << anyPerfect << "\n";    // 0
    return 0;
}

std::count (ohne _if) ist der einfachere Verwandte, der einen exakten Wert statt einer Bedingung zählt. Greife zu den Prädikat-Varianten, sobald deine Prüfung „alles, was einer Regel entspricht" lautet statt „dieser bestimmte Wert".

Einen Bereich transformieren und reduzieren

Zwei Arbeitspferde decken den Großteil der Datenverarbeitung ab: std::transform bildet jedes Element durch eine Funktion ab, und std::accumulate (aus <numeric>, nicht aus <algorithm>) faltet einen Bereich zu einem einzelnen Wert zusammen.

transform schreibt seine Ergebnisse über einen Ausgabe-Iterator. Ein häufiger und gefährlicher Fehler ist, die Ausgabe auf einen leeren vector zu richten - der Algorithmus nimmt an, dass bereits Platz existiert, und schreibt über das Ende hinaus. Dimensioniere entweder das Ziel zuerst oder verwende einen back_inserter, damit jedes Ergebnis per push_back angehängt wird.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3, 4};
    vector<int> squares;   // leer - noch kein Platz

    // back_inserter lässt `squares` wachsen, während die Ergebnisse eintreffen
    transform(nums.begin(), nums.end(), back_inserter(squares),
              [](int n) { return n * n; });

    for (int s : squares) cout << s << " ";  // 1 4 9 16
    cout << "\n";
    return 0;
}

accumulate startet von einem Anfangswert und kombiniert die Elemente von links nach rechts. Der Typ des Anfangswerts ist entscheidend: Übergib 0 (ein int), und die Summe wird in int berechnet, was überlaufen oder abschneiden kann.

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main() {
    vector<double> prices = {9.99, 4.50, 19.95};

    // Beginne mit 0.0 (double), damit die laufende Summe ein double bleibt.
    double total = accumulate(prices.begin(), prices.end(), 0.0);

    cout << "total: " << total << "\n";  // total: 34.44
    return 0;
}

Hättest du accumulate(prices.begin(), prices.end(), 0) mit einem int-Startwert geschrieben, würde jede Addition in int erfolgen und die Cent-Beträge verschwänden. Der Typ des Startwerts bestimmt stillschweigend den Ergebnistyp.

Das erase-remove-Idiom

Hier ist die Stolperfalle, die jeden überrascht. std::remove entfernt nichts aus dem Container. Algorithmen haben nur Iteratoren, also können sie die Größe eines Containers nicht ändern - sie wissen nicht einmal, dass überhaupt ein Container existiert. Was remove tatsächlich tut, ist, alle beibehaltenen Elemente nach vorn zu verschieben, das Ende in einem nicht spezifizierten Zustand zu lassen und einen Iterator auf das neue logische Ende zurückzugeben.

// remove allein lässt die Größe unverändert - das ist der Bug:
remove(v.begin(), v.end(), 0);  // gibt einen Iterator zurück, den du ignoriert hast
// v hat noch seine ursprüngliche Größe; das Ende ist Müll

Um die Elemente wirklich zu löschen, kombinierst du remove mit dem erase des Containers, weshalb es erase-remove-Idiom heißt:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 0, 7, 0, 1, 0, 9};

    // 1. remove schiebt die Nicht-Nullen nach vorn, gibt das neue Ende zurück
    // 2. erase schneidet alles von dort bis zum echten Ende ab
    v.erase(remove(v.begin(), v.end(), 0), v.end());

    for (int n : v) cout << n << " ";  // 3 7 1 9
    cout << "\n";
    return 0;
}

Verwende remove_if für ein Prädikat statt eines exakten Werts. In C++20 kannst du dir den ganzen Tanz mit den freien Funktionen std::erase / std::erase_if sparen, die beide Schritte für dich übernehmen: erase(v, 0);.

Iteratoren überleben ihre Gültigkeit auf eigene Gefahr

Da Algorithmen Iteratoren zurückgeben, unterliegen diese Iteratoren denselben Invalidierungsregeln, die du auf der vorherigen Seite kennengelernt hast. Einen Iterator zu speichern und dann den Container zu modifizieren - ein push_back, das eine Reallokation auslöst, oder ein erase - kann den gespeicherten Iterator baumelnd zurücklassen, und ihn zu verwenden ist undefiniertes Verhalten.

auto it = find(v.begin(), v.end(), 16);
v.push_back(99);   // kann den Speicher von v reallozieren
cout << *it;       // BUG: `it` zeigt nun möglicherweise auf freigegebenen Speicher

Die sichere Gewohnheit: Verwende den von einem Algorithmus zurückgegebenen Iterator sofort, vor jeder Operation, die den Container vergrößern oder reallozieren könnte. Wenn du den Container basierend auf einem Ergebnis verändern musst, erfasse stattdessen einen Index (it - v.begin()), da Indizes eine Reallokation überleben.

Als Nächstes: Sortieren

Du hast jetzt das Suchen, Zählen, Transformieren und Reduzieren gesehen - aber ein Algorithmus ist wichtig genug, um eine eigene Seite zu verdienen. std::sort ordnet einen Bereich an Ort und Stelle um, und sobald Daten sortiert sind, öffnet sich eine ganze Familie schnellerer, nur für sortierte Daten geeigneter Algorithmen (binary_search, lower_bound, equal_range). Als Nächstes gehen wir tief ins Sortieren: wie man einen eigenen Vergleicher bereitstellt, der Unterschied zwischen sort und stable_sort und die Regeln, die deine Vergleichsfunktion befolgen muss, um undefiniertes Verhalten zu vermeiden.

Häufig gestellte Fragen

Was ist der <algorithm>-Header in C++?

<algorithm> ist der Header der Standardbibliothek, der generische Funktionen wie std::find, std::sort, std::count_if und std::transform enthält. Sie arbeiten auf Bereichen, die durch ein Iterator-Paar beschrieben werden (üblicherweise begin() und end()), sodass derselbe Algorithmus auf einem vector, array, string oder jedem Container funktioniert, der Iteratoren bereitstellt.

Wie prüfe ich in C++, ob ein Wert in einem vector vorhanden ist?

Verwende std::find: auto it = find(v.begin(), v.end(), target);. Ist it == v.end(), ist der Wert nicht vorhanden; andernfalls zeigt it auf die erste Übereinstimmung. Um statt eines exakten Werts eine Bedingung zu prüfen, verwende std::any_of mit einem Prädikat.

Warum entfernt std::remove nicht wirklich Elemente aus meinem Container?

Algorithmen sehen nur Iteratoren, nicht den Container, daher kann std::remove ihn nicht verkleinern - es schiebt die beibehaltenen Elemente nach vorn und gibt einen Iterator auf das neue logische Ende zurück. Du musst es mit v.erase(...) ergänzen (das erase-remove-Idiom), um die Reste physisch zu entfernen.

Verwandte Konzepte