9.1 The map Data Abstraction

Other Names for Maps

A map is an indexed data structure, similar to a vector or a deque. However, maps differ from vectors or deques in two important respects. First, in a map, unlike a vector or deque, the index values (called the key values) need not be integer, but can be any ordered data type. For example, maps can be indexed by real numbers, or by strings. Any data type for which a comparison operator can be defined can be used as a key. As with a vector or deque, elements can be accessed through the use of the subscript operator (although there are other techniques). The second important difference is that a map is an ordered data structure. This means that elements are maintained in sequence, the ordering being determined by key values. Because they maintain values in order, maps can very rapidly find the element specified by any given key (searching is performed in logarithmic time). Like a list, maps are not limited in size, but expand or contract as necessary as new elements are added or removed. In large part, a map can simply be considered to be a set that maintains a collection of pairs.

There are two varieties of maps provided by the standard library. The map data structure demands unique keys. That is, there is a one-to-one association between key elements and their corresponding value. In a map, the insertion of a new value that uses an existing key is ignored. A multimap, on the other hand, permits multiple different entries to be indexed by the same key. Both data structures provide relatively fast (logarithmic time) insertion, deletion, and access operations.

Pairs

Whenever you use a map or a multimap, you must include the map header file.

   # include <map>

©Copyright 1996, Rogue Wave Software, Inc.