C++ Kurs

Standard-Container III

Die Themen:

In Kapitel wenden wir uns den assoziativen Containern zu. 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 einem Assoziativ-Container erfolgt ausschließlich über einen Schlüssel oder Iterator. Die in einem Assoziativ-Container abzulegende Elemente müssen sortierbar sein und das Sortierkriterium muss der 'strict weak ordering' Bedingung genügen:

Sehen wir uns nun die einzelnen Assoziativ-Container an:

set und multiset

Set bzw. Multiset definieren einen sortierten Container der nur 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 schreibt der C++ Standard aber nicht explizit vor.

set

Wenn ein Set bzw. Multiset verwendet wird, ist die Header-Datei set einzubinden. Der Datentyp eines Sets ist std:set<DTYP> und der eines Multisets std::multiset<DTYP>.

HinweisWenn 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.

Definition eines Set

Ein Set kann auf verschiedene Weisen definiert werden (leeres Set, Set mit gleichen Elementen oder mit Elementen aus einem anderen Container). Standardmäßig werden die Elemente in einem Set aufsteigend sortiert. Soll ein anderes Sortierkriterium verwendet werden, so muss dieses bei der Definition des Sets mit angegeben werden. Das Sortierkriterium muss als Funktionsobjekt (Functor) definiert werden. Mehr zum Sortierkriterium gleich noch. Wenn ein Sortierkriterium vorgegeben wird, beachten Sie, dass das Sortierkriterium dann mit zum Datentyp des Sets gehört!

PgmHeader#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());

Größenangaben

Über die Memberfunktion size() kann die Anzahl der Elemente in einem Set abgefragt werden.

Elementzugriffe

Ein Set erlaubt keinen direkten Zugriff auf die in ihm abgelegten Elemente. Der Zugriff kann nur über einen bidirektionalen Iterator oder über die gleich aufgeführten Such-Memberfunktionen erfolgen.

PgmHeader// 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;
// Alternativ mit Hilfe der range-for Schleifen
for (auto element: mySet)
  cout << element << endl;
HinweisIn vielen der nachfolgenden Beispiele können Sie anstelle einer for Schleife mit einem Iterator als Schleifenvariable auch eine range-for Schleife verwenden (siehe obiges Beispiel).
HinweisBeachten Sie ferner, dass Sie hier einen bidirektionalen Iterator verwenden müssen, d.h. Sie können diesen Iterator nur inkrementieren bzw. dekrementieren. Wollen Sie den Iterator um n-Positionen verschieben, so müssen Sie hierzu die Memberfunktion advance(...) verwenden.

Typdefinitionen

Kein Unterschied zu den Typdefinitionen eines Vektors.

Einfügen und Entfernen von Elementen

Zum Einfügen und Entfernen von Elementen stehen die Memberfunktionen insert(...), erase(...) und clear() zur Verfügung.

Ein einzelnes Element wird mit der Memberfunktion insert(element) eingefügt. Sollen mehrere Elemente aus einem anderen Container eingefügt werden, so ist die Memberfunktion insert(beg,end) zu verwenden. Der Iterator beg gibt die Startposition der einzufügenden Elemente an und end kennzeichnet das Ende+1 der einzufügenden Elemente. Das Element an der Position end wird demzufolge nicht mehr mit übernommen.

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.

Der Returntyp der Memberfunktion insert(element) ist bei einem Set und einem Multiset unterschiedlich, da bei einem Set 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 der Iterator auf die Einfügeposition des Elements und das zweite pair-Element gibt den Erfolg bzw. Misserfolg der Operation an. Enthält das zweite pair-Element den Wert false, so konnte das Element nicht eingefügt werden.

PgmHeader// 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

Bei einem Multiset liefert insert(…) nur den Iterator auf die Einfügeposition des Elements zurück.

Zuweisungen, Vergleichsoperationen und Iteratoren

Hierbei gibt es keine Unterschiede zur Liste (Iteratoren sind bidirektional). Beachtet werden muss dabei, dass nur gleiche Sets einander zugewiesen werden können. Ein Set mit dem Sortierkriterium A ist nicht identisch mit einem Set mit dem Sortierkriterium B, da das Sortierkriterium mit zum Datentyp des Sets gehört.

Weitere Set-Memberfunktionen

Sets sind Container die zum schnellen Suchen von Elementen optimiert sind. Daher stehen zum Suchen entsprechende Memberfunktionen zur Verfügung.

