C++/Tutorial: 19. Standardbibliothek: Container

Aus Scientia
Version vom 6. April 2011, 07:34 Uhr von Alexis Hiemis (Diskussion | Beiträge)

(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Wechseln zu: Navigation, Suche

Container, ein Deja vu? Nein, wir haben zwar bereits früh den std::vector Container kennen gelernt, aber über die Fähigkeiten, die ein Array auch hat sind wir kaum hinaus gegangen. Dazu kommen noch eine ganze Reihe anderer Container und generischen Algorithmen, die dafür sorgen, dass die Container den größten Teil der C++ Standardbibliothek ausmachen. Wer sich C++ Programmierer schimpfen will, für den ist es unabdinglich ein gewisses Verständnis dieser Container zu haben(auch wenn es unter manchen Umständen sinnvoll ist auf sie zu verzichten, sollte man sie kennen). Bevor ich allerdings anfange verschiedene Container zu beschreiben, will ich erst noch einmal am Beispiel von std::vector arbeiten und damit das Konzept der Iteratoren und ihre Verwendung in den generischen Algorithmen vorstellen.

Iteratoren

Stellen wir uns einmal vor, wir haben ein normales int-Array arr und wollen durch alle Elemente iterieren um sie z.B. auszugeben. Die Größe des Arrays muss uns ja bekanntlich bekannt sein, nehmen wir also an, sie sei in size gespeichert. 

for(size_t i(0); i < size; ++i)
  cout << arr[i];

Nun, das ist nichts unbekanntes und für vector(nehmen wir als Beispiel mal einen vector<int> vec) machen wir es ja bisher genauso, nur dass diese ihre Größe kennen: 

for(size_t i(0); i < vec.size(); ++i)
  cout << vec[i];
.

Für Arrays können wir aber bereits auf eine andere Weise durch Objekte iterieren und zwar nehmen wir dazu einen Pointer, der auf das erste Element zeigt und einen Pointer, der hinter das letzte Element des Arrays zeigt. Der Pointer auf das erste Element ist, wie wir wissen, arr selbst, dementsprechend ist der Pointer auf das letzte Element (arr + size): 

for(int const* p(arr); p != (arr + size); ++p)
  cout << *p;

Und genau das können wir mit vector auch machen, nur dass wir anstelle eines Pointers ein iterator Objekt verwenden, das sich jedoch in dem Fall semantisch identisch verhält. Wir benötigen einen Iterator auf das erste Element, diesen bekommen wir mit vec.begin() und einen hinter das letzte Element, diesen bekommen wir mit vec.end(). 

for(vector<int>::const_iterator itr(vec.begin()); itr != vec.end(); ++itr)
  cout << *itr;

Iteratoren dienen also als eine Art von Zeigern, die auf Elemente von Containern verweisen, aber wozu der Mist? Die letzte Zeile ist schließlich länger als alle vorhergehenden?
Nun, der Zugriff über den Index ist bei Arrays und vector problemlos möglich, aber die meisten Container verfügen über keinen Wahlfreien Zugriff mit fortlaufend nummerierten Indices, die erste Variante funktioniert also nur spezifisch für diese Container. Iteratoren hingegen funktionieren auf allen Containern und Code, der mit Templates arbeitet, kann durch Iteratoren so geschrieben werden, dass er auf jedem beliebigen Container funktioniert und hier kommen die generischen Algorithmen der Standardbibliothek ins Spiel. C++ bietet uns eine ganze Reihe von Funktionen, mit denen wir eine Menge mit unseren Containern machen können und diese sind völlig unabhängig vom Typ des Containers. Sogar Arrays können verwendet werden, da überall wo Iteratoren akzeptiert werden, auch Pointer akzeptiert werden. Anders ausgedrückt handelt es sich bei den Pointern in unserem dritten Beispiel tatsächlich schon um Iteratoren.
Bevor ich zu den Algorthmen komme möchte ich allerdings zunächst einmal auf die verschiedenen Arten von Iteratoren eingehen. Jeder Container hat einen Typ, oder genauer gesagt zwei Typen von iteratoren, die über die statischen Member iterator und, wie in unserem Beispiel, const_iterator angesprochen werden. const_iterator entspricht dabei, wie der Name schon sagt, immer einem konstantem Iterator, das heißt wir können die Elemente über den Iterator nicht modifizieren, *itr = 2 wäre damit nicht möglich. iterator hingegen ist für konstante Container ebenfalls ein konstanter Iterator, für nicht konstante Container hingegen ein Iterator, der die Veränderung der Elemente erlaubt.
Damit haben wir die Iteratoren schon einmal in 2 Arten eingeteilt, dennoch kann nicht jeder iterator und nicht jeder const_iterator das selbe. Die Fähigkeiten hängen hingegen von dem Container ab, für den dieser Iterator ist. Die Verwendung des Operators ++ erlaubt jeder Iterator, unser Code würde also auch mit jedem Container funktionieren. Nicht jeder Iterator muss aber bidirektional sein, --itr muss nicht auf jeden Iterator funktionieren. Die größere Beschränkung ist jedoch der Wahlfreie Zugriff. Als wahlfreien Zugriff bezeichnet man die Möglichkeit jederzeit auf jedes Element des Containers unmittelbar zuzugreifen, wie z.B. bei std::vector durch den [] Operator und diese Möglichkeit spiegelt sich auch in den Iteratoren wieder. Wir können einem vector<int>::const_iterator beliebige Zahlen aufaddieren und den Iterator so umherspringen lassen, z.B. itr + 3. Die meisten Container erlauben dies jedoch nicht, wir können also nur ++ und -- oder sogar nur ++ auf sie verwenden.
Ebenfalls noch interessant ist die Möglichkeit Iteratoren zu kreieren, die rückwärts durch den Container iterieren, dazu dienen die Memberfunktionen rbegin rend, die Iteratoren von den Membertypen reverse_iterator und const_reverse_iterator zurückgeben, um den Vector rückwärts auszugeben müsste der Code demnach so aussehen: 

for(vector<int>::const_reverse_iterator itr(vec.rbegin()); itr != vec.rend(); ++itr)
  cout << *itr;

Algorithmen

Nun zu den Algorithmen, was können wir eigentlich mit ihnen machen? Die generischen Algorithmen der Standardbibliothek ermöglichen es uns viele Dinge zu vereinfachen, Dinge, die wir ansonsten immer wieder wiederholen würden zu abstrahieren. Nun wir können die Algorithmen zum Beispiel verwenden um die Elemente eines Containers auszugeben. Es würde den Rahmen dieses Tutorials sprengen alle Algorithmen zu beschreiben, eine vollständige Übersicht finden wir hier: http://www.cplusplus.com/reference/algorithm/. Suchen wir also einen, der für die Ausgabe geeignet sein könnte und gleich die erste Funktion in der Liste ist für uns geeignet. std::for_each führt eine Funktion auf jedes Element eines Bereiches aus. Gehen wir zunächst einmal auf den Bereich ein: die Standardalgorithmen nutzen Iteratorenpaare um Bereiche abzustecken, das ist flexibler als auf dem ganzen Container zu operieren, dennoch wollen wir den ganzen Container ausgeben, also nehmen wir auch den ganzen Bereich von vec.begin() zu vec.end(). Das sind die ersten beiden Parameter. Als dritten Parameter nimmt for_each eine Funktion, die für jedes Element in diesem Bereich einmal (mit dem Element als Parameter) aufgerufen wird. Wir brauchen also eine Funktion, die ein int nimmt und dieses ausgibt, die Mittel dazu haben wir bereits: 

function<int> cout_int(bind((ostream&(ostream::*)(int))(&ostream::operator<<), &cout, _1));

Wir nehmen also einen Funktionszeiger auf die Überladung von ostream::operator<<, die ein int nimmt und binden das an cout. Das einzige was nun noch fehlt ist for_each selbst, dieses wird im Header <algorithm> deklariert. Okay, geben wir also alle Elemente eines vectors aus: 

function<int> cout_int(bind((ostream&(ostream::*)(int))(&ostream::operator<<), &cout, _1));
for_each(vec.begin(), vec.end(), cout_int);

oder etwas unleserlicher auch in einer Zeile möglich: 

for_each(vec.begin(), vec.end(), bind((ostream&(ostream::*)(int))(&ostream::operator<<), &cout, _1));

An dieser Stelle sehen wir auch ein Problem der Algorithmen der Standardbibliothek: es ist zwar nur ein Funktionsaufruf, aber dennoch ist dieser nicht kürzer, dafür aber weniger leserlich als eine Schleife zur Ausgabe zu verwenden.
Schauen wir uns noch ein paar andere Algorithmen an. for_each ist ein Algorithmus, der zwar auf einem Container operiert, allerdings nichts in diesem verändert, und auch sonst nichts tut. Bisher haben wir einfach angenommen, das vec existiert, nun wollen wir vec einmal erzeugen und zwar bestehend aus 10 Zufallszahlen zwischen 0 und 10!
Die Funktion, die wir brauchen heißt generate. generate nimmt wie auch for_each einen Funktor, der aber in dem Fall nicht auf die Elemente des Containers aufgerufen wird, sondern einfach Parameterlos immer wieder aufgerufen wird und die Ergebnisse den Elementen im angegebenen Bereich zugewiesen werden. generate gibt es in 2 Varianten: einmal generate selbst, die Funktion nimmt wie auch for_each zwei Iteratoren um einen Bereich abzustecken und weist in diesem Bereich jedem Element einen Wert zu, der von dem angegebenem Funktor errechnet wurde und generate_n, die Funktion gibt einen Iterator an, wo der Bereich beginnt und ein size_t für die Größe des Bereiches. Wir verwenden einfach mal das normale generate.
Okay, erzeugen wir also erst einmal ein vector, das groß genug ist unsere Zufallszahlen zu fassen: 

vector<int> vec(10);

Nun initialisieren wir unsere Zufallszahlen: 

srand(time(NULL));

Nun brauchen wir eine Funktion, die Zufallszahlen zwischen 0 und 10 generiert, wir können dazu nicht einfach bind verwenden, sondern benötigen eine Hilfsfunktion, z.B. 

int rand_in(int min, int max)
  {
  return min + rand() % max;
  }

Nun können wir mit bind(rand_in, 0, 10) eine Funktion erzeugen, die Zufallszahlen im Bereich von 0 bis 10 erzeugt und können damit mit generate unser vector bestücken: 

generate(vec.begin(), vec.end(), bind(rand_in, 0, 10));

Und haben nun ein vector mit 10 Zufallszahlen im Bereich von 0 bis 10.
Wir könnten diese Zufallszahlen nun mit den Algorithmen noch modifizieren und zum Beispiel sortieren, dazu verwenden wir die sort Funktion auf den Bereich. sort ist ein Beispiel für eine Funktion die nicht zwingend einen Funktor als Parameter nimmt, sie kann zwar als dritten Parameter eine Funktion zum Vergleichen nehmen, aber per Default wird mit dem < Operator verglichen und da dieser für unsere Zahlen definiert ist müssen wir nur einen Bereich angeben: 

sort(vec.begin(), vec.end());

Wir können mit den Algorithmen auch z.B. alle ungeraden Zahlen rausfiltern. Die Funktion remove_if nimmt einen Bereich und ein Predikat(ein Funktor, der bool zurückgibt), verschiebt alle Werte für die das Predikat true zurück gibt an den Schluss und gibt dann einen Iterator auf das neue Ende zurück.
Zunächst brauchen wir also eine Hilfsfunktion: 

bool is_odd(int n)
  {
  return n % 2 != 0;
  }
vector<int> end(remove_if(vec.begin(), vec.end(), is_odd));

Wir können nun entweder einen neuen Container erstellen, dazu müssten wir einfach den Bereich des alten angeben aus dem der neue erstellt(kopiert) werden soll: 

vector<int> vec2(vec.begin(), end);

oder wir arbeiten mit dem end Iterator einfach weiter.
Nach unseren Spielereien sieht das Programm nun folgendermaßen aus: 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <tr1/functional>
 
using namespace std;
using namespace std::tr1;
using namespace std::tr1::placeholders;
 
int rand_in(int min, int max) 
  {
  return min + rand() % max;
  }
 
bool is_odd(int n) 
  {
  return n % 2 != 0;
  }
 
int main() 
  {
  vector<int> vec(10);
  srand(time(NULL));
  generate(vec.begin(), vec.end(), bind(rand_in, 0, 10));
 
  function<void (int)> print_int(bind((ostream&(ostream::*)(int))(&ostream::operator<<), &cout, _1));
  cout << "generated values:" << endl;
  for_each(vec.begin(), vec.end(), print_int); 
 
  sort(vec.begin(), vec.end());
  cout << "\nsorted values:" << endl;
  for_each(vec.begin(), vec.end(), print_int);
 
  vector<int>::iterator end(remove_if(vec.begin(), vec.end(), is_odd));
  cout << "\nfiltered values:" << endl;
  for_each(vec.begin(), end, print_int);
  }

und kann z.B. folgende Ausgabe erzeugen: 

generated values:
0626631178
sorted values:
0112366678
filtered values:
026668

Mit den Algorithmen kann man noch viel mehr machen, aber das gibt einen Vorgeschmack darauf, wie mächtig sie sein können. Im nächsten Punkt möchte ich die Container an sich einmal vorstellen.

Container

vector

Einen Container kennen wir schon: std::vector. Nunja, eigentlich kennen wir ihn nur sehr oberflächlich, wir haben ihn bisher nur wie ein Array verwendet, er kann allerdings noch ein wenig mehr. Bevor ich darauf eingehe möchte ich das vector als Array allerdings noch einmal genauer spezifizieren: vector als Container ist der, den man wohl am häufigsten braucht und die Anwendungsfälle sind identisch mit denen eines Arrays. Auch garantiert der Standard für diesen Container als einziges, dass er intern einen zusammenhängenden Speicherbereich belegt, das heißt intern durch ein Array repräsentiert wird. Das bringt uns einen Vorteil, wenn wir mit (C-)Bibliotheken arbeiten, die noch rohe Arrays als Parameter nehmen: wir können trotzdem mit vector arbeiten, denn da intern ein Array verwendet wird können wir dieses auch bekommen und zwar mit dem simplen Trick &vec[0].
Es ist allerdings nicht garantiert, dass dieses Array auch gültig bleibt, denn vector kann sein internes array verschieben. Dies ist auch notwendig, da ein vector nicht von einer festen Größe ist, die Größe kann verändert werden. Wir können z.B. dem vector ein Element hinten anfügen, indem wir die push_back Methode verwenden: 

vector<int> vec(2, 2); //Vektor: {2,2}
vec.push_back(3); //Vektor: {2,2,3}

Mit pop_back() können wir das letzte Element wieder entfernen und mit back() auf das letzte Element zugreifen(mit front() auf das erste) Wir können die Größe auch direkt verändern, indem wir die Methode resize verwenden: 

vector<int> vec(2, 2); //Vektor: {2,2}
vec.resize(4); //Vektor: {2,2,0,0}
vec.resize(1); //Vektor: {1}

Wenn wir einen vector vergrößern muss das interne Array unter Umständen neu angelegt werden, aus diesem Grund ist das verändern der Größe eines vectors insbesondere für große vectoren sehr langsam. Um dem entgegen zu wirken kennt vector das Prinzip der Kapazität. Das interne Array, der reservierte Speicher also kann größer gehalten werden als die aktuell benötigte Größe. Die Kapazität setzen wir mit der Funktion reserve. Nehmen wir also einmal ein vector, dem wir mit push_back dann 30 Elemente anfügen, einmal "langsam": 

vector<int> vec;
for(int i(0); i < 30; ++i)
  vec.push_back(i);

und einmal schnell: 

>
vector<int> vec;
vec.reserve(30);
for(int i(0); i < 30; ++i)
  vec.push_back(i);

Die Kapazität lässt sich auch mit der Memberfunktion capacity() abfragen. capacity() gibt also den reservierten Speicher zurück, size() nur die tatsächliche Größe des vectors.
Charakteristisch für vector ist der wahlfreie Zugriff mit dem [] Operator, dieser ist ähnlich dem Zugriff auf ein Array, es gibt (aus Performancegründen) keine Überprüfung ob über die vectorgrenzen hinaus gelesen oder geschrieben wird, was einen Fehler, genauer gesagt undefiniertes Verhalten zur Folge hätte. Mit der Methode at() können wir hingegen überprüfen lassen und im Fehlerfall wird eine out_of_range Exception geworfen. 

vector<int> vec(2);
vec[0] = 2; //unchecked
cout << vec[0] << endl; //unchecked
vec[2] = 1; //undefiniertes Verhalten
vec.at(0) = 2; //checked
cout << vec.at(0) << endl; //checked
vec.at(2) = 1; //out_of_range Exception wird geworfen

Für eine genaue Auflistung der Funktionen siehe hier vector eignen sich demnach wenn man jederzeit auf alle Elemente mit konstanter Geschwindigkeit zugreifen können will und die Größe des vectors relativ konstant bleibt.

vector<bool>

Ein besonderer Container ist vector<bool>. vector<bool> ist eine Templatespezialisierung und nicht einfach ein normaler vector mit bool Elementen. Der Unterschied ist, dass in vector<bool> jedes bool nur 1 Bit anstelle von einem byte als Speicherplatz einnimmt. Der Zugriff ist dafür etwas langsamer.

deque

Der Container, der vector am ähnlichsten ist, ist der std::deque Container, wie alle Container findet er sich in einem gleichnamigen Header, in dem Fall also <deque>.
Genau wie vector bietet auch std::deque einen wahlfreien Zufriff durch fortlaufende Indices, anders als vector wird ein deque allerdings intern nicht (immer) durch ein einzelnes Array repräsentiert (&deq[0] wäre demnach fatal) sondern kann seine Daten in verschiedenen Arrays als Chunks gruppieren. Für kleine Größen ist der Overhead von deque daher etwas größer als der von vector, dafür ist das Vergrößern bei großen deques nicht ganz so kostenspielig wie das vergößern großer vectors. Die Methoden, die deque bietet sind weitestgehend die selben, neben push_back und pop_back bietet deque allerdings noch dir Methoden push_front und pop_front, mit denen Elemente an den Anfang angefügt und von diesem entfernt werden können. 

deque<int> deq(2,2); //Deque: {2,2}
deq.push_front(3); //Deque: {3,2,2}
cout << deq[0] << endl; //3

list

Wie schon erwähnt, haben viele der Standardcontainer keinen wahlfreien Zugriff durch Indices, wie es bei vector oder deque der Fall ist. list ist ein Container, der als zugrunde liegende Datenstruktur eine doppelt verkettete Liste verwendet. Das heißt es wird kein Array verwendet, sondern Elemente die mit Pointern jeweils auf das nächste und auf das vorhergehende Element zeigen. Ein wahlfreier Zugriff wäre demnach auch sehr performancelastig, der Vorteil dieser Datenstruktur ist jedoch, dass sehr schnell an beliebiger Stelle Elemente eingefügt oder entfernt werden können. list ist demnach eine Datenstruktur die sich dann eignet, wenn wir nunja.. eine Liste brauchen, das heißt wenn wir wissen, dass wir die Elemente in der Datenstruktur immer nur in ihrer Reihenfolge(oder umgekehrten Reihenfolge) abarbeiten wollen.
Neben den bekannten Methoden push_back, push_front, pop_back und pop_front, die für list allerdings deutlich schneller sind, gibt es noch die Methoden insert und erase, die einen Iterator nehmen und hinter diesem Iterator ein Element einfügen und einen Iterator auf das neue Element zurückgeben, oder das Element an diesem Iterator entfernen. 

list<int> l; //list: {}
l.push_back(0); //list: {0}
l.push_back(1); //list: {0,1}
l.push_back(2); //list: {0,1,2}
l.insert(find(l.begin(), l.end(), 1), 3); //list: {0,1,3,2}
l.erase(remove_if(l.begin(), l.end(), is_odd), l.end()); //list: {0, 2}

map

Die vierte Datenstruktur, die ich hier vorstellen möchte, hat ebenfalls wahlfreien Zugriff, allerdings nicht mit Indices, wie bei vector oder deque, sondern mit keys. Es handelt sich bei std::map um eine Assoziative Datenstruktur, die intern als Suchbaum repräsentiert wird. Das heißt wir können beliebige Werte als key nehmen, der Typ des keys wird als erster Templateparameter angegeben, der Typ der Werte als zweites: 

map<string, int> m;
m["hi"] = 3;
m["heyo"] = 6;

Die Reihenfolge der Key-Value-Paare wird dabei nicht beibehalten, sondern ist immer nach keys sortiert. Auch auf map gibt es Iteratoren, die dann allerdings vom Typ std::pair<Key, Value> sind, wobei Key für den Keytypen und Value für den Valuetypen steht. In dem Fall würde ein Iterator also immer auf pair<string, int>s zeigen. Ein pair ist ein einfaches Hilfsmittel, das zwei Werte halten kann und kann mit der Funktion make_pair aus <utility> erzeugt werden. Mit den öffentlichen Membervariablen first und second können wir dann auf die beiden Elemente in dem pair zugreifen. Wollen wir die map also ausgeben, können wir das folgermaßen tun: 

for(map<string, int>::const_iterator itr(m.begin()); itr != m.end(); ++itr)
  cout << "Key: " << itr->first << " Value: " << itr->second << endl;

map bietet außerdem eine Memberfunktion find, die sich von der globalen find Funktion insofern unterscheidet, dass mit ihr speziell nach Schlüsseln gesucht werden kann. m.find("hi") liefert also einen Iterator auf das "hi", 3 Paar. m.find("ho"), welches nach einem Schlüssel sucht, der nicht in m vertreten ist würde einen Iterator auf m.end() zurückgeben. 

map<string, int>::iterator ho_element(m.find("ho"));
if(ho_element != m.end())
  cout << "ho hat den Wert " << ho_element->second << endl;
else
  cout << "ho wurde nicht in m gefunden" << endl;

Noch einmal zurück zum Anfang,
wenn m[k] nicht existiert wird es angelegt, das funktioniert natürlich nur, wenn auch ein parameterloser Konstruktor existiert. Da wir hier die map füllen ist es unwahrscheinlich, dass wir zuerst defaultobjekte erstellen und dann überschreiben, zum füllen der map ist daher die insert Memberfunktion sinnvoller, diese nimmt ein pair, sodass das ganze dann folgendermaßen aussieht. 

m.insert(make_pair("hi", 3));
m.insert(make_pair("heyo", 6));

Auch beim abfragen der Werte wollen wir oft nicht, dass in der map Elemente angelegt werden(zumal das schon beim kompilieren Probleme mit Objekten ohne parameterlosen Konstruktor und const correctness gibt), die Memberfunktion find schafft hier abhilfe. Sie gibt einen Iterator auf das Paar zurück bzw. m.end() wenn der gesuchte key nicht in der map vorhanden ist. Wollen wir also m["hi"]ausgeben, aber den Indexoperator nicht verwenden sähe das so aus: 

cout << m.find("hi")->second << endl; //der key "hi" muss! in m vertreten sein

map verwenden wir also immer dann, wenn wir immer 2 Dinge miteinander assoziieren wollen.

multimap

In einer normalen std::map können Werte logischerweise so oft vorkommen wie sie wollen, Schlüssel müssen aber eindeutig sein(ansonsten könnten wir auch nicht mit dem [] Operator darauf zugreifen). Ist das nicht erwünscht, so können wir std::multimap verwenden. multimap ähnelt map stark, bis auf, dass Schlüssel mehrmals vorkommen können und der [] Operator daher nicht verwendet werden kann. Anstattdessen müssen Werte ähnlich wie auch bei list mit insert eingefügt werden und dann mit find auf sie zugegriffen werden.

set und multiset

set ist englisch für Menge und genau das wird von diesem Container auch beschrieben. set wird ebenso wie map durch einen Baum repräsentiert und ist daher immer sortiert. Im Gegensatz zum Baum, wird aber nicht nach dem Schlüssel sortiert, sondern, da set auch nur Werte enthält, nach dem Wert. Ein Anwendungsfall von set ist daher auch als sortierte Liste. Eigentlich ist set allerdings dazu gedacht Elemente zu halten um Auskunft darüber zugeben, ob diese Werte enthalten sind. Wie auch bei list fügen wir die Elemente mit insert ein, ein Iterator muss dabei nicht angegeben werden: 

set<int> s; //set: {}
s.insert(3); //set:{3}
s.insert(5); //set:{3,5}
s.insert(2); //set:{2,3,5}
s.insert(6); //set:{2,3,5,6}

Mit erase können wir diese wieder entfernen: 

s.erase(6); //set:{2,3,5}

Nun können wir überprüfen ob Elemente in der Menge enthalten sind, dazu verwenden wir die Methode count: 

if(s.count(5))
  cout << "s enthält 5" << endl;
else
  cout << "s enthält die 5 nicht" << endl;

Der Name der Methode count lässt vermuten, dass in set Werte auch mehrmals enthalten sein können, aber das ist irreführend. set hat die Eigenschaft, dass alle Werte einmalig sind, ist das nicht erwünscht so verwendet man ein multiset, welches sich in genau diesem Punkt unterscheidet. Wenn wir auf Kapitel 8 zurückschauen, haben wir dort Statuseffekte mit Flags in Integern gespeichert und diese dann abgefragt. Stattdessen könnten wir die Statuseffekte z.B. auch in einem set speichern.

String

Der letzte Container der hier angesprochen werden soll ist string. Nun string kennen wir bereits, was bisher nur noch nicht deutlich wurde, ist dass es sich bei string ebenso um einen Container handelt. Nicht nur, dass auf die einzelnen chars mit dem []-Operator zugegriffen werden kann, auch definiert string die Iteratormethoden begin(), end(), rbegin() und rend() und ermöglicht es somit, die Algorithmen auch auf string anzuwenden.

Container Adapter

Einige Datenstrukturen treten zudem immer wieder auf, dazu gehören z.B. der stack und die queue. C++ definiert keine eigenen Container für diese 3(stack, queue und priority_queue) Strukturen, sondern definiert sogenannte Container Adapter, die nur die nötigen Methoden für die Datenstrukturen definieren und intern auf die Standardcontainer zurückgreifen(welche genau lässt sich per Templateparameter spezifizieren, muss aber nicht).

stack

der stack ist in dem Header <stack> definiert und heißt übersetzt Stapel und ist auch eine Datenstruktur, die auch genau so funktioniert. Nehmen wir an, wir haben einen Stapel und legen eine 2 darauf. Dann legen wir auf den Stapel eine 1. Wenn wir nun etwas von dem Stapel herunter nehmen ist es zuerst die 1 und dann die 2, womit die Funktionsweise von stack auch schon zusammengefasst wäre, denn stack bietet nur eine handvoll Methoden, die wichtigsten 3 sind:

  • push, mit dem wir ein Element auf den Stapel legen
  • top, mit dem wir auf das oberste Element des Stapels zugreifen
  • pop, mit dem wir das oberste Element vom Stapel entfernen. 
stack<int> s;
s.push(2);
s.push(1);
cout << s.top() << endl; //1
s.pop();
cout << s.top() << endl; //2
s.pop();

queue

queue befindet sich im Header <queue> und wird im Gegensatz zu stack nach dem first in, first out Prinzip gehandhabt. Neben den Methoden push und pop, die wie auch bei stack Elemente einfügen und entfernen gibt es die Methoden front und back um auf diese Elemente zuzugreifen, wobei front auf das nächste Element in der Schlange zugreift. 

queue<int> q;
q.push(2);
q.push(1);
cout << q.front() << endl; //2
q.pop();
cout << q.front() << endl; // 1
q.pop();

priority queue

Der letzte Container Adapter ist die sogenannte priority_queue. Auch die priority_queue befindet sich im Header <queue>, hat aber sonst nicht mehr mit der queue gemeinsam als mit dem stack. Die priority_queue ist sortiert, standardmäßig nach dem < Operator, sodass wir wie gehabt mit push Elemente einfügen, das Element, das wir mit top() dann allerdings abrufen nicht abhängig von der Reihenfolge ist, in der es eingefügt wurde, sondern schlicht das "größte" Element zuerst zurückgegeben wird: 

priority_queue<int> pq;
pq.push(1);
pq.push(3);
pq.push(2);
cout << pq.top() << endl; //3
pq.pop();
cout << pq.top() << endl; //2
pq.pop();
cout << pq.top() << endl; //1
pq.pop();
Von „https://www.rpg-studio.org/wiki/index.php?title=C%2B%2B/Tutorial:_19._Standardbibliothek:_Container&oldid=16656“