Software Design Using C++
STL: Maps
What is a Map?
The map container class provides the programmer with a convenient way to
store and retrieve data pairs consisting of a key and an associated value.
Each key is associated with one value. (If you want to associate a key with
more than one value, look up the multimap container class.)
This is similar in some ways to what we have done elsewhere in these Web
pages with a list-based table
and a binary search
tree-based table. It is also similar to our
B-tree-based table,
although that was stored on disk whereas a map is stored in main memory.
Another difference is that our tables were unordered; they provided no
way to sequence through the data in key order. Maps are ordered, so that
you can step through the data if you like.
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.
You need to include the map header file to use maps. There
are a lot of available class functions. Some of the most basic ones are
outlined below. You cannot use random-access iterators with
the map class, but iterators can be used to traverse a map
in either ascending or descending key order.
empty, boolean function to report if the map is empty.erase, has several forms; one of these
removes the data pair having a given key.find, does a search for a particular key, returning
an iterator to the matching data pair.insert, also has several forms, the simplest of which
inserts one new data pair.size, returns the number of items currently in the map.
|
Example
A map is ideal for storing dictionary-like data, a symbol table, etc.
Our example program stores a very short dictionary of words and their
meanings in a map and then allows the user to interactively look up
words, in each case reporting their meanings if a match is found.
Although you can use key/value pairs that contain simple data items
like integers and floats, this program uses objects as both the keys
and the associated values. Each such object belongs to the class
LineClass, which is designed to contain one "line" of
text data (in this case, a word or its meaning). Note that it is
necessary to provide a < operator for the class used for the keys. This is
because a map is ordered according to the keys. Also, you need to provide a
default constructor
for the class used for the associated values.
In our example, each LineClass object contains a simple
C-style string to hold the data. The default constructor places an
empty string into this field (by just putting a NULL character, the
character that marks the end of a C-style string, into the first
location of the array of characters).
This program uses strcpy as a quick way to copy these C-style strings.
Note well that strcpy does not check to see if the destination
string has enough room for the data. This can open up one's software to a
buffer overflow attack, a well-known type
of security flaw. When writing professional software use a copy function that
does proper bounds checking instead. Follow the above link for further information
on this important topic.
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<LineClass, LineClass> 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<LineClass, LineClass> & 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
LineClass objects as its parameters. Note the use of
the LineClass 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 LineClass objects to
place into the pair as the key and associated value.
Dictionary.insert(pair<LineClass, LineClass>(LineClass("hot"),
LineClass("having a high temperature")));
Dictionary.insert(make_pair(LineClass("cold"),
LineClass("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<LineClass, LineClass>::iterator p;
LineType Meaning;
p = Dictionary.find(LineClass(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. Since that data field is
an object of class LineClass, we can in fact use the
GetLine class function on this field.
As an exercise you might want to modify the above program in various ways.
For one thing, the constants, types, class declaration, and function
prototypes could be placed in a header file. The class functions could
be placed in a separate .cpp file. You might also 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. (This file might be too long to be handled; you might
have to 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
Back to the main page for Software Design Using C++
|
Author: