C++

Container-Adapter & spezielle Container

Lerne stack, queue, priority_queue und moderne Vokabeltypen wie span, string_view und optional kennen. Verstehe, wann Adapter deinen Code vereinfachen.

Was sind Container-Adapter?

Container-Adapter sind Wrapper um bestehende Container, die eine eingeschränkte Schnittstelle bieten. Sie erzwingen ein bestimmtes Zugriffsmuster, indem sie die vollständige Container-API verbergen:

- std::stack — LIFO (Last In, First Out), standardmäßig von deque unterstützt
- std::queue — FIFO (First In, First Out), standardmäßig von deque unterstützt
- std::priority_queue — Max-Heap, standardmäßig von vector unterstützt

Adapter bieten keine Iteratoren — du kannst nur auf das oberste/vorderste Element zugreifen. Diese Einschränkung ist beabsichtigt: Sie macht die Absicht des Codes klarer und verhindert versehentlichen Missbrauch.

Stack und Queue in Aktion

Stacks und Queues sind fundamentale Datenstrukturen, die beim Parsen, BFS/DFS, Rückgängig-Systemen und Aufgabenplanung verwendet werden.

stack_queue.cpp
#include <stack>
#include <queue>
#include <string>
#include <iostream>

// Check if parentheses are balanced using a stack
bool is_balanced(const std::string& expr) {
    std::stack<char> stk;
    for (char c : expr) {
        if (c == '(' || c == '[' || c == '{') {
            stk.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (stk.empty()) return false;
            char top = stk.top();
            stk.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return stk.empty();
}

int main() {
    std::cout << std::boolalpha;
    std::cout << is_balanced("({[]})") << '\n';   // true
    std::cout << is_balanced("({[}])") << '\n';   // false

    // Queue — BFS-style task processing
    std::queue<std::string> tasks;
    tasks.push("compile");
    tasks.push("link");
    tasks.push("run tests");

    while (!tasks.empty()) {
        std::cout << "Processing: " << tasks.front() << '\n';
        tasks.pop();   // removes from front
    }
}

Priority Queue (Heap)

std::priority_queue ist standardmäßig ein Max-Heap — top() gibt das größte Element zurück. Für einen Min-Heap verwende std::greater als Vergleichsfunktion.

priority_queue.cpp
#include <queue>
#include <vector>
#include <functional>
#include <iostream>
#include <string>

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

int main() {
    // Max-heap (default) — largest first
    std::priority_queue<int> max_heap;
    max_heap.push(30);
    max_heap.push(10);
    max_heap.push(50);
    max_heap.push(20);

    while (!max_heap.empty()) {
        std::cout << max_heap.top() << ' ';  // 50 30 20 10
        max_heap.pop();
    }
    std::cout << '\n';

    // Min-heap — smallest first
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
    min_heap.push(30);
    min_heap.push(10);
    min_heap.push(50);
    std::cout << "Min: " << min_heap.top() << '\n';  // 10

    // Custom comparator with lambda
    auto cmp = [](const Task& a, const Task& b) {
        return a.priority < b.priority;  // higher priority first
    };
    std::priority_queue<Task, std::vector<Task>, decltype(cmp)> task_queue(cmp);
    task_queue.push({3, "low priority"});
    task_queue.push({10, "critical"});
    task_queue.push({7, "medium"});

    while (!task_queue.empty()) {
        auto& t = task_queue.top();
        std::cout << "[" << t.priority << "] " << t.name << '\n';
        task_queue.pop();
    }
}

std::span — Nicht-besitzende Sicht auf zusammenhängende Daten (C++20)

std::span ist eine leichtgewichtige, nicht-besitzende Sicht auf eine zusammenhängende Folge von Elementen. Es ersetzt das fehleranfällige Muster, (Zeiger, Groesse)-Paare zu übergeben.

span_example.cpp
#include <span>
#include <vector>
#include <array>
#include <iostream>
#include <numeric>

// span accepts vector, array, C-array — anything contiguous
void print_stats(std::span<const int> data) {
    if (data.empty()) return;
    std::cout << "Size: " << data.size() << '\n';
    std::cout << "First: " << data.front() << '\n';
    std::cout << "Last:  " << data.back() << '\n';

    int sum = std::accumulate(data.begin(), data.end(), 0);
    std::cout << "Sum:   " << sum << '\n';

    // Subviews
    auto first3 = data.first(3);   // first 3 elements
    auto last2  = data.last(2);    // last 2 elements
    auto mid    = data.subspan(1, 3);  // 3 elements starting at index 1
}

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::array<int, 5> arr = {10, 20, 30, 40, 50};
    int c_arr[] = {100, 200, 300, 400, 500};

    print_stats(vec);     // works with vector
    print_stats(arr);     // works with array
    print_stats(c_arr);   // works with C-array
}

string_view und optional

std::string_view (C++17) ist eine nicht-besitzende, schreibgeschützte Referenz auf einen String. Es vermeidet die Kosten des Kopierens oder Allokierens von std::string für Funktionen, die nur lesen müssen:

void greet(std::string_view name) {  // kein Kopieren, keine Allokation
    std::cout << "Hello, " << name << '\n';
}
greet("world");               // funktioniert mit String-Literalen
greet(std::string{"world"});  // funktioniert mit std::string

std::optional (C++17) repräsentiert einen Wert, der vorhanden sein kann oder nicht — ein typsicherer Ersatz für "magische Werte" oder rohe Zeiger zur Anzeige von Abwesenheit:

std::optional<int> find_index(std::span<const int> data, int target) {
    for (int i = 0; i < data.size(); ++i)
        if (data[i] == target) return i;
    return std::nullopt;  // nicht gefunden
}
auto idx = find_index(vec, 42);
if (idx) std::cout << "Found at " << *idx << '\n';
std::cout << idx.value_or(-1) << '\n';  // -1 wenn leer
Stolperfalle

Da std::string_view und std::span nicht-besitzend sind, können sie leicht zu Dangling-Referenzen werden, wenn die zugrunde liegenden Daten zerstört werden:

std::string_view bad() {
    std::string temp = "hello";
    return temp;  // DANGLING -- temp wird am Ende des Gültigkeitsbereichs zerstört
}

Gib niemals einen string_view oder span auf eine lokale Variable zurück. Sie sind sicher für Funktions-Parameter (die Daten des Aufrufers überleben den Aufruf), aber gefährlich als Rückgabewerte, es sei denn, du kannst garantieren, dass die Quelle die Sicht überlebt.

Dasselbe gilt für std::span — es ist intern nur ein Zeiger und eine Größe, ohne Besitz-Semantik.

Best Practice

Verwende Container-Adapter, wenn du eine Disziplin erzwingen möchtest, wie auf Elemente zugegriffen wird:

- Verwende std::stack anstelle eines rohen deque oder vector, wenn nur LIFO-Zugriff sinnvoll ist. Das macht die Absicht offensichtlich und verhindert versehentlichen Direktzugriff.
- Verwende std::queue für FIFO-Verarbeitung (Aufgabenwarteschlangen, BFS).
- Verwende std::priority_queue für Scheduling, Dijkstras Algorithmus oder jedes Szenario, in dem du immer das Extremelement willst.

Wenn du Iteration, beliebige Größenabfragen oder Zugriff in der Mitte der Sequenz brauchst, verwende den zugrunde liegenden Container direkt.

Wichtigste Erkenntnisse
  • Container-Adapter (stack, queue, priority_queue) schränken die Schnittstelle ein, um Nutzungsdisziplin zu erzwingen
  • std::priority_queue ist standardmäßig ein Max-Heap — verwende std::greater für einen Min-Heap
  • std::span (C++20) bietet eine nicht-besitzende Sicht auf zusammenhängende Daten und ersetzt (Zeiger, Groesse)-Paare
  • std::string_view (C++17) vermeidet das Kopieren von Strings für schreibgeschützte Nutzung — aber achte auf Dangling-Referenzen
  • std::optional (C++17) ist der typsichere Weg, "möglicherweise kein Wert" darzustellen, ohne magische Sentinel-Werte
  • Nicht-besitzende Sichten (span, string_view) dürfen niemals die Daten überleben, auf die sie verweisen

Quiz — Teste dein Wissen

(15 XP)

1. Welcher Container-Adapter bietet FIFO-Verhalten (First In, First Out)?

2. Welchen Typ gibt `std::priority_queue<int>` standardmäßig von `top()` zurück?

3. Warum ist es gefährlich, einen `std::string_view` auf einen lokalen `std::string` zurückzugeben?

Zurück
Assoziative Container: map, set, unordered_map
Weiter
Iteratoren: Der Klebstoff der STL