In addition, LEDA offers two classes for persistent dictionaries, the classes p_dictionary and pp_dictionary. These are dictionaries that do not forget their “creation history” so that one can go back and access an older state of the dictionary at any time.

In a p_dictionary, an insertion or deletion of a key-value pair leads to a new dictionary being created. This new dictionary contains the modification; the old dictionary is unchanged and is returned by the operation. It then can be caught in an assignment of the form

D_old = D.insert(k,v);

and is thus further available. This assignment takes only constant time in contrast to ordinary dictionaries because no deep copy in the sense of LEDA rule “Copy of a value” is made. Even if D is changed now, D_old does not change, and nevertheless the implementation of this data type is so efficient that search and modification operations are very fast. This structure is used in the LEDA type planar_subdivision, for example.

In a pp_dictionary, only the dictionary created last may be changed; all previous ones can be accessed only by searches. Such a dictionary is called partially persistent. The main benefit of a pp_dictionary, when compared to a p_dictionary, is that an even faster implementation of the search and modification operations is possible, due to the restriction that only the latest dictionary may be modified.

Further information about these two classes is found on the corresponding manual page of p_dictionary and pp_dictionary.

All container types introduced in this chapter are one-dimensional in the sense that the keys must originate from a one-dimensional universe; they cannot be pairs of keys, so the set of keys cannot be (a subset of) a cross-product of partial key sets. Put differently: The key always consists of only one component.

As an extension of the one-dimensional container type map to two-dimensional key sets, LEDA offers the class map2. In this structure, a value v can be stored, associated to a pair (s1,s2) of two components of partial keys s1 and s2. So the structure manages containers of the form (s1,s2,v), in which v can be accessed via a full key pair (s1, s2).

This class has the same interface as map and the same implementation by hashing with chaining and table doubling.

Further information on map2 can be found on the corresponding manual page.