Wurden bisher nur Container behandelt, die die Elemente sequentiell (der Reihe nach) ablegen, so werden wir uns jetzt assoziative Container ansehen. Assoziativ-Container erlauben den schnellen Zugriff auf Elemente über einen frei wählbaren Schlüssel (Key), d.h. der direkt Zugriff auf die Elemente in einen Assoziativ-Container erfolgt nicht wie bei den sequentiellen Containern über einen Index oder Iterator sondern ausschließlich über einen Schlüssel. Die in einem Assoziativ-Container abzulegende Elemente müssen sortierbar sein. Das Sortierkriterium muss der 'strict weak ordering' Bedingung genügen:
Aber sehen wir uns nun die einzelnen Assoziativ-Container an:
Set bzw. Multiset definieren einen sortierten Container der nur den Schlüssel enthält. Der Unterschied zwischen einen Set und einem Multiset besteht darin, dass in einem Set ein Schlüssel nur einmal vorkommen darf während ein Multiset mehrere gleiche Schlüssel zulässt.
Typischerweise wird ein Set bzw. Multiset über einen binären Baum realisiert. Dies ist schreibt der C++ Standard aber nicht explizit vor
Wenn Sie ein Set bzw. Multiset einsetzen, müssen Sie die Header-Datei set einbinden. Der Datentyp eines Sets ist std:set<DTYP> und der eines Multisets std::multiset<DTYP>.
|
|
Auch ein Set können Sie auf verschiedene Arten definieren (leeres Set, Set mit gleichen Elementen oder mit Elementen aus einem anderen Container initialisieren). Standardmäßig werden die Elemente in einem Set aufsteigend sortiert. Wollen Sie ein anderes Sortierkriterium, so müssen Sie dieses bei der Definition des Sets mit angeben. Das Sortierkriterium muss als Funktionsobjekt (Functor) definiert werden. Mehr zum Sortierkriterium gleich noch. Bitte beachten Sie, dass das Sortierkriterium mit zum Datentyp des Sets gehört!
 #include <set> // Leeres Set für ints definieren set<int> emptySet; // Set mit Sortierkriterium definieren set<int,SortFtor> mySortSet; // Set für Objekte definieren, Sortierkriterium ist // innerhalb der Klasse definert set<Object,Object::Sort> mySortObj; // Elemente aus einer Liste in ein Set umkopieren list<int> myList; ... set<int> mySet(myList.begin(),myList.end()); |
