STL-Algorithmen: Die Kraft von <algorithm>

Meistere die wichtigsten STL-Algorithmen — vom Suchen und Sortieren bis zum Transformieren und Akkumulieren. Lerne, wie Algorithmen sich mit Iteratoren zu ausdrucksstarkem, effizientem Code komponieren lassen.

Der <algorithm>-Header

Der -Header enthält über 100 generische Algorithmen, die auf Iterator-Bereichen operieren. Diese Algorithmen verkörpern Jahrzehnte der Informatik — kampferprobt, optimiert und korrekt. Ihre Verwendung anstelle handgeschriebener Schleifen macht deinen Code kürzer, ausdrucksstärker und oft schneller.

Algorithmen sind in Kategorien organisiert:

- Nicht-modifizierend: find, count, search, all_of/any_of/none_of, equal, mismatch
- Modifizierend: copy, transform, fill, generate, replace, remove
- Sortierung & Ordnung: sort, stable_sort, partial_sort, nth_element
- Binäre Suche: lower_bound, upper_bound, binary_search, equal_range
- Numerisch (in ): accumulate, inner_product, partial_sum, iota

Jeder Algorithmus nimmt einen Iterator-Bereich [first, last) als primäre Eingabe.

Nicht-modifizierende Algorithmen

Nicht-modifizierende Algorithmen untersuchen Elemente, ohne sie zu ändern. Sie sind die Arbeitspferde für Abfragen und Validierung.

non_modifying.cpp

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

int main() {
    std::vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5};

    // find — returns iterator to first match (or end)
    auto it = std::find(nums.begin(), nums.end(), 5);
    if (it != nums.end()) {
        std::cout << "Found 5 at index " << std::distance(nums.begin(), it) << '\n';
    }

    // find_if — with a predicate
    auto even = std::find_if(nums.begin(), nums.end(),
                             [](int x) { return x % 2 == 0; });
    std::cout << "First even: " << *even << '\n';  // 4

    // count / count_if
    int fives = std::count(nums.begin(), nums.end(), 5);
    int odds  = std::count_if(nums.begin(), nums.end(),
                              [](int x) { return x % 2 != 0; });
    std::cout << "Fives: " << fives << ", Odds: " << odds << '\n';

    // all_of / any_of / none_of
    bool all_positive = std::all_of(nums.begin(), nums.end(),
                                    [](int x) { return x > 0; });
    bool has_negative = std::any_of(nums.begin(), nums.end(),
                                    [](int x) { return x < 0; });
    std::cout << std::boolalpha;
    std::cout << "All positive: " << all_positive << '\n';  // true
    std::cout << "Has negative: " << has_negative << '\n';  // false

    // equal — compare two ranges
    std::vector<int> nums2 = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    bool same = std::equal(nums.begin(), nums.end(), nums2.begin());
    std::cout << "Equal: " << same << '\n';  // true
}

Modifizierende Algorithmen

Modifizierende Algorithmen ändern Elementwerte oder ordnen Elemente innerhalb eines Bereichs neu an.

modifying_algorithms.cpp

#include <algorithm>
#include <vector>
#include <iostream>
#include <iterator>

int main() {
    std::vector<int> src = {1, 2, 3, 4, 5};

    // transform — apply a function to each element
    std::vector<int> squared;
    std::transform(src.begin(), src.end(), std::back_inserter(squared),
                   [](int x) { return x * x; });
    // squared: {1, 4, 9, 16, 25}

    // transform with two input ranges (binary transform)
    std::vector<int> b = {10, 20, 30, 40, 50};
    std::vector<int> sums;
    std::transform(src.begin(), src.end(), b.begin(),
                   std::back_inserter(sums),
                   [](int a, int b) { return a + b; });
    // sums: {11, 22, 33, 44, 55}

    // fill and generate
    std::vector<int> zeros(10);
    std::fill(zeros.begin(), zeros.end(), 42);  // all 42s

    int counter = 0;
    std::generate(zeros.begin(), zeros.end(),
                  [&counter]() { return counter++; });
    // zeros: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

    // remove-erase idiom (pre-C++20)
    std::vector<int> data = {1, 2, 3, 2, 4, 2, 5};
    auto new_end = std::remove(data.begin(), data.end(), 2);
    data.erase(new_end, data.end());  // actually shrinks the vector
    // data: {1, 3, 4, 5}

    // C++20: simpler
    std::erase(data, 3);
    // data: {1, 4, 5}

    // replace
    std::replace(data.begin(), data.end(), 4, 99);
    // data: {1, 99, 5}

    for (int x : data) std::cout << x << ' ';
    std::cout << '\n';
}

Sortier- und Ordnungsalgorithmen

Die STL bietet mehrere Sortieralgorithmen mit unterschiedlichen Kompromissen. std::sort ist das universelle Arbeitspferd (O(n log n) im Durchschnitt, Introsort), während partial_sort und nth_element effizienter sind, wenn du nur eine teilweise Ordnung brauchst.

sorting.cpp

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

struct Student {
    std::string name;
    double gpa;
};

