Software Design Using C++

STL: Maps

What is a Map?

Maps are guaranteed to be efficient. In general, inserting a new item into a map is supposed to take O(lg(n)) time, where n is the number of items in the map. However, if you want to insert at a specific location (specified by an iterator), it takes on average O(n) time. You can also sequence through the items in a map using an iterator, in ascending order by key, probably in an efficient manner as well, though this author knows of no specific time guarantee. Note, also, that we don't necessarily know what underlying data structure is used by a map.

Example

To create an empty map that can hold pairs of such objects we use the following. Note that, unlike what was done in this example, it is legal to use a different type for the key (first item in the pair) and the value (second item in the pair).

map<string, string> Dictionary;

Note that the same notation is used in specifying the type for the map when passing it as a parameter to the helping functions. For example, here is the header for one of the two helping functions:

void LoadData(map<string, string> & Dictionary)

Inside the code for this function you see the two basic methods for creating a data pair for inserting into the map. The first one was created by using the pair constructor, with two string objects as its parameters. Note the use of the string class constructor in each case to build an object from the C-style string supplied. In the second insertion, the make_pair generic function was used to create the pair. It, too, was handed two string objects to place into the pair as the key and associated value.

Dictionary.insert(pair<string, string>(string("hot"),
   string("having a high temperature")));
Dictionary.insert(make_pair(string("cold"),
   string("having a low temperature")));

The code for the Lookup function is shown below. It illustrates how to use an iterator, p, with the find class function.

map<string, string>::iterator p;
string Meaning;

p = Dictionary.find(Target);
if (p != Dictionary.end())
   {
   p->second.GetLine(Meaning);
   cout << "Meaning is: " << Meaning << endl;
   }
else
   cout << "Word not found" << endl;

Note that the find function is used to look up a key object in the map named Dictionary. This function returns an iterator to the location where the match was found or an iterator to one past the end of the data if no match was found. Since the latter is the location given by end(), one typically tests to see if the iterator equals Dictionary.end() to see if no match was found. In the case where the key was found, note that the iterator returned is an iterator to a data pair, not to the value itself. The two fields of a pair are named first and second. These are the key and value, respectively. Thus you see in the code above p->second to get at the data value in the pair pointed to by the iterator p.

As an exercise you might want to modify the above program in various ways. For example, you might want to modify the program so that it reads the word and definition data from a suitable text file. That would certainly be more reasonable for a longer list of words. For example, you might want to use the text file btree.txt that was used in an earlier program. (If this file is too long to handle, you might cut it down in size.)

In general, the map container class is quite convenient for the programmer. It is a lot easier to use it than to write all of the code needed for your own map-like data structure. However, should you need to have control over the details of data storage, the latter would be the appropriate choice.

The map class has additional capabilities that are not covered here. There is also a multimap container class where the keys do not have to be unique. That is, a key can be associated with more than one value. See the references for more information.

Related Items