Über die Memberfunktion size() können Sie die Anzahl der Elemente in einem Set abfragen.
Ein Set erlaubt keinen direkten Zugriff auf die Elemente. Der Zugriff kann nur über einen bidirektionalen Iterator oder über die gleich aufgeführten Such-Memberfunktionen erfolgen.
// Multiset definieren multiset<int> mySet; ... // Iterator definieren multiset<int>::iterator iter; // Alle Elemente auslesen for (iter=mySet.begin(); iter!=mySet.end(); ++iter) cout << *iter << endl; |
|
|
Keine Änderung gegenüber Vektor.
Zum Einfügen und Entfernen von Elementen stehen die Memberfunktionen insert(...), erase(...) und clear() zur Verfügung.
Um ein einzelnes Element einzufügen, verwenden Sie die Memberfunktion insert(element). Sollen mehrere Elemente aus einem anderen Bereich eingefügt werden, so ist insert(beg,end) zu verwenden. beg ist ein Iterator der die Startposition der einzufügenden Elemente angibt und end der Iterator auf das Ende+1 der einzufügenden Elemente. Beachten Sie, dass das Element an der Position end nicht mehr übernommen wird.
Zum Löschen eines einzelnen Elements dient die Memberfunktion erase(element) und zum Löschen mehrere Elemente die Memberfunktion erase(beg,end). Das Element an der Position end verbleibt weiterhin im Set. Bei einem Multiset entfernt erase(element) alle Elemente, die mit dem übergebenen übereinstimmen.
Die Returntypen der Memberfunktionen insert(element) unterscheiden sich bei einem Set und einem Multiset, da bei einem Set ja keine doppelten Schlüssel auftreten dürfen und damit die insert(element) Memberfunktion auch fehlschlagen kann.
Die insert(element) Memberfunktion eines Sets besitzt den Returntyp
| pair<set<DTYP>::iterator,bool> |
Das erste pair-Element ist ein Iterator auf die Einfügeposition des Elements und das zweite pair-Element gibt den Erfolg/Misserfolg der Operation an. Enthält das zweite pair-Element den Wert false, so konnte das Element nicht eingefügt werden.
// Set definieren set<int> mySet; ... // pair-Return für insert definieren pair<set<int>::iterator,bool> success; // Element einfügen success = mySet.insert(value); // Abprüfen ob Element eingefügt wurde if (!success.second) ... // Fehlerbehandlung |
Hierbei gibt es keine Unterschiede zur Liste (Iteratoren sind bidirektional). Beachten müssen Sie nur, dass Sie nur gleiche Sets einander zuweisen können. Ein Set mit dem Sortierkriterium A ist nicht identisch mit einem Set mit dem Sortierkriterium B, d.h. das Sortierkriterium gehört mit zum Datentyp des Sets.
Sets sind Container die zum schnellen Suchen von Elementen optimiert sind. Daher stehen zum Suchen entsprechende Memberfunktionen bereit.
Die Memberfunktion count(element) liefert die Anzahl der Elemente mit dem Wert element zurück. Bei einem set kann die Memberfunktion nur 0 oder 1 zurückliefern.
Soll die (erste) Position eines Wertes im einem Set bestimmt werden, so steht dazu die Memberfunktion find(element) zur Verfügung. find(...) liefert einen Iterator auf das gesuchte Element zurück. Ist das gesuchte Element nicht im Container vorhanden, so liefert find(...) die Position end() zurück.
multiset<int> mySet; ... // Anzahl der Elemente mit dem Wert 5 size_t noOfElements = mySet.count(5); // Iterator definieren multiset<int>::iterator iter; // Erstes Element mit dem Wert 10 suchen iter = mySet.find(10); // Wenn das Element nicht vorhanden ist if (iter == mySet.end()) ... |
Zusätzlich zum Suchen eines bestimmten Wertes enthält ein Set noch die Memberfunktionen lower_bound(element), upper_bound(element) und equal_range(element) zum Suchen von Wertebereichen. Alle Memberfunktionen liefern Iteratoren auf die gefundenen Positionen innerhalb des Sets zurück. lower_bound(element) sucht nach der Position, die einen Wert größer/gleich element besitzt während upper_bound(element) die erste Position liefert, die einen Wert größer als element besitzt. equal_range(element) ist eine Kombination aus lower_bound(...) und upper_bound(...) und liefert die beiden Positionen in einem pair zurück.
multiset<int> mySet; ... // Iteratoren definieren typedef multiset<int>::iterator msi; msi liter, uiter; // Erste Position des Werts 10 oder größer suchen liter = mySet.lower_bound(10); // Letzte+1 Position des Wertes größer 10 suchen uiter = mySet.upper_bound(10); // Beide Position auf einmal holen pair<msi,msi> range = mySet.equal_range(10); |
Sehen wir uns einmal ein praktisches Beispiel für den Einsatz eines sets an.
|
 In der letzten Lektion haben Sie etwas ueber Funktionen und Templates erfahren Aber Sie koennen Templates nicht nur fuer Funktionen verwenden sondern auch fuer Klassen einsetzen |
