Chapter 3. Associative container types

Table of Contents

3.1. Dictionaries (class dictionary)
3.2. Dictionary arrays (class d_array)
3.3. Hashing types
3.3.1. Hashing and hashed types
3.3.2. Hashing arrays (class h_array)
3.3.3. Maps (class map)
3.4. Sorted sequences (class sortseq)
3.4.1. Basic functionality
3.4.2. Finger search and fast insertion
3.4.3. Splitting, concatenating, and merging
3.5. dictionary, d_array, h_array, map, and sortseq compared
3.6. Implementation parameters
3.7. What we did not cover

This chapter describes the associative container types of LEDA. Unlike simple container types, these types store additional information with every single object. In this context, an object is called a key, the information associated to it a value. So the collection consists of key-value pairs.

The associated value can be accessed via a key. In general, the inversion does not hold, because several keys definitely can have the same value, so the mapping is not always invertible. The access time is generally very short thanks to the clever implementations of LEDA.