Definition
An instance D of the parameterized data type p_dictionary<K,I> is a set of items (type p_dic_item). Every item in D contains a key from the linearly ordered data type K, called the key type of D, and an information from data type I, called the information type of D. If K is a user-defined type, you have to provide a compare function (see Section User Defined Parameter Types).The number of items in D is called the size of D. A dictionary of size zero is called empty. We use < k, i > to denote an item with key k and information i (i is said to be the information associated with key k). For each k K there is at most one item < k, i > D.
The difference between dictionaries (cf. section Dictionaries) and persistent dictionaries lies in the fact that update operations performed on a persistent dictionary D do not change D but create and return a new dictionary D'. For example, D.del(k) returns the dictionary D' containing all items it of D with key(it) ! = k. Also, an assignment D1 = D2 does not assign a copy of D2 (with new items) to D1 but the value of D2 itself.
#include < LEDA/core/p_dictionary.h >
Creation
p_dictionary<K,I> | D | creates an instance D of type p_dictionary<K,I> and initializes D to an empty persistent dictionary. |
Operations
Implementation
Persistent dictionaries are implemented by leaf oriented persistent red black trees. Operations insert, lookup, del_item, del take time O(log^{2}n), key, inf, empty, size and change_inf take time O(1). The space requirement is O(1) for each update operation.