Easy C++


STL Tutorial - Lesson 3: Associative Containers

Associative Containers

by John Kopp

Support this site at no cost to you

With the sequence containers, the same data, that is, the same sequence could be stored in any of the containers. The issue in choosing a particular container was performance based on how the data would be manipulated, updated and accessed. Questions such as where in the sequence insertions and deletions would be made drove the choice of container. With the associative containers, the choice of container is driven by the nature of the data to be stored and manipulated, rather than performance. Some of the containers store key-value pairs, some just values. Some allow duplicates, some don’t. We’ll explore these differences in this lesson.

The associative containers are specialized to allow the fastest possible retrieval (or look up) of values. This retrieval is either by the values themselves or by a key, where each value has its own key. There are four standard associated containers that will be part of any implementation of the standard C++ library.

  • Set - No keys are used. Duplicates are not allowed.
  • Multiset - No keys are used. Duplicates are allowed.
  • Map - Key-value pairs are stored. Duplicates are not allowed.
  • Multimap - Key-value pairs are stored. Duplicates are allowed.

These standard associative containers are also known as sorted associative containers. They store their data internally in binary tree structures. A second set of associative containers, available in some C++ library implementations, is hashed associative containers. A hash is a set of successively more specific look-up tables, dividing the data into smaller and smaller subsets. The difference between these two sets of containers is performance. A binary tree will have access times bound by O(log(N)), where N is the number of elements in the tree. A hash will have faster average access times, but in the worst case, access time can be as large as O(N).

The hashed associative containers available in Microsoft's C++ implementation are:

  • hash_set
  • hash_multiset
  • hash_map
  • hash_multimap
We will concentrate on the use of the sorted associative containers. Their use is the same as their hashed cousins; only performance differs depending on the distribution of the data stored.

Previous Page       Next Page