The map Abstract Data Type

Recent textbooks on data structures often include a discussion of a data structure called a "map", which may also be called a "dictionary" or a "table", though these terms for similar concepts have been around longer. The map, like the vector, is an "indexed collection", but, unlike the vector, the index values need not be integer, and can instead be any kind of ordered data values (strings, for example). These "non-integral indices" nevertheless allow us to store and retrieve values which are accessible via their corresponding indices in a manner analogous to the use of integral indices, at least from a user's point of view. A convenient way to think of a map, therefore, is as a collection of associations of key/value pairs, and you will also see the term associative array used in this context, particularly in scripting languages like Perl and PHP.

In any case, the map container class of the C++ STL supports an "associative" container in which unique keys are "mapped" to their corresponding values. These key/value pairs are, in fact, kept in STL pair structs which we refer to as the "elements" or "items" of the map.

A useful concrete example to keep in mind when you're thinking about maps is a "telephone directory", i.e., a sequence of key/value pairs that would allow you to look up a value (such as a phone number), given a key (such as a name).

Map Operations
Generic (ADT) Specific (STL)
Construct a map
Default constructor map<Tkey, Tval> m;
Copy constructor map<Tkey, Tval> m(otherMap);
Construct a map from a range of elements map<Tkey, Tval> m(inputIter1, inputIter2);
Test a map
Test for emptiness empty()
Add one or more elements to a map
Insert the element passed and return a pair struct containing the iterator position of that element (or of the previously existing element) and a boolean indicating whether the insertion succeeded insert(element)
Insert the element passed, with iter a "hint" at the location (for efficiency purposes) and return the iterator position of the inserted element (or of the previously existing element) insert(iter, element)
Insert elements from the given range, but return nothing insert(startIter, endIter)
Remove one or more elements from a map
Remove all elements clear()
Remove the element(s) with key(s) equal to keyVal erase(keyVal)
Remove element at the iterator position erase(iter)
Remove all elements in the given range erase(startIter, endIter)
Retrieve value of a map element
Return value corresponding to a given key
But, and take special note of this behavior:
If an element with key value keyVal does not exist, an element with this key value and the default value of Tval (the value type of the key/value pairs for this map) is inserted into the map mapName.]
mapName[keyVal]
Search operations
Return number of elements (0 or 1) having the given key value count(keyVal)
Return iterator position of element whose key is same as keyVal, or end() find(keyVal)
Return first iterator position where keyVal would be inserted (position of first element with key value >= keyVal) lower_bound(keyVal)
Return last iterator position where keyVal would be inserted (position of first element with key value > keyVal) upper_bound(keyVal)
Return the values of lower_bound(keyVal) and upper_bound(keyVal) as a pair struct, with lower_bound first and upper_bound second equal_range(keyVal)
Retrieve map size
Return the maximum size max_size()
Return the current size size()
Miscellaneous map operations
Exchange the contents of one map with another swap(otherMap)

What kind of iterator does the map container provide?

The map<T>::iterator and map<T>::reverse_iterator iterators are bidirectional iterators, the second-most powerful kind of STL iterator. The member function begin() returns the iterator position of the first element of the map (the element whose key is first in the list of keys), while end() is a member function returning the iterator position "one past the end" of the map (one past the element whose key is the last key in the list of keys). Analogously, rbegin() and rend() return the iterator positions of the last element, and "one before the first element", respectively.

When should a map container class be used?

The map container class should be used whenever you need to deal with key/value pairs which are stored in sorted key order and you need fast retrieval.

The map class is one of the four "associative" container classes in the STL. The multimap, the set, and the multiset are the other three.

The multimap Abstract Data Type

The multimap is like the map, except that it allows elements with duplicate keys. But because of this, one of the insert functions in the multimap interface has a different return value from the corresponding function in the map interface, and the count function may now return a value other than 0 or 1, as shown in the table below:

Multimap Operations
Generic (ADT) Specific (STL)
Insert the element passed and return the iterator position of that element insert(element)
Return number of elements having the given key value count(keyVal)