int main() {
    std::vector<int> nums = {5, 2, 8, 1, 9, 3, 7, 4, 6};

    // sort — O(n log n), not stable
    std::sort(nums.begin(), nums.end());
    // nums: {1, 2, 3, 4, 5, 6, 7, 8, 9}

    // sort descending with comparator
    std::sort(nums.begin(), nums.end(), std::greater<int>{});
    // nums: {9, 8, 7, 6, 5, 4, 3, 2, 1}

    // stable_sort — preserves relative order of equal elements
    std::vector<Student> students = {
        {"Alice", 3.8}, {"Bob", 3.5}, {"Charlie", 3.8}, {"Diana", 3.5}
    };
    std::stable_sort(students.begin(), students.end(),
                     [](const Student& a, const Student& b) {
                         return a.gpa > b.gpa;  // descending GPA
                     });
    // Alice before Charlie (both 3.8) — relative order preserved

    // partial_sort — sort only the first k elements
    std::vector<int> data = {5, 2, 8, 1, 9, 3};
    std::partial_sort(data.begin(), data.begin() + 3, data.end());
    // First 3 are sorted: {1, 2, 3, ...rest unspecified}

    // nth_element — partition so the nth element is in its sorted position
    std::vector<int> vals = {5, 2, 8, 1, 9, 3, 7};
    std::nth_element(vals.begin(), vals.begin() + 3, vals.end());
    // vals[3] == 5 (the median), left side <= 5, right side >= 5

    // lower_bound / upper_bound — binary search on sorted data
    std::vector<int> sorted = {1, 2, 4, 4, 4, 7, 9};
    auto lo = std::lower_bound(sorted.begin(), sorted.end(), 4);  // first 4
    auto hi = std::upper_bound(sorted.begin(), sorted.end(), 4);  // past last 4
    std::cout << "Count of 4s: " << std::distance(lo, hi) << '\n';  // 3
}

Numerische Algorithmen (<numeric>)

Der -Header stellt Algorithmen für mathematische Berechnungen auf Bereichen bereit.

numeric_algorithms.cpp

#include <numeric>
#include <vector>
#include <iostream>
#include <functional>

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};

    // accumulate — fold/reduce with initial value
    int sum = std::accumulate(nums.begin(), nums.end(), 0);
    std::cout << "Sum: " << sum << '\n';  // 15

    // accumulate with custom operation (product)
    int product = std::accumulate(nums.begin(), nums.end(), 1,
                                  std::multiplies<int>{});
    std::cout << "Product: " << product << '\n';  // 120

    // inner_product — dot product
    std::vector<int> weights = {2, 3, 1, 4, 2};
    int dot = std::inner_product(nums.begin(), nums.end(),
                                 weights.begin(), 0);
    std::cout << "Dot product: " << dot << '\n';  // 1*2 + 2*3 + 3*1 + 4*4 + 5*2 = 37

    // partial_sum — running total
    std::vector<int> running;
    std::partial_sum(nums.begin(), nums.end(), std::back_inserter(running));
    // running: {1, 3, 6, 10, 15}

    // iota — fill with incrementing values
    std::vector<int> seq(10);
    std::iota(seq.begin(), seq.end(), 1);  // {1, 2, 3, ..., 10}

    // C++17: reduce (parallel-friendly version of accumulate)
    // int sum2 = std::reduce(nums.begin(), nums.end());  // same as accumulate for +

    for (int x : running) std::cout << x << ' ';
    std::cout << '\n';
}

Stolperfalle

std::remove entfernt Elemente nicht tatsächlich aus einem Container. Es verschiebt die "behaltenen" Elemente nach vorne und gibt einen Iterator auf das neue logische Ende zurück. Die tatsächliche Größe des Containers bleibt unverändert — du musst erase() aufrufen, um die nachfolgenden Elemente physisch zu entfernen:

std::vector<int> v = {1, 2, 3, 2, 4};
auto new_end = std::remove(v.begin(), v.end(), 2);
// v ist jetzt: {1, 3, 4, ?, ?} mit Größe immer noch 5
v.erase(new_end, v.end());  // JETZT ist die Größe 3

In C++20 erledigen std::erase(container, value) und std::erase_if(container, predicate) dieses Idiom in einem Aufruf. Bevorzuge diese, wenn verfügbar.

Best Practice

Algorithmen glänzen, wenn sie komponiert werden. Anstatt komplexe Schleifen zu schreiben, verkette Algorithmen miteinander:

// Sortierte eindeutige Elemente erhalten
std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());

// Nur gerade Zahlen kopieren, quadriert, in die Ausgabe
std::vector<int> result;
std::copy_if(v.begin(), v.end(), std::back_inserter(result),
             [](int x) { return x % 2 == 0; });
std::transform(result.begin(), result.end(), result.begin(),
               [](int x) { return x * x; });

Dieser Stil ist klar, korrekt und übertrifft oft handgeschriebene Schleifen, da Bibliotheksimplementierungen SIMD, verzweigungsfreien Code und andere Mikrooptimierungen verwenden.

Wichtigste Erkenntnisse

Der -Header stellt 100+ generische Algorithmen bereit, die mit jedem Iterator-Bereich funktionieren
std::sort ist O(n log n) Introsort; std::stable_sort bewahrt die Reihenfolge gleicher Elemente
std::transform ist das funktionale "map" — wendet eine Funktion auf jedes Element an
std::remove löscht nicht — verwende das Remove-Erase-Idiom oder C++20 std::erase_if
std::accumulate (aus ) ist die allgemeine Fold/Reduce-Operation
Bevorzuge Algorithmen gegenüber handgeschriebenen Schleifen — sie sind klarer, sicherer und oft schneller

Quiz — Teste dein Wissen

(20 XP)

1. Was gibt `std::remove` zurück?

2. Welchen Algorithmus würdest du verwenden, um zu prüfen, ob ALLE Elemente in einem Bereich ein Prädikat erfüllen?

3. Was ist die Zeitkomplexität von `std::nth_element`?

Zurück

Iteratoren: Der Klebstoff der STL

Weiter

Lambdas & funktionale Programmierung