Benutzer:Koschi/Kontainer der STL
In der Spieleentwicklung ist es oft nötig, ein gewisse Menge an identischen Daten zu verwalten. Um die Verwaltung der Daten nicht nicht von Grund auf selber zu programmieren bietet die Standard Template Libary eine umfangreiche Sammlung an Kontainern, die das Verwalten der Daten erheblich erleichtert. Die Arbeitsweise und wofür die Verschiedenen Kontainer sind soll in diesem Artikel näher beschrieben werden.
Inhaltsverzeichnis |
Was ist ein Kontainer
Einen Kontainer kann man sich als Behältnis für Daten vorstellen, diese Daten werden auch Elemente genannt. Einen bekannter (nicht STL) Kontainer, den wohl jeder bereits kennt und benutzt hat, ist ein simples eindimenionales Array. Der Vorteil bei den STL Kontainer ist, dass die Anzahl der Elemente in den meinsten Fällen dynamisch wachsen können. Es spielt dabei keine Rolle ob diese Daten Structs, Klassen oder eines der Grunddatentypen sind. Wie das "Befüllen" mit Daten erfolgt, hängt aber vom Konatainer selber ab, da sich die Interne Datenstrukture von Kontainertyp zu Kontainertyp unterscheiden kann. Bedingt durch den Aufbau der Kontainer kann man diese in 3 Kategorien aufteilen:
- Sequentielle Kontainer
- Assoziative Kontainer
- Kontainer Adapter
Um die Verwaltung des benötigten Speichers, kümmern sich die Kontainer selber.
Sequentielle Kontainer
Die Daten in einem Sequentiellen Kontainer liegen in der Reihenfolge vor wie sie Eingefügt wurden. Das heist wurde ein Element als drittes hinzugefügt ist es auch später wieder an dieser stelle zu finden. Für Sequentielle Kontainer kann ein Iterator erstellt werde, der es ermöglicht alle Elemente des Kontainers über eine Schleife zu erreichen.
Zu den Sequentille Kontainer gehören:
- array
- deque
- forward_list
- list
- vector
Assoziative Kontainer
Die Assoziative Kontainer können weiter unterteilt werden in Map- und Set-Kontainer, sowie jeweils in eine multi Version. An welche Stelle im Kontainer die Elemente eingeordnet werden, kann über eine eigene Vergleichsfunktion bestimmt werden.
Mit C++11 wurden noch jeweils eine ungeordnete Versionen eingeführt. Ungeordnet heist in diesem Zusammenhang aber nur, dass nicht die Möglichkeit gegeben ist eine (eigene) Vergleichsfunktion einzusetzen. Intern arbeiten diese ungeordneten Kontainer mit Hashwerten, der Zugriff auf die Daten ist so wesentlich schneller. Es besteht aber die Möglichkeit einen eigenen Hash-Algorithmus einzusetzen, um die Reihenfolge der Daten festzulegen.
Der Zugriff auf ein Elemente kann bei allen Assoziative Kontainer über einen Schlüssel erfolgen. Die Map-Kontainer besitzen ein Schlüssel-Werte-Paar, Schlüssel und Wert können (müssen aber nicht) unterschiedliche Datentypen sein. Die Set-Kontainer besitzen lediglich den Schlüssel, der gleichzeitig auch den Wert darstellt. Der Schlüssel darf dabei nur einmalig im Kontainer vorkommen, es sei den es handelt sich um die multi Version, hier darf der Schlüssel mehrfach vorkommen.
Für Assoziative Kontainer kann ein Iterator erstellt werde, der es ermöglicht alle Elemente des Kontainers über eine Schleife zu erreichen.
Zu den Assoziative Kontainer gehören:
- map
- multimap
- unordered_map
- unordered_multimap
- set
- multiset
- unordered_set
- unordered_multiset
Kontaineradapter
Zu den Kontaineradapter gehören:
- priority_queue
- queue
- stack
Allgemeines
Alle Kontainer der Standard Template Libary befinden sich im Namensraum std.
Header
| Kontainer Name | array | deque | forward_list | list | vector |
|---|---|---|---|---|---|
| #include | <array> | <deque> | <forward_list> | <list> | <vector> |
| Kontainer Name | map | multimap | unordered_map | unordered_multimap | set | multiset | unordered_set | unordered_multiset |
|---|---|---|---|---|---|---|---|---|
| #include | <map> | <map> | <unordered_map> | <unordered_map> | <set> | <set> | <unordered_set> | <unordered_set> |
| Kontainer Name | priority_queue | queue | stack |
|---|---|---|---|
| #include | <queue> | <queue> | <stack> |
Laufzeitverhalten
| Kontainer Name | array | deque | forward_list | list | vector | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Beginn | Mitte | Ende | Beginn | Mitte | Ende | Beginn | Mitte | Ende | Beginn | Mitte | Ende | Beginn | Mitte | Ende | |
| Element zugriff | O(1) | O(1) | O(1) | N/A | O(1) | N/A | O(1) | O(1) | |||||||
| Element einfügen | N/A | O(1) | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) | O(n) | O(1) | |||||
| Element löschen | N/A | O(1) | O(n) | O(1) | O(1) | O(1) | O(n) | O(1) | |||||||
| Element finden | N/A | ||||||||||||||
| Kontainer Name | map | multimap | unordered_map | unordered_multimap | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Beginn | Mitte | Ende | Beginn | Mitte | Ende | Beginn | Mitte | Ende | Beginn | Mitte | Ende | |
| Element zugriff | O(log n) | O(log n) | O(1)+ | O(1)+ | ||||||||
| Element einfügen | O(log n) | O(log n) | O(1)+ | O(1)+ | ||||||||
| Element löschen | O(log n) | O(log n) | O(1)+ | O(1)+ | ||||||||
| Element finden | O(log n) | O(log n) | O(1)+ | O(1)+ | ||||||||
| Kontainer Name | set | multiset | unordered_set | unordered_multiset | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Beginn | Mitte | Ende | Beginn | Mitte | Ende | Beginn | Mitte | Ende | Beginn | Mitte | Ende | |
| Element zugriff | O(log n) | O(log n) | O(1)+ | O(1)+ | ||||||||
| Element einfügen | O(log n) | O(log n) | O(1)+ | O(1)+ | ||||||||
| Element löschen | O(log n) | O(log n) | O(1)+ | O(1)+ | ||||||||
| Element finden | O(log n) | O(log n) | O(1)+ | O(1)+ | ||||||||
| Kontainer Name | priority_queue | queue | stack | ||||||
|---|---|---|---|---|---|---|---|---|---|
| Größte Wert | nicht Größte Wert | Beginn | Mitte | Ende | Beginn | Mitte | Ende | ||
| Element zugriff | O(1) | N/A | O(1) | N/A | O(1) | O(1) | N/A | ||
| Element einfügen | O(log n) | N/A | O(1) | O(1) | N/A | ||||
| Element löschen | O(log n) | N/A | O(1) | N/A | O(1) | N/A | |||
| Element finden | N/A | ||||||||
