3.3.3. Maps (class map)

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.

Use cases for 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.

Further information

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.




Imprint-Dataprotection