Die Memberfunktion count(element) liefert die Anzahl der Elemente mit dem Wert element zurück. Bei einem set wird die Memberfunktion daher nur die Werte 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.

PgmHeadermultiset<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 nach einem bestimmten Wert, enthält ein Set noch die Memberfunktionen lower_bound(element), upper_bound(element) und equal_range(element) zum Suchen von Wertebereichen. Alle drei Memberfunktionen liefern Iteratoren auf die gefundenen Positionen innerhalb des Sets zurück. lower_bound(element) sucht die Position des Elements, das einen Wert größer/gleich element besitzt während upper_bound(element) die erste Position des Elements liefert, das 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.

PgmHeadermultiset<int> mySet;
...
// Erste Position des Werts 10 oder größer suchen
auto liter = mySet.lower_bound(10);
// Position des nächst größeren Wertes als 10 suchen
auto uiter = mySet.upper_bound(10);
// Beide Position auf einmal holen
pair<msi,msi> range = mySet.equal_range(10);

BeispielUnd hier geht's zum Beispiel.

map und multimap

Map bzw. Multimap definieren einen sortierten Container, der nun nicht nur einen Schlüssel enthält sondern zusätzlich auch ein beliebiges Datum. 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 auch eine Map bzw. Multimap über einen entsprechenden binären Baum realisiert. Dies schreibt der C++ Standard aber nicht explizit vor.

map

Um eine Map bzw. Multimap zu verwenden zu können, muss die Header-Datei map eingebunden werden. Der Datentyp einer Map ist std:map<DTYP> und der einer Multimap std::multimap<DTYP>.

HinweisWenn im Folgenden der Begriff Map verwendet wird, bezieht sich dies auch immer auf eine Multimap. Sollten zwischen einer Map und einer Multimap Unterschiede bestehen, wird wiederum explizit darauf hingewiesen.

Definition einer Map

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. Soll ein anderes Sortierkriterium verwendet werden, so ist dieses bei der Definition der Map ebenfalls mit anzugeben. Das Sortierkriterium ist, wie bei einem Set, über ein entsprechendes Funktionsobjekt zu definieren.

PgmHeader#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;

Größenangaben

Über die Memberfunktion size() kann die Anzahl der Elemente in einer Map ermittelt werden.

Elementzugriffe

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 das mit ihm verbundene Datum.

PgmHeader// 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"];
AchtungGeben Sie beim Setzen des Zusatzwertes einen nicht existierenden Schlüssel an, so wird ein neues Element 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.

Wird über einen Iterator auf die Elemente in einer Map zugegriffen, so ist der Rückgabewert ein pair vom Typ pair<key,value>. Alternativ kann auch nur der Schlüssel bzw. das Datum, wie nachfolgend angegeben, ausgelesen werden. Ebenfalls möglich ist, das Datum über einen Iterator neu zu setzen. Nicht verändert werden kann hierbei der Schlüssel, da dies ansonsten die Sortierung der Map durcheinander bringen würde.

PgmHeader// Map definieren, Schlüssel ist string und Zusatzwert ist int
using smap = map<string,int>;
smap myMap;
// Iterator definieren und 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;

Typdefinitionen

Identisch mit denen des Vektors.

Einfügen und Entfernen von Elementen

Es stehen die gleichen Memberfunktionen insert(...), erase(...) und clear() wie beim Set zur Verfügung.

Beachtet werden muss dabei, dass ein Map-Element immer aus einem Schlüssel/Wert Paar besteht. Es muss also der insert(element) Memberfunktion, wie nachfolgend dargestellt, ein solches Paar übergeben werden. Im Beispiel sind drei verschiedene Methoden dargestellt, wie ein Element in eine Map eingefügt werden kann.

PgmHeader// Multimap definieren
using mis = multimap<int, string>;
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.

Zuweisungen, Vergleichsoperationen und Iteratoren

Auch hier gilt das Gleiche wie beim Set.

Weitere Map-Memberfunktionen

Auch Maps sind Container die zum schnellen Suchen von Elementen optimiert sind. Daher stehen zum Suchen die gleichen Memberfunktionen count(key), find(key), lower_bound(key), upper_bound(key) und equal_range(key) wie bei einem Set zur Verfügung. Als Parameter erhalten alle Memberfunktionen nur den Schlüssel des zu suchenden Elements übergeben.

Beispiel und ÜbungUnd hier geht's zum Beispiel und zur Übung.