C++ STL Container

6 Container-Typen

Die wichtigsten Container der C++ Standard Template Library (STL): vector · array · list · map · set · stack / queue Die STL bietet eine Vielzahl von Containern für die Verwaltung von Daten – von dynamischen Arrays über assoziative Container bis zu Adaptern. Diese Cheatsheet fasst die wichtigsten zusammen.

vector – Dynamisches Array

#include <vector> · push_back · resize

#include <vector> std::vector<int> zahlen = {1, 2, 3}; zahlen.push_back(4); // [1, 2, 3, 4] std::cout << zahlen[0]; // 1

vector ist der vielseitigste Container der STL – ein dynamisches Array mit wahlfreiem Zugriff. Die Größe kann zur Laufzeit wachsen und schrumpfen.

Wichtige Methoden

Methode	Beschreibung	Komplexität
push_back(val)	Element am Ende hinzufügen	O(1) amortisiert
pop_back()	Letztes Element entfernen	O(1)
size()	Anzahl der Elemente	O(1)
capacity()	Reservierter Speicher	O(1)
reserve(n)	Speicher für n Elemente reservieren	O(n)
resize(n)	Größe auf n ändern	O(n)
at(index)	Zugriff mit Bereichsprüfung	O(1)
begin() / end()	Iteratoren für Schleifen	O(1)

Beispiele

#include <vector>

#include <iostream>

std::vector<std::string> namen;

namen.push_back("Anna");

namen.push_back("Ben");

namen.push_back("Clara");

// Range-based for-Schleife

for (const auto& name : namen) {

std::cout << name << std::endl;

}

// Zugriff mit [] und at()

std::cout << namen[0]; // "Anna"

std::cout << namen.at(2); // "Clara"

Tipp: Verwenden Sie reserve(), wenn Sie die ungefähre Größe kennen – das vermeidet mehrfache Speicher-Neuallokationen und verbessert die Performance.

array – Statisches Array (C++11)

#include <array> · std::array

#include <array> std::array<int, 5> zahlen = {1, 2, 3, 4, 5}; std::cout << zahlen.size(); // 5 std::cout << zahlen[0]; // 1

std::array ist ein Container mit fester Größe (zur Kompilierzeit bekannt). Er kombiniert die Performance von C-Arrays mit der Sicherheit der STL-Container.

Wichtige Methoden

Methode	Beschreibung
size()	Anzahl der Elemente (constexpr)
empty()	Prüft, ob Array leer ist (immer false)
at(index)	Zugriff mit Bereichsprüfung
begin() / end()	Iteratoren für Schleifen
fill(value)	Alle Elemente mit value befüllen
data()	Zeiger auf die zugrunde liegenden Daten

Beispiele

#include <array>

#include <iostream>

std::array<int, 3> a = {10, 20, 30};

// size() zur Kompilierzeit

constexpr int n = a.size(); // 3

// Iterieren

for (const auto& x : a) {

std::cout << x << " ";

} // 10 20 30

// Alle Elemente mit 99 befüllen

a.fill(99); // [99, 99, 99]

Tipp: Verwenden Sie std::array anstelle von C-Arrays int arr[5] – es bietet STL-Methoden, ist typsicherer und funktioniert mit allen STL-Algorithmen.

list – Doppelt verkettete Liste

#include <list> · push_front · push_back

#include <list> std::list<int> zahlen; zahlen.push_back(1); zahlen.push_front(0); // [0, 1] zahlen.insert(++zahlen.begin(), 99); // [0, 99, 1]

list ist eine doppelt verkettete Liste. Sie ermöglicht schnelle Einfügungen und Löschungen an beliebigen Positionen – jedoch keinen wahlfreien Zugriff.

Wichtige Methoden

Methode	Beschreibung	Komplexität
push_front(val)	Element am Anfang einfügen	O(1)
push_back(val)	Element am Ende einfügen	O(1)
pop_front()	Erstes Element entfernen	O(1)
pop_back()	Letztes Element entfernen	O(1)
insert(it, val)	Element an Position einfügen	O(1)
erase(it)	Element an Position löschen	O(1)
size()	Anzahl der Elemente	O(1)

Beispiele

#include <list>

#include <iostream>

std::list<std::string> todo;

todo.push_back("Einkaufen");

todo.push_front("Aufstehen");

todo.push_back("Lernen");

// Iterieren

for (const auto& task : todo) {

std::cout << task << std::endl;

}

// Erstes Element entfernen

todo.pop_front();

// Element an Position einfügen

auto it = todo.begin();

std::advance(it, 1); // Iterator auf zweites Element

todo.insert(it, "Mittagessen");

Tipp: list ist ideal, wenn Sie häufig an beliebigen Positionen einfügen/löschen. Für wahlfreien Zugriff verwenden Sie vector.

map – Sortierte Schlüssel-Wert-Paare

#include <map> · insert · find

#include <map> std::map<std::string, int> alter; alter["Anna"] = 30; alter.insert({"Ben", 25}); std::cout << alter["Anna"]; // 30

