1. Einführung
Wenn man mit Programmieren beginnt, möchte man gern an ein Märchen glauben: „es gibt einen Container, der schnell, bequem und immer richtig ist“. In Wirklichkeit ist die Standardbibliothek von C++ wie ein Satz Küchenmesser: eines schneidet Brot perfekt, ein anderes Fleisch, und das dritte ist eher ein Korkenzieher (und ja, man kann damit auch schneiden, aber das muss man später dem Ermittler erklären). Heute vergleichen wir drei sequentielle Container und lernen, die richtige Frage zu stellen: welche Operationen sind in meinem Szenario am häufigsten?
Wir sprechen über sequentielle Container — solche, bei denen die Elemente in einer bestimmten Reihenfolge stehen (erstes, zweites, drittes …), aber im Speicher unterschiedlich organisiert sind. Zu diesen Containern gehören in C++ zum Beispiel std::vector, std::deque, std::list (und noch andere, aber heute behandeln wir genau diese drei). Im Standard treten diese Container als eigene „Familien“ mit spezifischen Garantien auf.
Um nicht den Faden zu verlieren, halten wir die zentrale „Idee des Tages“ fest: die Wahl des Containers ist eine Frage des Kompromisses. An einer Stelle gewinnt man bei Einfügen, an anderer beim Durchlauf, an anderer beim Indexzugriff. Und kostenlos gibt es nur Käse in der Mausefalle — und selbst der ist nicht für die Maus kostenfrei.
2. std::vector: schnell, solange man nicht am Anfang einfügt
std::vector wird oft zum „Default-Container“ (und das ist in Ordnung). Er ist sehr CPU-freundlich: die Elemente liegen zusammenhängend im Speicher, deshalb ist das Durchlaufen aller Elemente in der Praxis häufig sehr schnell. Aber der vector hat auch eine typische Schwäche: wenn man Elemente am Anfang oder in der Mitte einfügt/entfernt, müssen die nachfolgenden Elemente „verschoben“ werden, als hätte man in Excel oben eine Zeile eingefügt und die ganze Tabelle würde nach unten rutschen.
Intuition zum vector
Bei std::vector<T> gibt es intern einen großen zusammenhängenden „Speicherbereich“ für die Elemente vom Typ T. Daraus folgen zwei zentrale Eigenschaften.
Erstens — schneller Indexzugriff: v[i] funktioniert in der Regel sehr schnell, weil das „i-te Element“ als „Startadresse + i * sizeof(T)“ berechnet werden kann.
Zweitens — Wachstum. Wenn ein vector voll wird, muss er manchmal einen neuen (meist größeren) Speicherbereich alloziieren und alle Elemente dorthin kopieren. In früheren Themen habt ihr schon reserve() kennengelernt, um die Anzahl solcher teuren Schritte zu verringern.
Kleine Visualisierung (sehr vereinfacht):
flowchart LR A["vector: ein zusammenhängender Block"] --> B["[0][1][2][3][4]..."]
Mini-Beispiel: Index und schnelles Durchlaufen
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{10, 20, 30};
std::cout << v[1] << '\n'; // 20
}
Dieses Beispiel wirkt sehr simpel, aber das Wesentliche ist: vector ist als „dynamisches Array“ gedacht — Indexierung ist natürlich und bequem.
Mini-Beispiel: Einfügen am Anfang
#include <vector>
int main() {
std::vector<int> v{2, 3, 4};
v.insert(v.begin(), 1); // Elemente werden nach rechts "verschoben"
}
Wir gehen jetzt nicht in die Details der Kosten und „was mit Iteratoren/Referenzen passiert“ — das ist Thema der nächsten Vorlesung. Merkt euch vorerst: insert nahe am Anfang eines vector ist potenziell teuer, weil Elemente verschoben werden müssen.
3. std::deque: Operationen an beiden Enden
Wenn vector ein Flur mit einer Tür ist (bequem, am Ende hinzuzufügen), dann ist deque ein Flur mit einer Tür vorne und hinten. Der Name sagt es schon: double‑ended queue. Er eignet sich hervorragend, wenn man oft an beiden Enden Elemente hinzufügen und entfernen möchte: push_front, push_back, pop_front, pop_back.
Dabei kann deque — im Gegensatz zu list — weiterhin Indexzugriff: d[i]. Intern ist er aber meist nicht als ein zusammenhängender Block organisiert, sondern als eine Reihe von Blöcken (vereinfacht dargestellt).
Vereinfachte Darstellung:
flowchart LR A["deque: Blöcke"] --> B["[ ][ ][ ]"] A --> C["[ ][ ][ ]"] A --> D["[ ][ ][ ]"]
Warum deque, wenn es vector gibt?
Weil es beim vector schmerzhaft ist, am Anfang schnell einzufügen, und genau dafür ist deque gemacht. In realen Aufgaben tritt häufig das Muster „Task-Queue“, „Message-Buffer“, „History der letzten Ereignisse“ auf, wo es natürlich ist, mit beiden Enden zu arbeiten.
Mini-Beispiel: Operationen an beiden Enden
#include <deque>
#include <iostream>
int main() {
std::deque<int> d{2, 3};
d.push_front(1);
d.push_back(4);
std::cout << d.front() << ' ' << d.back() << '\n'; // 1 4
}
Da ist keine Magie — die zentrale Rolle des deque ist: beide Enden sind „erstklassig“.
Wichtige Klarstellung
deque ist nicht per se ein „besserer vector“. Es ist ein eigener Kompromiss. In der Regel gibt er die perfekte Kontinuität des Speichers teilweise auf, um Operationen an beiden Enden zu erleichtern. Die detaillierten Auswirkungen auf die Performance durch Speicherstruktur besprechen wir in der Abschlussvorlesung, aber schon jetzt merkt euch: deque steht oft für „Komfort an den Enden“, während vector für „Dichte der Daten“ steht.
4. std::list: Knoten und Arbeiten per Position
std::list ist eine doppelt verkettete Liste. Stellt euch Perlenkette vor: jedes Element ist eine eigene Perle (Knoten), und jede Perle hat einen Verweis auf die vorherige und nächste. Im Gegensatz zu vector und deque müssen die Elemente einer Liste nicht zusammenhängend im Speicher liegen. Das nennt man einen node‑based Container: jeder Knoten wird normalerweise separat alloziert.
Schema auf die Schnelle:
flowchart LR A["[10]"] <--> B["[20]"] <--> C["[30]"]
Worin unterscheidet sich list von vector und deque?
Der wichtigste „psychologische“ Unterschied ist: list ist nicht über Indizes gedacht, sondern über Positionen.
std::list hat keinen operator[]. Nicht weil die STL-Autoren „vergessen“ hätten, sondern weil die Idee, schnell das i-te Element zu holen, schlecht zur Liste passt: um zum i-ten zu gelangen, muss man i Schritte entlang der Verweise gehen.
Dafür hat die list ihre Stärke: Einfügen/Löschen an einer bekannten Position (wenn man bereits einen Iterator hat) erfordert in der Regel kein Verschieben aller anderen Elemente. Auch hier bleiben wir bei der Intuition: „den Schwanz nicht verschieben“ — das ist der Kern.
Mini-Beispiel: Einfügen per Iterator
#include <list>
#include <iostream>
int main() {
std::list<int> lst{10, 30};
auto it = lst.begin();
++it; // Position zeigt auf 30
lst.insert(it, 20); // 20 vor 30 eingefügt
for (int x : lst) {
std::cout << x << ' ';
}
std::cout << '\n'; // 10 20 30
}
Der Iterator ist hier ein „Positionsmarker“. Die Liste ist besonders nützlich, wenn man oft „innerhalb“ einer Sequenz arbeitet und es wichtiger ist, schnell an einer Stelle einzufügen/zu löschen als schnell per Index zuzugreifen.
Denken über die O(1)-Einfügung — eine Falle
Anfänger hören oft: „in einer list ist Einfügen O(1)“ und schließen: „also ist list immer besser zum Einfügen“. Das ist nur die halbe Wahrheit. Einfügen kann schnell sein, wenn der Einfügeort bereits bekannt ist (man hat einen Iterator). Aber das „Finden des Ortes“ ist eine separate Kostenkomponente und erfordert oft einen linearen Durchlauf.
Merkregel:
„Position finden“ + „an Position einfügen“ = zwei unterschiedliche Aufgaben.
list beschleunigt die zweite Aufgabe, nicht notwendigerweise die erste.
5. Wie wählt man einen Container: Vergleich und Mini‑Szenarien
Vergleichstabelle
Wenn ihr das nächste Mal einen Container auswählt, ist es nützlich, eine kleine „Karte der Umgebung“ vor Augen zu haben. Wir machen sie so praxisnah wie möglich: nicht als Tabelle aus dem Standard, sondern als Spickzettel für Entwickler, die einmal versucht haben, eine Queue mit vector zu bauen und dann lange an die Decke gestarrt haben.
| Operation / Eigenschaft | |
|
|
|---|---|---|---|
| Indexzugriff c[i] | Ja, Stärke | Ja, normalerweise gut | Nein, konzeptionell „nicht dafür“ |
|
In der Regel sehr gut | Gut | Gut, aber nicht der Hauptgrund für die Wahl |
|
In der Regel schlecht (Verschiebungen) | Stärke | Gut |
| Einfügen/Löschen in der Mitte | In der Regel teuer (Verschiebungen) | In der Regel auch nicht ideal | In der Regel gut, wenn die Position bereits gefunden ist |
| Linearer Durchlauf „alle Elemente nacheinander“ | In der Regel sehr schnell | In der Regel ziemlich gut, aber weniger „dicht“ | Oft langsamer wegen verstreuter Knoten |
| Denkmodell | „Array + Wachstum“ | „Double-ended Queue“ | „Positionen‑Iteratoren, Knoten“ |
Diese Tabelle ist keine „mathematische Wahrheit für alle Zeiten“, sondern eine praktikable Näherung. Sie hilft jedoch sehr, den Container nicht „aus Stimmung“ auszuwählen. Und ja: die Standardbibliothek differenziert klar zwischen deque, list und vector als eigene Container mit eigenen Spezifikationen.
Mini‑Szenarien aus TaskKeeper
Bis hierhin haben wir hypothetisch die Konsolenanwendung TaskKeeper entwickelt: wir speichern Aufgaben, drucken Listen, filtern, sortieren, suchen nach Bedingungen. Für die meisten dieser Fälle ist std::vector<Task> eine ausgezeichnete Wahl, und ihr müsst euch nicht unnötig verkomplizieren, nur weil „es in C++ noch andere Container gibt“.
Aber es gibt Situationen, in denen ein anderer Container natürlicher klingt. Schauen wir uns drei Mini‑Szenarien an. Ziel ist nicht, die App umzuschreiben, sondern Situationen zu erkennen.
Für die Beispiele definieren wir ein einfaches Task-Modell:
#include <string>
struct Task {
int id{};
std::string title;
};
Szenario A: „Aufgabenliste“ — meist vector
Wenn ihr meist „alle Aufgaben anzeigen“, „sortieren“, „eine Schleife zum Drucken“, „suchen nach Bedingung“ macht, bleibt vector oft die einfachste und schnellste Wahl. In solchen Aufgaben sind Kompaktheit und Komfort der Algorithmen wichtig.
#include <iostream>
#include <vector>
int main() {
std::vector<int> ids{101, 102, 103};
for (int id : ids) {
std::cout << id << ' ';
}
std::cout << '\n'; // 101 102 103
}
Wichtig: linearer Durchlauf ist beim vector ein „natürliches Szenario“. Das werdet ihr am häufigsten tun.
Szenario B: „Ereigniswarteschlange“ — passt deque
Stellt euch vor, wir haben in TaskKeeper eine Ereignisverarbeitung: Nutzer gibt Befehle ein, und wir wollen eine „Queue von Befehlen zur Ausführung“ haben, wobei wir gelegentlich einen dringenden Befehl „vor die Queue“ setzen. Das ist genau ein Fall für Operationen an beiden Enden.
#include <deque>
#include <iostream>
#include <string>
int main() {
std::deque<std::string> q;
q.push_back("load");
q.push_front("help"); // dringend help anzeigen
std::cout << q.front() << '\n'; // help
}
Einfaches Konzept: deque ist praktisch, wenn „auch vorne etwas passiert“, nicht nur hinten.
Szenario C: „aktive Aufgaben und Verschiebungen“ — list möglich
Angenommen, wir haben eine Queue „aktiver Aufgaben“ und verschieben häufig eine Aufgabe aus der Mitte irgendwohin (z. B. ans Ende, weil die Aufgabe blockiert ist). Wenn ihr bereits einen Iterator auf die betreffende Aufgabe habt, kann eine Liste wegen der positionsbasierten Arbeit praktisch sein.
#include <list>
#include <iostream>
int main() {
std::list<int> active{1, 2, 3};
auto it = active.begin();
++it; // zeigt auf 2
active.erase(it); // 2 entfernt
std::cout << active.front() << '\n'; // 1
}
Beachtet: wir diskutieren hier nicht „was mit Iteratoren passiert“ oder „welche Garantien jeder Container bietet“. Das ist Thema der nächsten Vorlesung. Wichtig ist das Modell: in einer Liste denkt man eher in Iteratoren/Positionen als in Indizes.
6. Typische Fehler
Fehler Nr. 1: std::list wählen, nur weil „Einfügen O(1)“ falsch ist, und erwarten, die ganze Anwendung beschleunigt sich.
Das ist eine typische Falle: klingt wissenschaftlich, wirkt überzeugend, und am Ende stellt sich heraus, dass ihr trotzdem eine lineare Suche nach der Einfügeposition macht — und zusätzlich wird das Durchlaufen wegen schlechter Speicherlokalität unfreundlicher. Besser ist, die Aufgabe in zwei Teile zu zerlegen: zuerst überlegen, wie ihr die Position findet, und erst dann, wie ihr dort einfügt.
Fehler Nr. 2: versuchen, per Index auf std::list zuzugreifen, wie auf ein Array.
Manche gewohnheitsmäßig tippen lst[i], weil sie „das dritte Element“ wollen. list hat keinen operator[], und das ist eine ehrliche Warnung der STL: der Container ist nicht für „drittes Element in O(1)“ gedacht. Wenn ihr einen Index braucht, ist fast sicher vector oder deque passender.
Fehler Nr. 3: std::deque als „der selbe vector, nur besser“ betrachten.
deque unterstützt zwar Indexierung und Anhängen am Ende, aber seine Hauptrolle sind effiziente Operationen an beiden Enden. Wenn euer Szenario „vieles nacheinander lesen, selten ändern“ ist, dann ist vector oft einfacher und vorhersagbarer. Holt deque nur raus, wenn ihr wirklich push_front/pop_front braucht.
Fehler Nr. 4: den Container „vorsorglich“ optimieren, ohne ein Operationsprofil zu haben.
Man will gern im Voraus den „richtigsten“ Container wählen, aber der richtige Container hängt davon ab, was ihr am häufigsten macht: Iteration, Einfügen, Indexzugriff, Arbeiten an den Enden. Der vernünftige Ablauf ist: zuerst typische Operationen aufschreiben, dann den Container danach auswählen und erst danach Details optimieren.
Fehler Nr. 5: Denkmodelle vermischen: Daten wie in einem vector speichern, aber wie in einer Liste arbeiten.
Zum Beispiel viele Einfügungen am Anfang eines vector in einer Schleife durchführen und sich wundern, warum es langsam wird. Container „erziehen“ euer Codeverhalten: wenn ihr gegen ihre Natur arbeitet, rächen sie sich — still, ohne Warnung, einfach indem sie langsamer werden.
GO TO FULL VERSION