| 3.3.3. Maps (class map) | ||
|---|---|---|
 | 3.3. Hashing types |  |
| 3.3.3. Maps (class map) | ||
|---|---|---|
| | 3.3. Hashing types | |
Learning objectives
The class map |
As already mentioned in Section 3.3.1, LEDA offers a further
associative container type that works with hashing. It is the type
map. This name may suggest that
this type deals with quite general mappings in which any key type and
any value type can be used. However, this is not at all so! On the
contrary, one is essentially limited in the choice of the key type of
a map to types that are integral in the sense
that they can be interpreted as a value of the type int:
These are the type int itself, every pointer type, and every item
type.
The implementation of map works
with a hardwired hash function that interprets every key k as a
32-bit value and hashes it onto the position k mod
2m; here m is the current number of
slots. This hardwired hash function makes map a
considerably faster associative container type than h_array in
general, that is, when the keys are more or less equally distributed.
The interface of map is exactly
same as the one of h_array, with one important
exception: There is no operation undefine(),
that is, keys, once inserted, cannot be deleted any more unless one
empties the complete container structure by means of
clear().
So a map with key type
K and value type V is created by
map<K,V> M;
and
map<K,V> M(x);
respectively. In the latter case, in addition, the default value of
the map is set to the value x.
An access via a key k to the respective
value is carried out by the subscript operator
M[k];
As in the case of h_array an
M.defined(k);
asks whether a certain key k occurs in the map, and
M.clear();
deletes all key-value pairs from the map.
In which cases can a map be of
advantage? When should one rather use the type
h_array (which is also a hashing type)?
First of all, it has to be noticed that for a
map only the three key types
int, pointer type, and
item type are possible. If a different key type
is to be stored by means of hashing, only an
h_array is possible, with an appropriately
predefined or self-written hash function. An
h_array is also inevitable if key-value pairs
are to be deleted again - this is not possible in a
map. An h_array should
also be used if, due to a key distribution known a priori, a
specialized hash function is needed or desired - only an
h_array with its two-step procedure allows the
user to influence the computing of the hash value.
In the other cases a map is
considerably faster than an h_array because of
its hard-wired hash function.
The most frequent use of a map
when programming with LEDA might occur in the application cases in
which values are to be associated to the item types
point and segment.
(These types belong to the geometry part of LEDA.)
For the cases map<node,V> and
map<edge,V>, which occur particularly
frequently in graph algorithms,
there are the special types node_map<V> and edge_map<V>
, respectively.
A use of map with a pointer type
as the key type makes sense in the following scenario: One has to
refer to a great many objects whose type is a “small”
structure small_struct, that is,
small_struct encapsulates only a few, small data
members. One wants to associate an additional value of a type
V only to a few of these
structures. Since one altogether has to reference many
small_structs, however, an inclusion of V as
a data member in small_struct would waste too much unused
storage. Here a map<small_struct*,V> can be
useful to associate additional values to only a few references.
Like the variables managed in an
h_array, the ones managed in a
map are not persistent either.
More about the class map can be found on the corresponding manual page.
| |  | |
| 3.3.2. Hashing arrays (class h_array) |  | 3.4. Sorted sequences (class sortseq) |