map ist ein assoziativer Container, der Schlüssel-Wert-Paare sortiert nach dem Schlüssel speichert. Jeder Schlüssel ist eindeutig.

Wichtige Methoden

Methode	Beschreibung	Komplexität
operator[](key)	Wert hinzufügen / abrufen (erzeugt Schlüssel)	O(log n)
insert({key, value})	Paar einfügen	O(log n)
find(key)	Such nach Schlüssel (gibt Iterator zurück)	O(log n)
erase(key)	Eintrag löschen	O(log n)
size()	Anzahl der Einträge	O(1)
begin() / end()	Iteratoren (sortiert nach Schlüssel)	O(1)

Beispiele

#include <map>

#include <iostream>

std::map<std::string, double> preise;

preise["Apfel"] = 0.99;

preise["Banane"] = 1.29;

preise.insert({"Orange", 0.79});

// Iteration (sortiert nach Schlüssel)

for (const auto& [name, preis] : preise) {

std::cout << name << ": " << preis << std::endl;

}

// Suche mit find

auto it = preise.find("Apfel");

if (it != preise.end()) {

std::cout << "Preis: " << it->second;

}

Tipp: Verwenden Sie find() statt operator[], wenn Sie nur prüfen möchten, ob ein Schlüssel existiert – operator[] erstellt einen neuen Eintrag, falls der Schlüssel fehlt.

set – Sortierte, eindeutige Elemente

#include <set> · insert · find

#include <set> std::set<int> zahlen; zahlen.insert(3); zahlen.insert(1); zahlen.insert(3); // wird ignoriert (doppelt) // zahlen = {1, 3}

set ist ein assoziativer Container, der eindeutige, sortierte Elemente speichert. Doppelte Einträge werden automatisch ignoriert.

Wichtige Methoden

Methode	Beschreibung	Komplexität
insert(value)	Element einfügen (doppelte werden ignoriert)	O(log n)
find(value)	Element suchen	O(log n)
erase(value)	Element löschen	O(log n)
size()	Anzahl der Elemente	O(1)
contains(value)	Prüft, ob Element existiert (C++20)	O(log n)

Beispiele

#include <set>

#include <iostream>

std::set<std::string> woerter;

woerter.insert("Hallo");

woerter.insert("Welt");

woerter.insert("Hallo"); // wird ignoriert

woerter.insert("C++");

// Ausgabe: C++, Hallo, Welt (sortiert)

for (const auto& w : woerter) {

std::cout << w << std::endl;

}

// Prüfen mit contains (C++20)

if (woerter.contains("Welt")) {

std::cout << "Welt ist enthalten";

}

Tipp: Verwenden Sie std::unordered_set für unsortierte, eindeutige Elemente mit O(1)-Zugriff (Hash-Tabelle). Die Reihenfolge ist dann nicht definiert.

Container Adapter – stack, queue, priority_queue

#include <stack> · #include <queue>

#include <stack> std::stack<int> s; s.push(1); s.push(2); std::cout << s.top(); // 2 s.pop(); // entfernt 2

Container Adapter bieten spezifische Schnittstellen für bestimmte Datenstrukturen – stack (LIFO), queue (FIFO) und priority_queue (priorisierte Warteschlange).

Die drei Adapter

Adapter	Beschreibung	Wichtige Methoden
stack	LIFO (Last-In-First-Out)	push, pop, top, empty, size
queue	FIFO (First-In-First-Out)	push, pop, front, back, empty, size
priority_queue	Warteschlange mit Priorität (größte zuerst)	push, pop, top, empty, size

Beispiele

// STACK

#include <stack>

std::stack<int> stapel;

stapel.push(10);

stapel.push(20);

std::cout << stapel.top(); // 20

stapel.pop(); // 20 entfernt

// QUEUE

#include <queue>

std::queue<std::string> warteschlange;

warteschlange.push("erster");

warteschlange.push("zweiter");

std::cout << warteschlange.front(); // "erster"

warteschlange.pop(); // "erster" entfernt

// PRIORITY_QUEUE

#include <queue>

std::priority_queue<int> pq;

pq.push(5);

pq.push(1);

pq.push(8);

std::cout << pq.top(); // 8 (größte Priorität)

pq.pop(); // 8 entfernt

std::cout << pq.top(); // 5

Tipp: priority_queue verwendet standardmäßig std::vector als zugrunde liegenden Container. Sie können den Container und die Vergleichsfunktion anpassen.

STL Container im Überblick

vector Dynamisches Array
Wahlfreier Zugriff

array Statisches Array
Feste Größe

list Doppelt verkettete Liste
Schnelle Einfügungen

map Schlüssel-Wert-Paare
Sortiert, eindeutig

set Eindeutige Elemente
Sortiert

stack LIFO-Adapter
push, pop, top

Quick Summary

vector

Dynamisches Array

array

Statisches Array

list

Verkettete Liste

map

Schlüssel-Wert

set

Eindeutige Werte

stack

Container Adapter

std::vector v = {1, 2, 3}; · std::map m; m["key"] = 42; · std::set s = {1, 2, 3};