ADTMap and ADTMultimap
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) |
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.
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 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) |