Map

Overview

The STL map class template is an example of an associative container. The map template associates, or maps, values of some key type to values of some other type. For example, it is possible to use a map to associate names represented as strings with some other type that you chose, such as floating-point values. This would allow you to associate a person's name with a bank account balance, grade point average, etc.

Associative containers similar to maps are often referred to as associative arrays in other programming languages. Those familiar with the Perl programming language recognize associative arrays (hashes) as a fundamental data type in that language. Traditional arrays allow access to elements by their position in the array. For example, you have direct access to the 1^st element, 2^nd element, and so on. However, if you wish to locate an element that contains the string "John Doe," then you will have to write code that searches through the array until a matching element is encountered.

The map container allows you to directly access elements based upon a key value, so that if you want to associate a value of 3.2 with the name John Doe, you can write a much more elegant expression such as:

aMap["John Doe"] = 3.2;

For map, each key must be unique. For example,

aMap["John Doe"] = 6.4;

would replace whatever value was previously associated with the string "John Doe" with 6.4.

To use the map template, you must #include <map>. Some older C++ compilers may require you to #include <map.h> instead, because this was the name of the file that was used in the original Hewlett Packard implementation of the STL. To declare an instance of a map, you must pass the key type and the value type as template parameters. Like all of the C++ Standard Library, map is part of the std namespace. The following is an example declaration of a map that associates strings with doubles.

#include <map>
using namespace std;
void SomeFunction()
{
    map<string, double> aMap;
}

Not Quite That Simple

You must be careful when using a map as an associative array. The [] operator may not have the semantics you think it should. Operator [] for map uses this basic algorithm:

1. Search the map for key.

2. If key is found, return a reference to the value object associated with key.

3. If key is not found, create a new object of type value associated with key, and return a reference to that.

The problem is step 3. Whether the [] operator is used in an expression that is an r-value or an l-value, it will create a new object of the value type if the key is not found and return a reference to it. These are often not the desired semantics, as in:

double GPA = aMap["John Doe"]; // Wrong! aMap["John Doe"] will be created if it does not exist and default to 0.0!

Instead, you should use the find() method of map, which will search for an element that matches key, but will not create the element if it does not exist. The find() method returns an iterator to a pair object, or map::end() if the key was not found. The first member of the pair contains the key and the second member of the pair contains the value associated with key. The above line would be correctly written:

map<string, double>::iterator itr;

if ( (itr = aMap.find("John Doe")) == aMap.end()) 
	cerr << "John Doe not found." << endl;
else 
	cout << "John Doe has a " << itr->second << " GPA" << endl;

More on the Pair Class Template

As stated above, the find() method returns an iterator to a pair object. The pair class template, declared in <utility>, contains two objects of specific types. Pair objects have two public members, first and second, which provide access to the elements that comprise a pair. The map class template uses key/value pairs to store the key/value associations. pair::first represents the key, while pair::second represents the value associated with key.

As a side note, the easiest way to construct a pair is with the convenience function template make_pair(). It accepts two objects, and returns a pair that contains copies of those two objects. For example:

pair<string,double> p;
p = make_pair(string("Microsoft Share Price"), double(85.27));

Characteristics Of Map

You may be wondering what mechanism the map container uses to accomplish these key/value associations. While the C++ standard does not specifically require that the map container be implemented using any specific data structure, the time complexity requirements imposed by the standard for each map operation suggest a balanced binary search tree. Many STL implementations use a red/black tree to implement map. Map operations such as searching for an element or adding an element are O(log n) operations. Logarithmic time complexity for these common operations means that maps are suitable for storing a collection of almost any size, including large collections. Also, map provides bidirectional iterators.

Element Requirements

The map class template requires that key and value types be assignable, which just means that these types should have an assignment operator that does what it should, such as performing a deep copy if necessary. Basically, the target of an assignment for these types must be independent but equal to the source of the assignment. The independence property should be carefully observed. For example, after the assignment "a=b;", a change to b should not affect a. If a and b were linked lists and a shallow copy was used the perform the assignment, then a and b would not be independent.

Also, the key type used in a map must adhere to strict weak ordering. Strict weak ordering means the following:

1. a<a is false.

2. Equality can be determined by the expression (!(a<b) && !(b<a)). That is, equality can be determined using only the less than operator.

3. If a<b and b<c, then a<c must be true.

Note that a, b, and c are objects of the key type, and the less than operator is assumed to be used when comparing two objects.

Any type that does not satisfy the above three rules is not a strict weak ordered type. Note that the built-in data types (char, int, double, etc.) are all strict weak ordered types.

Lastly, the value type used by the map must have a defined default constructor. The built-in data types, while they do not have a "default constructor" in the pure sense, are default constructable by definition and satisfy this requirement.

Methods

Map defines the following methods:

Operation	Description	Time Complexity
swap	Swaps elements with another map. This operation is performed in constant time. Ex: map1.swap(map2);	O(1)
begin	Returns an iterator to the first pair in the map. Ex: itr = map1.begin();	O(1)
end	Returns an iterator that is just beyond the end of the map.	O(1)
size	Returns the number of elements contained by the map. You should use empty() to test whether or not size equals 0, because empty() may be much faster. cout << map1.size();	O(n) or better.
empty	Returns true if the map contains zero elements.	O(1)
operator[]	Accepts a key and returns a reference to the object associated with key. Note that this operator always creates an element associated with key if it does not exist.	O(log n)
find	Accepts a key and returns an iterator to the pair element if found. If the key is not found in the map, this method returns end(). if ( (itr = map1.find("Bob")) == map1.end()) cerr << "Bob was not found in the map." << endl; else cout << "Bob was found in the map." << endl;	O(log n)
erase	There are three overloaded forms of this method. The first accepts a single iterator, and removes the element implied by the iterator from the map. The map should be non-empty. O(1). Ex: assert(!map1.empty()); map1.erase(map1.begin()); // remove the first element The second accepts two iterators, that specify a range of values within the map to be removed. The time complexity is logarithmic plus linear time for the length of the sequence being removed. The two iterators must be valid iterators within the sequence contained by the map. Formally, the range of values [starting, ending) are removed. At worst, this is an O(n) operation. Ex: map1.erase(map1.begin(), map1.end()); // erase the entire map The last accepts an object of the key type, and removes all occurrences of the key from map. Note that since map elements all have unique keys, this will erase at most 1 element. O(log n). Ex: map1.erase(string("Bob")); // removes all occurences of "Bob"	See description

Other, less frequently used methods are defined for maps. Consult a reference for documentation on these.

Notes on Interpreting the Above Table

For the code examples, <map> is assumed to be included, and the following declarations are assumed:

map<string, double> map1;

map<string, double> map2;

map<string, double>::iterator itr;

Other notes on interpreting this table can be found in the document on the list container.

Author: Rodney Myers, 3/4/00