📦 1. Sequenzielle vs. Assoziative STL-Container
Die C++ STL trennt Datenstrukturen und Algorithmen strikt über Iteratoren. Die Wahl des passenden Containers ist entscheidend für Cache-Lokalität und Zeitkomplexität:
#include <vector>
#include <unordered_map>
#include <set>
#include <string>
#include <iostream>
int main() {
// 1. std::vector: Dynamisches Contiguous Array (O(1) amortisiert, beste Cache-Lokalität)
std::vector<int> scores = {85, 92, 78, 99};
scores.push_back(95);
// 2. std::unordered_map: Hash-Tabelle für O(1) Key-Value Lookups
std::unordered_map<std::string, int> inventory;
inventory["health_potion"] = 10;
inventory["mana_potion"] = 5;
// 3. std::set: Selbstbalancierter Rot-Schwarz-Baum (O(log N), sortiert & dedupliziert)
std::set<std::string> tags = {"cpp", "systems", "cpp", "performance"};
// tags enthält: {"cpp", "performance", "systems"}
}Ein std::vector ist wie ein durchgehendes Förderband: Pakete liegen direkt hintereinander im Speicher, was der CPU blitzschnellen Cache-Zugriff ermöglicht. Eine std::unordered_map ist wie ein automatisierter Barcode-Scanner: Barcode einlesen, Fach sofort finden! Ein std::set ist das alphabetische Register am Eingang.
⚡ 2. Mächtige STL-Algorithmen (<algorithm> & <numeric>)
Schreibe keine manuellen for-Schleifen, wenn die STL optimierte, ausgetestete Algorithmen bereitstellt:
#include <algorithm>
#include <numeric>
#include <vector>
#include <iostream>
struct Player {
std::string name;
int score;
};
int main() {
std::vector<Player> players = {{"Alice", 350}, {"Bob", 500}, {"Charlie", 420}};
// 1. Sortieren mit Lambda-Comparator
std::sort(players.begin(), players.end(), [](const Player& a, const Player& b) {
return a.score > b.score; // Absteigend sortieren
});
// 2. Suchen mit std::find_if
auto it = std::find_if(players.begin(), players.end(), [](const Player& p) {
return p.name == "Bob";
});
// 3. Akkumulieren mit std::accumulate
int total_score = std::accumulate(players.begin(), players.end(), 0,
[](int sum, const Player& p) { return sum + p.score; });
}📑 3. Cheat-Sheet: STL Container & Komplexität
| Container | Zugriff (Lookup) | Einfügen (Insert) | Vorteile & Systems-Einsatz |
|---|---|---|---|
std::vector<T> |
O(1) via Index |
O(1) am Ende (amortisiert) |
Standard-Wahl: Beste Hardware-Cache-Nutzung |
std::unordered_map<K, V> |
O(1) (Avg) |
O(1) (Avg) |
Schnellste Key-Value Assoziation (Hash-Table) |
std::set<T> |
O(log N) |
O(log N) |
Sortierte Unikate (Rot-Schwarz-Baum) |
std::deque<T> |
O(1) via Index |
O(1) an Front & Back |
Double-Ended Queue ohne Reallokationskosten |
🎯 Aufgaben & Checkliste in aufgabe.cpp
reserve() verwenden!Wenn du vorab weißt, wie viele Elemente in einen std::vector eingefügt werden, rufe immer vec.reserve(n) auf. Das verhindert wiederholte teure Reallokationen und Memory Copying auf dem Heap!