Woerter aus einer Datei im Set ablegen: |
// Beispiel zu set #include <iostream> #include <fstream> #include <set> #include <string> #include <locale> using std::cout; using std::endl; using std::string; // Name der zu untersuchenden Textdatei const char *pFILE = "demo.txt"; // Functor, Stringvergleich ohne Berücksichtigung der // Gross-/Kleinschreibung struct ignorecase { std::locale loc; bool operator()(const string& s1, const string& s2) const { string::const_iterator iter1 = s1.begin(); string::const_iterator iter2 = s2.begin(); while ((iter1!=s1.end()) && (iter2!=s2.end())) { // tolower aus locale. Berücksichtigt die // landesspezifischen Umwandlungen char cs1 = std::tolower(*iter1,loc); char cs2 = std::tolower(*iter2,loc); // Buchstaben vergleichen if (cs1<cs2) return true; if (cs1>cs2) return false; // Bei Gleichheit, nächster Buchstabe ++iter1; ++iter2; } return false; } }; // main() Funktion int main() { // Zu untersuchende Datei öffnen std::ifstream infile(pFILE); if (!infile) { cout << "Fehler beim Oeffnen der Datei " << pFILE << endl; exit(1); } // Set für Wörter aus Datei anlegen // Ignoriert Gross/Kleinschreibung beim Einfügen über Functor ignorecase() std::set<string,ignorecase> dictionary; // Returncode für insert() Memberfunktion std::pair<std::set<string,ignorecase>::iterator,bool> success; // Iterator definieren std::set<string,ignorecase>::iterator iter; // Komplette Datei einlesen cout << "Woerter aus einer Datei im Set ablegen:\n"; while (!infile.eof()) { // Wort aus Datei einlesen string word; infile >> word; // und im Set ablegen. Falls Wort schon vorhanden, Meldung ausgeben success = dictionary.insert(word); if (!success.second) cout << "Wort '" << *success.first << "' schon vorhanden!\n"; } // Alle Wörter aus Datei ausgeben cout << "In der Datei enthaltene Worte:\n"; for (iter=dictionary.begin(); iter!=dictionary.end(); ++iter) cout << *iter << ','; cout << endl; // Nun alle Wörter mit einem bestimmten Buchstaben ausgeben // Gesuchter String string toSearch = "e"; // Iterator auf ersten übereinstimmenden Eintrag std::set<string,ignorecase>::iterator lowerPos = dictionary.lower_bound(toSearch); // Iterator auf ersten nicht mehr übereinstimmenden Folgeeintrag std::set<string,ignorecase>::iterator upperPos = dictionary.upper_bound(toSearch); // Alle gefunden Wörter ausgeben cout << "Alle Woerter mit dem Buchstaben 'e':\n"; cout << "Anzahl: " << std::distance(lowerPos,upperPos) << endl; for (iter=lowerPos; iter!=upperPos; ++iter) cout << *iter << ' '; cout << endl; cout << "Anzahl der Woerter (ohne Duplikate): " << dictionary.size() << endl; } |
Sie sehen, mithilfe eines solchen Sets lassen sich auf elegante Art und Weise sortierte Reihenfolgen erstellen und verarbeiten. Ein solches Set kann z.B. auch zum Sortieren und Verarbeiten einer Adressenliste verwendet werden, wenn das Sortierkriterium entsprechend definiert ist. Denken Sie immer daran, das die Container nicht nur einfache Daten sondern auch Objekte aufnehmen können. Im obigen Beispiel enthält das set z.B. Objekte vom Typ string.
Map bzw. Multimap definieren einen sortierten Container, der nun nicht nur einen Schlüssel enthält sondern auch einen beliebigen zusätzlichen Wert. Der Unterschied zwischen einer Map und einer Multimap besteht, genauso wie beim Set, darin, dass in einer Map ein Schlüssel nur einmal vorhanden sein darf und eine Multimap mehrere gleiche Schlüssel zulässt.
Typischerweise wird eine Map bzw. Multimap über einen binären Baum realisiert. Dies schreibt der C++ Standard aber nicht explizit vor.
Wenn Sie eine Map bzw. Multimap einsetzen, müssen Sie die Header-Datei map einbinden. Der Datentyp einer Map ist std:map<DTYP> und der einer Multimap std::multimap<DTYP>.
|
|
Da eine Map zusätzlich zum Schlüssel noch einen beliebigen Wert enthält, muss der Datentyp dieses zusätzlichen Werts mit bei der Definition angegeben werden. Standardmäßig werden die Elemente in einer Map aufsteigend sortiert. Wollen Sie ein anderes Sortierkriterium, so müssen Sie dieses bei der Definition der Map mit angeben. Das Sortierkriterium ist, wie bei einem Set, über ein entsprechendes Funktionsobjekt zu definieren.
#include <map> // Leere Map mit int-Schlüssel und string als zusätzliches Datum map<int, string> emptyMap; // Gleiche Map mit zusätzlichem Sortierkriterium definieren map<int,string,SortFtor> mySortMap; |
Über die Memberfunktion size() können Sie die Anzahl der Elemente in einer Map abfragen.
Im Gegensatz zu einem Set, erlaubt eine Map zusätzlich den direkten indizierten Zugriff auf die Elemente, wobei als Index der Schlüssel anzugeben ist. Bei dieser Zugriffsart kann der Schlüssel nicht verändert werden sondern nur der mit ihm verbundene Wert. Beachten Sie im Beispiel, dass der Schlüssel vom Typ string ist und damit innerhalb der Indexklammern auch ein string (oder etwas in einen string konvertierbares) stehen muss.
// Map definieren, string ist Schlüssel und Zusatzwert ist int map<string,int> myMap; ... // Zusatzwert direkt setzen myMap["KEY"] = 10; // Zusatzwert auslesen int var = myMap["KEY"]; |
|
|
Greifen Sie über einen Iterator auf Elemente in einer Map zu, so erhalten Sie als Rückgabewert immer ein pair vom Typ pair<key,value>. Alternativ können Sie auch nur den Schlüssel bzw. den Wert wie unten angegeben auslesen. Ebenfalls möglich ist es, den Wert über einen Iterator neu zu setzen. Nicht verändern können Sie aber den Schlüssel, da dies ansonsten die Sortierung der Map durcheinander bringen würde.
// Map definieren, string ist Schlüssel und Zusatzwert ist int typedef map<string,int> smap; smap myMap; // Iterator definieren/initialisieren smap::iterator iter = myMap.begin(); // komplettes Element auslesen pair<string,int> rval = *iter; // Nur Key auslesen string sret = iter->first; // Nur Wert auslesen int val = iter->second; // Wert über Iterator setzen iter->second = 10; |
Identisch mit denen des Vektors.
Es stehen die gleichen Memberfunktionen insert(...), erase(...) und clear() wie beim Set zur Verfügung.
Beachten müssen Sie hier, dass ein Map-Element immer aus einem Schlüssel/Wert Paar besteht. Sie müssen also der insert(element) Memberfunktion, wie nachfolgend dargestellt, ein solches Paar übergeben. Im Beispiel sehen Sie drei verschiedene Weisen, wie Sie ein Element in eine Map einfügen können.
// Multimap definieren typedef multimap<int, string> mis; mis myMap; // Neue Elemente einfügen myMap.insert(pair<int,string>(10,"ten")); myMap.insert(make_pair(11,"eleven")); myMap.insert(mis::value_type(9,"nine")); |
Bezüglich des Returnwertes der insert(element.) Memberfunktion für eine Map gilt das Gleiche wie beim Set. Da eine einfache map keine doppelten Schlüssel zulässt, liefert die insert(element) Memberfunktion ebenfalls ein pair zurück, dessen zweites Element (second) den Erfolg oder Misserfolg der Operation angibt.
Auch hier gilt das Gleiche wie beim Set.
Auch Maps sind Container die zum schnellen Suchen von Elementen optimiert sind. Und daher stehen zum Suchen die gleichen Memberfunktionen count(key), find(key), lower_bound(key), upper_bound(key) und equal_range(key) wie beim Set zur Verfügung. Als Parameter erhalten alle Memberfunktionen nur den Schlüssel des zu suchenden Elements übergeben.
Damit haben Sie alle Container der Standard Bibliothek mit ihren wichtigsten Eigenschaften und Operationen kennen gelernt. Im Anschluss finden Sie eine Tabelle mit einer Übersicht über alle Container.
|
|
|
Im Anschluss an das Einfügen der Aktien werden diese zur Kontrolle alle ausgegeben.
Danach wird der Kurswert einer Aktien erhöht, eine neue Aktie hinzugefügt und das ganze Aktienkonto dann erneut ausgegeben.
Zum Schluss wird der Name einer Aktie umbenannt. Da der Aktienname als Schlüssel innerhalb der map verwendet wird, kann dies nicht direkt erfolgen, da ansonsten die map nicht mehr sortiert wäre. Im Beispiel wird dazu die umzubenennende Aktie einer neuen Aktie zugewiesen. Bei einer solchen Zuweisung wird nur der Wert und nicht der Schlüssel übernommen, d.h. es wird lediglich der Aktienkurs übernommen. Anschließend wird die alte, bisherige Aktie gelöscht.
|
BMW Aktie: 54.45 EUR |
// Beispiel zu map #include <iostream> #include <iomanip> #include <string> #include <map> using std::cout; using std::endl; // main() Funktion int main() { // Zur Abwechslung mal ein Zeiger auf einen Container! typedef std::map<std::string,float> aktien; aktien *pAktien; // Iterator definieren aktien::iterator iter; // Map dynamisch anlegen pAktien = new aktien; // Map mit Daten füllen (*pAktien)["VW"] = 12.f; (*pAktien)["Ford"] = 34.45f; (*pAktien)["BMW"] = 54.45f; (*pAktien)["Daimler Crysler"] = 123.50f; // Ausgabe der Aktienwerte mit 2 Nachkommastellen cout << std::fixed << std::setprecision(2); // Alle Aktien ausgeben for (iter=pAktien->begin(); iter!=pAktien->end(); ++iter) cout << iter->first << " Aktie: " << iter->second << " EUR\n"; // VW Aktien um 10.00 erhöhen cout << "-- VW Aktie stiegt um 10.00 EUR --\n"; (*pAktien)["VW"] += 10.f; // Alle Aktien ausgeben for (iter=pAktien->begin(); iter!=pAktien->end(); ++iter) cout << iter->first << " Aktie: " << iter->second << endl; // Element explizit hinzufügen cout << "-- Porsche Aktien hinzufuegen --\n"; pAktien->insert(std::pair<const std::string,float>("Porsche",560.0f)); // Daimler Crysler Aktien in Daimler umbenennen // Zuerst kopieren cout << "-- Daimler Crysler in Daimler umbenennen --\n"; (*pAktien)["Daimler"] = (*pAktien)["Daimler Crysler"]; // und dann löschen! pAktien->erase("Daimler Crysler"); // Alle Aktien ausgeben for (iter=pAktien->begin(); iter!=pAktien->end(); ++iter) cout << iter->first << " Aktie: " << iter->second << endl; // map wieder löschen! delete pAktien; } |
Übung:In dieser Übung geht es darum, eine Klasse zu implementieren deren Schnittstellen bereits vorgegeben sind. Ziel ist es, eine Klasse für die Verwaltung von Adressen zu implementieren. Die Adressdaten bestehen dabei aus einem Namen, einer Telefon-Nummer und einer Email-Adresse. Alle Adressdaten liegen in Form von Strings vor.
Da sehr häufig Änderungen/Erweiterungen am Adressbuch vorgenommen werden, sollen die Adressdaten in einem entsprechenden Container abgelegt werden. Doppelte Adressen sind nicht zugelassen. Als Suchkriterium dient der Name.
Vervollständigen Sie die Implementierung der nachfolgenden Klasse AddressBook.
Die main() Funktion zum Testen der Klasse sowie der prinzipielle Klassenaufbau des Adressbuchs ist bereits fertig vorgegeben, d.h. bei richtiger Implementierung sollten Sie die nachfolgende Ausgabe erhalten.
|
Adressbuch enthaelt 4 Eintraege |
// Loesung zu Container #include <iostream> #include <string> #include <map> #include <iterator> using std::cout; using std::endl; using std::string; // Adressbuch Klasse // Lässt keine doppelten Einträge zu class AddressBook { // *** hier den Container definieren *** public: // ctor AddressBook() {} // dtor ~AddressBook() {} // Neue Adresse aufnehmen void Insert(const string& name, const string& phone, const string& email); // Gibt einzelne Adresse aus void PrintAddress(const string& name); // Ändert Adressbuch-Eintrag bool Update(const string& name, const string& phone, const string& email); // Adresse entfernen void Remove(const string& name); // Liefert Anzahl der Adressbuch-Einträge size_t size() { } // Gibt gesamtes Adressbuch aus friend std::ostream& operator << (std::ostream& os, AddressBook& abook); }; // Ausgabe einer Adresse void AddressBook::PrintAddress(const string& name) { } // Neuen Eintrag ins Adressbuch aufnehmen void AddressBook::Insert(const string& name, const string& phone, const string& email) { } // Eintrag aus Adressbuch entfernen void AddressBook::Remove(const string& name) { } // Eintrag abändern bool AddressBook::Update(const string& name, const string& phone_, const string& email_) { } // Ausgabe des gesamten Adressbuchs // I.A. kann noch kein const-Objekt übergeben werden da hierfür ein anderer, // (noch nicht behandelter) Iteratortyp (const_iterator) benötigt wird std::ostream& operator << (std::ostream& os, AddressBook& abook) { } // main() Funktion int main() { // Adressbuch dynamisch anlegen AddressBook *pAddr = new AddressBook; // Einige Einträge hinzufügen pAddr->Insert("Emil Maier", "0111/4545", "ema@sonst.net"); pAddr->Insert("Agathe Maier", "0111/4545", "agma@sonst.net"); pAddr->Insert("Franzi Xelsbrot", "08888/1234", "frax@kostnix.de"); pAddr->Insert("Gustav Gans", "09999/1111", "guga@lucky.com"); // Komplettes Adressbuch ausgeben cout << "Adressbuch enthaelt " << pAddr->size() << " Eintraege\n"; cout << *pAddr; // Eintrag abändern cout << "Aendere Telefon-Nummer von Gustav Gans:\n"; pAddr->Update("Gustav Gans", "09999/7777", "guga@lucky.com"); // Und nur geänderten Eintrag ausgeben cout << "Neuer Eintrag ist:\n"; pAddr->PrintAddress("Gustav Gans"); // Eintrag entfernen cout << "Entferne Franzi Xelsbrot:\n"; pAddr->Remove("Franzi Xelsbrot"); // Nochmals komplettes Adressbuch ausgeben cout << "Neues Adressbuch enthaelt " << pAddr->size() << " Eintraege:\n"; cout << *pAddr; // Adressbuch löschen delete pAddr; } |
Lösung
ansehen!
Wenn
im Folgenden der Begriff Set verwendet wird, bezieht sich dies
auch immer auf ein Multiset. Sollten zwischen einem Set und
einem Multiset Unterschiede bestehen, wird darauf explizit
hingewiesen.
Beispiel:
Geben
Sie beim Setzen des Zusatzwertes einen nicht existierenden
Schlüssel an, so wird ein neues Elemente mit diesem Schlüssel
erzeugt und in die Map eingefügt. Wird beim Auslesen eines
Elements ein nicht vorhandener Schlüssel angegeben, wird
ebenfalls ein neues Element erstellt und der Zusatzwert mit
seinem Standard-Konstruktor initialisiert.