Definition
An instance D of the parameterized data type dictionary<K,I> is a collection of items (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 the 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 the empty dictionary. 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 i I with < k, i > D.
#include < LEDA/core/dictionary.h >
Types
dictionary<K,I>::item | the item type. |
dictionary<K,I>::key_type | the key type. |
dictionary<K,I>::inf_type | the information type. |
Creation
dictionary<K,I> | D | creates an instance D of type dictionary<K,I> based on the linear order defined by the global compare function and initializes it with the empty dictionary. |
dictionary<K,I> | D(int (*cmp)(const K& , const K& )) | |
creates an instance D of type dictionary<K,I> based on the linear order defined by the compare function cmp and initializes it with the empty dictionary. |
Operations
Iteration
forall_items(it, D) { ``the items of D are successively assigned to it'' }
forall_rev_items(it, D) { ``the items of D are successively assigned to it in reverse order'' }
forall(i, D) { ``the informations of all items of D are successively assigned to i'' }
forall_defined(k, D)
{ ``the keys of all items of D are successively assigned to k'' }
STL compatible iterators are provided when compiled with
-DLEDA_STL_ITERATORS (see LEDAROOT/demo/stl/dic.c
for an example).
Implementation
Dictionaries are implemented by (2, 4)-trees. Operations insert, lookup, del_item, del take time O(log n), key, inf, empty, size, change_inf take time O(1), and clear takes time O(n). Here n is the current size of the dictionary. The space requirement is O(n).
Example
We count the number of occurrences of each string in a sequence of strings.
#include <LEDA/core/dictionary.h> main() { dictionary<string,int> D; string s; dic_item it; while (cin >> s) { it = D.lookup(s); if (it==nil) D.insert(s,1); else D.change_inf(it,D.inf(it)+1); } forall_items(it,D) cout << D.key(it) << " : " << D.inf(it) << endl; }