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; }