text: 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
  Creation
  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; }