| 3.3.3. Maps (Klasse map) | ||
|---|---|---|
 | 3.3. Hashende Typen |  |
| 3.3.3. Maps (Klasse map) | ||
|---|---|---|
| | 3.3. Hashende Typen | |
Lernziele
Die Klasse map |
Wie schon in Abschnitt 3.3.1
erwähnt, besitzt LEDA noch einen weiteren assoziativen
Containertyp, der mit Hashing arbeitet. Es handelt sich um den
Typ map, zu
deutsch also „Abbildung“. Diese Bezeichnung mag
nahelegen, dass es sich hierbei um ganz allgemeine Abbildungen
handelt, bei der jeder Schlüsseltyp und jeder Wertetyp verwendet
werden kann. Dies ist aber mitnichten so! Im Gegenteil, man ist
bei der Wahl des Schlüsseltyps einer map
im Wesentlichen auf Typen eingeschränkt, die in dem Sinne
ganzzahlig sind, als dass sie sich als ein Wert des Typs
int interpretieren lassen: Das sind der Typ
int selbst, jeder Pointer-Typ und jeder
Item-Typ.
Die Implementierung von map arbeitet
mit einer festverdrahteten Hash-Funktion, die jeden Schlüssel k
als 32-Bit-Wert interpretiert und auf die Position k mod 2^m hasht, wobei m die
aktuelle Anzahl der Slots ist. Diese festverdrahtete
Hash-Funktion macht map i. Allg., d. h. bei
mehr oder weniger gleichverteilten Schlüsseln, zu einem
wesentlich schnelleren assoziativen Containertyp als h_array.
Die Schnittstelle von map ist genau
dieselbe wie die von h_array, mit einer
wichtigen Ausnahme: Es gibt keine Operation
undefine(), d. h., einmal eingefügte
Schlüssel können nicht mehr gelöscht werden, es sei denn, man
leert mittels clear() die gesamte
Containerstruktur.
Eine map mit Schlüsseltyp K und Wertetyp V wird also angelegt durch
map<K,V> M;
bzw.
map<K,V> M(x);
wobei im letzteren Fall zusätzlich der Default-Wert der Map auf den Wert x gesetzt wird.
Ein Zugriff über einen Schlüssel k auf den
zugehörigen Wert geschieht durch den Subskript-Operator
M[k];
Wie bei h_array fragt
M.defined(k);
ob ein bestimmer Schlüssel k in der Map vorkommt, und
M.clear();
löscht alle
Schlüssel-Wert-Paare aus der map.
In welchen Fällen kann eine map
von Vorteil sein? Wann sollte man eher den ebenfalls hashenden
Typ h_array verwenden?
Zunächst einmal ist festzuhalten, dass für eine
map nur die drei Schlüsseltypen
int,
Pointer-Typ oder
Item-Typ in Frage kommen. Soll ein
anderer Schlüsseltyp unter Verwendung von Hashing gespeichert werden, kommt nur ein
h_array mit entsprechend vordefinierter
oder selbstgeschriebener Hash-Funktion in Frage. Ein
h_array ist auch dann unumgänglich,
wenn Schlüssel-Wert-Paare wieder gelöscht werden sollen - dies
ist in einer map nicht
möglich. Verwendet werden sollte ein
h_array auch in dem Fall, in dem
aufgrund einer a priori bekannten Schlüsselverteilung eine
spezialisierte Hash-Funktion vonnöten oder erwünscht ist - nur
ein h_array mit seinem zweistufigen
Verfahren erlaubt es dem Benutzer, die Berechnung des
Hash-Wertes zu beeinflussen.
In den anderen Fällen ist eine
map aufgrund ihrer fest verdrahteten
Hash-Funktion deutlich schneller als ein
h_array.
Die häufigste Verwendung einer
map beim Programmieren mit LEDA
dürfte in den Anwendungsfällen auftreten, in denen zu den
Item-Typen point oder
segment Werte assoziiert werden
sollen. (Zu diesen Typen aus dem Geometrie-Teil von LEDA
werden wir erst später kommen.) Für die bei Graphenalgorithmen
besonders häufig auftretenden Fälle
map<node,V> und
map<edge,V> gibt es die speziellen
Typen node_map<V> und
edge_map<V>.
Eine Verwendung von map mit einem
Pointer-Typ als Schlüsseltyp hat in folgendem Szenario Sinn:
Man hat auf sehr viele Objekte zu verweisen, deren Typ eine
„kleine“ Struktur small_struct ist,
d. h., small_struct kapselt nur wenige, kleine
Datenmember. Nur zu einigen dieser
Strukturen will man noch einen zusätzlichen Wert eines Typs
V assoziieren. Da man insgesamt aber sehr viele
small_structs zu referenzieren hat, würde eine
Aufnahme von V als Datenmember in
small_struct zu viel Speicherplatz ungenutzt
verschwenden. Hier kann eine
map<small_struct*,V> nützlich sein, um nur zu
einigen Referenzen zusätzliche Werte zu assoziieren.
Die in einer map verwalteten
Variablen sind wie die in einem
h_array verwalteten ebenfalls nicht persistent.
Mehr über die Klasse map
findet sich auf der entsprechenden Manualseite.
| |  | |
| 3.3.2. Hashing-Arrays (Klasse h_array) |  | 3.4. Geordnete Folgen (Klasse sortseq) |