Dragon
Super JLI'ler
Alter: 38
Anmeldedatum: 24.05.2004
Beiträge: 340
Wohnort: Sachsen
Medaillen: Keine
|
 Verfasst am: 27.08.2005, 19:18 Titel: [C++/STL] Teil 2: Assoziative Container und Containeradapter |
 |
|
Assoziative Container
map
Eine map ist eine Tabelle die Zeilen mit einem Schlüssel und einem dazugehörigen Wert enthält. Der Schlüssel darf nur einmal vorhanden sein. Wenn ein neuer Wert mit dem selben Schlüssel hinzugefügt wird, dann wird der alte mit dem neuen übeschrieben. Das besondere an diesem Container ist die Implementierung als Binärbaum. Beim hinzufügen eines Schlüssel-Wert-Paares wird dieses Paar in den Baum sortiert eingefügt. Jeder der schon mal eine Binärbaum genutzt hat weiß, dass diese ziemlich schnell sind.
Um die Containerklasse nutzen zu können müssen wir ersteinmal die Headerdatei <map> einbinden.
Jetzt erstellen wir einen Container. Als Beispiel nehme ich das klassiche Telefonbuch. In unserem Telefonbuch ist der Schlüssel der Name und die Telefonnummer der Wert. Klingt etwas kompliziert, ist aber ganz easy.
| CPP: | | std::map<std::string, int> telbuch; |
Die Containerklasse map bietet uns den []-Operator an. Mit ihm können wir Werte mit neuem Schlüssel hinzufügen, Werte eines Schlüssels abfragen(Vorsicht! wenn es den Schlüssel nicht gibt, dann gibt es eine Speicherzugriffsverletzung) und ändern. Aber erstmal fügen wir ein paar Datensätze in unser Telfonbuch hinzu.
| CPP: | telbuch["Polizei"] = 110;
telbuch["Notruf"] = 112;
telbuch["Maier"] = 1000;
telbuch["Bauer"] = 5494;
telbuch["Fischer"] = 3030; |
Die Anzahl der Elemente gibt uns, wer hätte es gedacht, die Methode size() zurück.
| CPP: | | std::cout << "Anzahl der Eintraege: " << telbuch.size() << std::endl << std::endl; |
Mit Iteratoren gehen wir unser Telefonbuch durch und geben es aus. Es gibt aber einen kleinen Unterschied z.B. zu dem durchgehen bei einer Liste. Unsere Iterator hat zwei Attribute. Einmal first für den Schlüssel und einmal second für den Wert. Wir wollen den Namen und die dazugehörige Telefonnummer ausgeben. Altbekanntes Spiel mit begin() und end()  .
| CPP: | // Iterator erzeugen
std::map<std::string, int>::iterator it;
// Alle Elemente ausgeben
for(it = telbuch.begin(); it != telbuch.end(); it++)
std::cout << "Name:\t" << (*it).first << "\tTel:\t" << (*it).second << std::endl; |
Wenn Sie dies nun testen, dann werden Sie sehen, dass die Liste Alphabethisch sortiert ausgegeben wird.
Die Containerklasse map stellt uns eine Methode zum suchen eines bestimmten Schlüssels zur verfügung. Der Methode find() übergeben wir den Schlüssel nach dem gesucht werden soll. Zurückgeben wird uns ein Iterator. Doch was ist, wenn die Suche fehlgeschlagen ist? Wenn dies passiert, dann zeigt der Iterator hinter das letzte Element der Liste. Wir müssen also einfach nur mit der Methode end() unseres Containers vergleichen.
| CPP: | std::string name;
std::cout << "Bitte Name eingeben: ";
std::cin >> name;
it = telbuch.find(name);
if(it != telbuch.end())
std::cout << "Suche erfolgreich. Ergebnis: " << (*it).second << std::endl;
else
std::cout << "Suche erfolglos" << std::endl; |
multimap
In einer multimap dürfen Schlüssel auch mehrmals vorkommen. Dadurch geht aber die Eindeutigkeit und somit einige bestimmte Funktionen verloren. Es gibt keinen []-Operator und keine Methode find() mehr. Ich bleib mal Beispiel beim Telefonbuch. Es kann ja vorkommen, das es Personen gibt, die den gleichen Namen haben.
Um die multimap nutzen zu können muss die Headerdatei <map> includiert sein.
Jetzt legen wir einen Container an. Dieser soll den Namen in einem std::string und die Telefonnummer in einem int.
| CPP: | | std::multimap<std::string, int> telbuch; |
Das einfügen ist etwas komplizierter als bei einer normalen map. Da uns der []-Operator nicht mehr zu verfügung steht müssen wir uns mit der Methode insert() begnügen. Da wir ein Schlüssel-Wert-Paar einfügen wollen, müssen wir pair nutzen. Da es eine Template ist, müssen wir die Datentypen in den spitzen Klammern <> angeben.
| CPP: | telbuch.insert(std::pair<std::string, int>("Maier", 1239));
telbuch.insert(std::pair<std::string, int>("Bauer", 7832));
telbuch.insert(std::pair<std::string, int>("Fischer", 2904));
telbuch.insert(std::pair<std::string, int>("Maier", 4032)); |
Wie Sie sehen fügen wir Maier mit zwei unterschiedlichen Telefonnummern hinzu. Die Ausgabe ist wie bei der „normalen“ map mit Iteratoren.
| CPP: | // Iterator erzeugen
std::multimap<std::string, int>::iterator it;
// Liste ausgeben
for(it = telbuch.begin(); it != telbuch.end(); ++it)
std::cout << "Name:\t" << (*it).first << "\tTel:\t" << (*it).second << std::endl; |
Bei der Ausgabe werden Sie sehen, das Maier zweimal mit ausgeben wird. Die multimap gibt uns auch die Möglichkeit die Anzahl eines bestimmten Schlüssels zurückzugeben. Hierfür steht die Methode count() zur verfügung.
| CPP: | | std::cout << "Anzahl von Maier: " << telbuch.count("Maier") << std::endl; |
set
Ein set ist ein Container, der seine Element sortiert enthält. Auch ist es nicht möglich, dass ein Element mehrmals vorkommt. Der Wert ist zugleich der Schlüssel. Implementiert ist diese Klasse als Binärbaum. Dies hat den Vorteil, dass das Einfügen eines neuen Elements ziemlich schnell geht.
Erstmal müssen wir die Headerdatei <set> einbinden um dieses Container nutzen zu können.
Als Beispiel legen wir nun ein set mit Namen an. Für die Namen nehmen wir die Klasse std::string.
std::set<std::string> namen;
Jetzt wollen wir noch ein paar Namen einfügen. Hierfür nehmen wir die Methode insert(). Übergeben müssen wir dieser nur den Wert.
| CPP: | namen.insert("Sven Burow");
namen.insert("Max Mustermann");
namen.insert("Stefan Raab");
namen.insert("Elton");
namen.insert("Sven Burow"); //Wird ignoriert, weil schon vorhanden |
Ausgeben können wir unser set mit Hilfe von Iteratoren. Dazu erzeugen wir einen Iterator für unseren Container.
| CPP: | // Iterator erzeugen
std::set<std::string>::iterator it;
// Alles ausgeben
for(it = namen.begin(); it!= namen.end(); it++)
std::cout << *it << std::endl; |
Durch die Eindeutigkeit der Schlüssel/Werte können wir mit der Methode find() ganz leicht suchen. Zurückgegeben wird ein Iterator. Wenn nichts gefunden wurde, dann zeigt dieser hinter das letze Element also auf end().
| CPP: | std::string name;
std::cout << "Nach welchen Namen wollen Sie suchen? ";
std::cin >> name;
it = namen.find(name);
if(it != namen.end())
std::cout << *it << std::endl;
else
std::cout << "Nicht in der Liste" << std::endl; |
multiset
Der Unterschied zum normalen set ist, dass die Eindeutigkeit der Schlüssel aufgehoben ist, d.h. wir können gleiche Schlüssel hinzufügen.
Die Definition dieses Containers steht in der Headerdatei <map>. Diese müssen wir einbinden.
Jetzt erzeugen wir einen Container, der Namen speichern kann.
| CPP: | | std::multiset<std::string> namen; |
Daten können wir mit der Methode insert() einfügen.
| CPP: | namen.insert("Sven Burow");
namen.insert("Elton");
namen.insert("Max Mustermann");
namen.insert("Stefan Raab");
namen.insert("Elton"); |
Die Ausgabe ist wie auch schon bei dem „normalen“ set mit Iteratoren. Wir erzeugen also als erstes einen Iterator und lassen diesen dann das set ausgeben.
| CPP: | // Iterator erzeugen
std::multiset<std::string>::iterator it;
// Alles ausgeben
for(it = namen.begin(); it!= namen.end(); it++)
std::cout << *it << std::endl; |
Wie sie merken ist Elton mehrmals vorhanden. Um nun die Anzahl von Elton festzustellen, können wir die Methode count() nutzen.
| CPP: | | std::cout << "Anzahl von Elton: " << namen.count("Elton") << std::endl; |
Containeradapter
Containeradapter sind Containerklassen, die mit einem anderem Container implementiert wurden. Dazu zählen stack und queue. Beide werden standardmässig mit deque implementiert.
stack
Ein stack ist ein Stapel. Auf diesen Stapel kann man oben etwas drauflegen oder entfernen. Wie bei einem Papierstabel kann man immer nur den obersten lesen. Möchte man die darunter lesen, muss man erst die darüberliegenden Blätter runternehmen und auf einen neuen Stapel legen oder in den Schredder werfen.
Erstmal müssen wir die Headerdatei <stack> includieren um diesen Containeradapter nutzen zu können.
Nun legen wir einen Stapel an, auf den wir Zahlen legen können.
| CPP: | | std::stack<int> zahlen; |
Nun wollen wir Zahlen auf unserem Stapel drauflegen. Hierzu gibt es die Methode push(). Ihr übergeben wir den Wert.
| CPP: | zahlen.push(12345);
zahlen.push(3002); |
Da es ein Stapel ist können wir nur auf das oberste schauen. Um nun den Wert auszugeben, bietet uns dieser Containeradapter die Methode top(). Diese gibt eine Referenz auf das oberste Objekt zurück. Wir können dieses also auch ändern.
| CPP: | std::cout << zahlen.top() << std::endl;
zahlen.top() = 40;
std::cout << zahlen.top() << std::endl; |
Ein Objekt vom Stapel zu nehmen ist auch nicht schwer. Dafür gibt es die Methode pop().
zahlen.pop();
Die Anzahl der Objekte auf dem Stapel bekommen wir mit Hilfe der Methode size();
| CPP: | | std::cout << „Anzahl der Elemente: “ << zahlen.size() << std::endl; |
queue
Eine queue ist ein erweiteter Stapel. Bei diesem kann man auf das oberste und unterste Element schauen.
Zu erst includieren wir die Headerdatei <queue>.
Nun können wir, wie beim stack, die Daten mit push() auf den Stapel drauflegen.
| CPP: | zahlen.push(911);
zahlen.push(4711);
zahlen.push(9000);
zahlen.push(4299); |
Wie schon gesagt können wir auf das oberste Element und auf das unterste Element zugreifen. Dafür gibt es die Methoden front() und back(). Diese geben eine Referenz zurück, d.h. wir können die Werte ändern.
| CPP: | std::cout << "Erstes Element: " << zahlen.front() << std::endl;
std::cout << "Letztes Element: " << zahlen.back() << std::endl; |
Das oberste Element können wir mit der Methode pop() löschen.
_________________
Nur wenn man ein Ziel sieht, kann man es auch treffen.
___________
Mein Leben, Freunde und die Spieleentwicklung |
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Medaillen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
