Associative Arrays in C++ - Map(C++)


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:

These are worst-case times: there is no pathological input that might cause the performance to degrade beyond these bounds.

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.

Next topic: Suggested Applications
Previous topic: An Iterator Example

© 2005 The SCO Group, Inc. All rights reserved.
SCO OpenServer Release 6.0.0 -- 02 June 2005