3.5. dictionary, d_array, h_array, map, and sortseq compared

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 key-value pair can be deleted in a map, which is necessary in structures that are dynamically growing and shrinking.


If one does not know at all or cannot even estimate what one needs: One always can start with a sortseq (perhaps having to write a linear order function compare() by oneself) and, at the end, replace this sortseq by the structure whose operations one really needs and that behaves best in the given situation.

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

Key typelinearly orderedlinearly orderedhashedint or pointer type or item typelinearly ordered
Access timeO(log n) worst caseO(log n) worst caseO(1) expected, O(n) worst caseO(1) expected, O(n) worst case. Faster than h_arrayO(log n) worst case, O(log min(d,n-d)) with finger search, O(1) expected when finger known
Memory consumptionaverageaveragelowvery lowhigh
forall_defined ordersortedsortedunsortedunsortedsorted
Deletion of a key-value pair possible?yesyesyesnoyes
Splitting, concatenating, merging possible?nonononoyes
Insertion at a given position possible?nonononoyes, with finger
Persistence of variables?yesyesnonoyes