Performance

Associative arrays greatly simplify many programming tasks, but that is almost irrelevant if they are too expensive to use. Thus, while a map will never be as fast as an ordinary array, we have gone to some effort to ensure that the map classes perform reasonably well. In general, for a map with n elements:

• Searching for an element takes "O(log n)" time.

• Inserting a new element takes "O(log n)" time plus the time to call malloc once.

• Incrementing or decrementing an iterator takes "O(log n)" time. Visiting every element of a map takes O(n) time (not "O(n log n)" )

• Removing a single map element takes "O(log n)" time.

• Copying an entire map takes "O(n log n)" time.

A map takes a trivial amount of space for the map itself plus an additional overhead per element of three pointers, two characters, and whatever additional overhead malloc imposes. Note that maps only require memory to be allocated for the elements actually stored.

What about absolute execution time?

As an example, we wrote a small program to generate 20,000 random integers and store them in a conventional array and a map. On the small machine on which we tried it, it takes 0.9 seconds to fill the conventional array and 8.8 seconds to fill the map, including the time spent in the rand function. So in this application maps are about ten times slower than conventional arrays.

But of course maps are not intended to replace conventional arrays where speed is all that matters -- they do other things as well. For instance, storing values in a map has the side effect of sorting them by key. Thus using the random numbers as keys sorts them for free. Picking them out of the map again takes 0.8 seconds. In other words, using a map to sort 20,000 random integers takes 9.6 seconds: 8.8 seconds to put them in and 0.8 to take them out again.

In contrast, using the qsort routine to sort the conventional array takes 17 seconds.