Learning objectives
When to use which associative container type 
A survey of the 5 associative container types of LEDA 
Two of the most frequently asked questions about the
associative container types of LEDA simply are “When do I
use which of these 5 types?” and “To objects of a
type K
, I must associate other objects of a type
V
. Do I take a d_array
or an
h_array
now, or what?” This section
tries to summarize what we said about these types until now, and
to give rules of thumb for their use. A survey of the types is
given in Table 3.1.
The most important deciding factor is for certain the type
of the keys that shall be used. Only the type int
,
pointer types and item types can be used in a
map
. The key type must be linearly ordered or
hashed for the other
container types. Usually, a linear order of one's own can easily
be defined; in contrast, finding a suitable hash function that
behaves well for a given distribution of the keys is
much more difficult to do in most cases.
If no special operations are required available for
sortseq
only, access time and space
consumption have to be weighed up as the next deciding
factor. Regarding this, the hashing
types h_array
and
map
generally have an advantage over the
other types. However, these types are of use only if one does not
have to iterate over the keys in a certain order. Moreover, no
keyvalue pair can be deleted in a map
,
which is necessary in structures that are dynamically growing and
shrinking.
Tip  

If one does not know at all or cannot even estimate what
one needs: One always can start with a

Table 3.1. dictionary
, d_array
, h_array
, and map
compared
dictionary  d_array  h_array  map  sortseq  

Key type  linearly ordered  linearly ordered  hashed  int or pointer type or item type  linearly ordered 
Access time  O(log n) worst case  O(log n) worst case  O(1) expected, O(n) worst case  O(1) expected, O(n) worst case. Faster than h_array  O(log n) worst case, O(log min(d,nd)) with finger search, O(1) expected when finger known 
Memory consumption  average  average  low  very low  high 
forall_defined order  sorted  sorted  unsorted  unsorted  sorted 
Deletion of a keyvalue pair possible?  yes  yes  yes  no  yes 
Splitting, concatenating, merging possible?  no  no  no  no  yes 
Insertion at a given position possible?  no  no  no  no  yes, with finger 
Persistence of variables?  yes  yes  no  no  yes 