Mapping strings to Other Things

Problem

You have objects that you need to store in memory, and you want to store them by their string keys. You need to be able to add, delete, and retrieve items quickly (with, at most, logarithmic complexity).

Solution

Use the standard container map, declared in , to map keys (strings) to values (any type that obeys value semantics). Example 6-6 shows how.

Example 6-6. Creating a string map

#include 
#include
#include 

using namespace std;

int main( ) {

 map strMap;

 strMap["Monday"] = "Montag";
 strMap["Tuesday"] = "Dienstag";
 strMap["Wednesday"] = "Mittwoch";
 strMap["Thursday"] = "Donnerstag";
 strMap["Friday"] = "Freitag";
 strMap["Saturday"] = "Samstag";
 // strMap.insert(make_pair("Sunday", "Sonntag"));
 strMap.insert(pair("Sunday", "Sonntag"));

 for (map::iterator p = strMap.begin( );
 p != strMap.end( ); ++p ) {
 cout << "English: " << p->first
 << ", German: " << p->second << endl;
 }

 cout << endl;

 strMap.erase(strMap.find("Tuesday"));

 for (map::iterator p = strMap.begin( );
 p != strMap.end( ); ++p ) {
 cout << "English: " << p->first
 << ", German: " << p->second << endl;
 }
}

 

Discussion

A map is an associative container that maps keys to values, provides logarithmic complexity for inserting and finding, and constant time for erasing single elements. It is common for developers to use a map to keep track of objects by using a string key. This is what Example 6-6 does; in this case, the mapped type happens to be a string, but it could be nearly anything.

A map is declared like this:

map, // The function/functor
 // used for sorting
 typename Alloc = std::allocator > // Memory allocator

Key and Value are the types of the key and associated value that will be stored in the map. LessThanFun is a function or functor that takes two arguments and returns true if the first is less than the second; the standard functor less is used by default. Alloc is the memory allocator, which defaults to the standard allocator.

Using a map is easy enough. Declare the type of the key and value like this:

map strMap;

This creates a map where both the key and the value are strings. Put objects in your map with operator[], which is intuitive and easy to read:

strMap["Monday"] = "Montag";
strMap["Tuesday"] = "Dienstag";
strMap["Wednesday"] = "Mittwoch"; // ...

This inserts elements into the map with the index (e.g., "Monday") as the key and the righthand side as the value. They are stored in order according to the LessThanFun template parameter, if you supplied one; if not, map uses std::less.

To get values out of a map, use operator[] on the righthand side of assignment, like this:

wedInGerman = strMap["Wednesday"];

In the manner of all standard containers, the value associated with the key "Wednesday" is copied into the object wedInGerman using operator=.

operator[] is a convenient way to insert or update items in, or retrieve values from a map, but it has subtle behavior that might not be what you expect. Strictly speaking, operator[k] returns a reference to the value associated with kwhether k exists in the map or not. If the k is in the map already, its associated value object is returned. If it doesn't, k is inserted and the value type's default constructor is used to create a value object for that key. To make this concrete, consider what the following code does:

map mapZipCodes; // There are zero elements now

string myZip = mapZipCodes["Tempe"]; // Nothing is in the map yet,
 // but what is count( ) now?

What's in myZip, and how many elements are in mapZipCodes now? Since operator[] inserts the key you give it if it doesn't already exist, myZip is an empty string and there is now one element in mapZipCodes. This might not be the behavior you expect, but whether it is or not, be aware that operator[] is not a const member function: there is always the possibility that it will change the state of the map by adding a node.

The insert member function provides an alternative for adding pairs to the map. insert performs a strict insert, not an insert/update as operator[] does. If you are using a map (and not a multimap, which can have duplicate keys), insert does nothing if the key already exists. By comparison, operator[] replaces the value object for the key you supply if it already exists.

But the syntax of insert requires a little more work than operator[], and this has to do with how a map stores your data. Consider this line from Example 6-6:

strMap.insert(std::make_pair("Sunday", "Sonntag"));

A map stores your key/value pairs in a pair object. A pair is a simple utility class template (declared in and included by ) that holds two values of two types. To declare a pair of strings, do this:

pair myPair;

The first and second elements in the pair are accessible by the public members first and second. If you use operator[] to access elements in a map, then you don't usually have to deal with pairs directly, but with many of the other member functions you do, so it's good to know how to create and reference pair objects. Iterators, for example, simply dereference to a pair object, so when you use them, as I did in Example 6-6, you ought to know how to get at the key and its value.

for (map::iterator p = strMap.begin( );
 p != strMap.end( ); ++p )
 cout << "English: " << p->first
 << ", German: " << p->second << endl;

The key is stored in first and the value is stored in second.

This doesn't explain why I used make_pair, though. make_pair is a helper function template that creates a pair object out of the arguments you give it. Some prefer this to calling the pair constructor because a class template can't use argument deduction to figure out its template parameters, whereas a function template can. Thus, these two lines of code are functionally equivalent:

strMap.insert(std::make_pair("Sunday", "Sonntag"));
strMap.insert(std::pair("Sunday", "Sonntag"));

maps prohibit duplicate keys. If you want to allow duplicate keys, you have to use a multimap, which is a map that permits multiple equivalent keys. Its interface is identical to map, but the behavior of the member functions is necessarily different. Table 6-1 lists the member functions that are in one but not the other, and explains any behavioral differences in the common member functions. map s and multimaps have some typedefs that describe the different values that are stored in them. In Table 6-1, I use them as follows:

 

key_type

This is the type of the key. In a string map declared as map, key_type would be string.

 

mapped_type

This is the type of the value that the key maps to. In a string map declared as map, mapped_type would be MyClass*.

 

value_type

This is the type of the object that contains a key and a value, which, in a map or mutimap, is a pair.

Table 6-1. map versus multimap

Member function	map, multimap, or both	Behavior
T& operator[] (const key_type& k)	map	Returns a reference to the value object stored with key k. If k is not already in the map, it is added and a value object is created with its default constructor.
iterator insert(const value_type& v) pair insert(const value_type& v)	Both	The first version inserts v into the mutimap and returns an iterator that points to the inserted pair. The second version inserts v into a map if there is not already a key in the map equivalent to the key of v. The pair returned contains an iterator that points to the pair that was inserted, if any, and a bool indicating whether the insert was successful or not.
iterator find(const key_type& k)	Both	Returns an iterator or a const_iterator that points to the mapped_type that corresponds to k. In a multimap, the iterator returned is not guaranteed to point to the first value equivalent to k. If there is no key equivalent to k, the returned iterator is equivalent to end( ).

Table 6-1 also shows the behavioral differences between map and multimap.

If operator[] doesn't work for you, there are other ways to find things in a map. You can use the find member function:

map::const_iterator p
 = strMap.find("Thursday");

if (p != strMap.end( ))
 cout << "Thursday = " << p->second << endl;

Just be aware that when you are using a multimap, the item returned isn't guaranteed to be the first element that is equivalent to the search key. If you want the first element that is not less than some value or not more than some value, use lower_bound or upper_bound. lower_bound returns an iterator to the first key/value pair equal to or greater than its key_type argument. In other words, if your map is filled with days of the week as in Example 6-6, the following will return an iterator that points to the pair containing "Friday" and "Freitag":

p = strMap.lower_bound("Foo");

if (p != strMap.end( ))
 cout << p->first << " = " << p->second << endl;

This is because "Friday" is the first key greater than or equal to "Foo". upper_bound works the same way, but in the opposite manner.

I mentioned at the beginning of this discussion that the elements in a map are stored in sorted order according to their keys, so if you iterate from begin to end, each element is "greater" than the previous element (in a multimap it is greater than or equal to). But if you aren't using something as trivial as strings or numbers as your keys, you may have to specify how keys are compared when the map has to determine what should be inserted where.

By default, keys are sorted using the standard functor less (declared in ). less is a binary function (takes two arguments of the same type) that returns a bool indicating whether the first argument is less than the second. In other words, less(a, b) returns a < b. If this is not what you want, create your own functor and declare the map using it instead. For example, if you have a Person object as your key, and each Person has a last name and a first name, you may want to compare last names and first names. Example 6-7 presents one way to do this.

Example 6-7. Using your own sorting functor

#include 
#include
#include 

using namespace std;

class Person {
 friend class PersonLessThan;
public:
 Person(const string& first, const string& last) :
 lastName_(last), firstName_(first) {}
 // ...
 string getFirstName( ) const {return(firstName_);}
 string getLastName( ) const {return(lastName_);}
private:
 string lastName_;
 string firstName_;
};

class PersonLessThan {
public:
 bool operator( )(const Person& per1,
 const Person& per2) const {
 if (per1.lastName_ < per2.lastName_) // Compare last
 return(true); // names, then
 else if (per1.lastName_ == per2.lastName_) // first
 return(per1.firstName_ < per2.firstName_);
 else
 return(false);
 }
};

int main( ) {

 map personMap;

 Person per1("Billy", "Silly"),
 per2("Johnny", "Goofball"),
 per3("Frank", "Stank"),
 per4("Albert", "Goofball");

 personMap[per1] = "cool";
 personMap[per2] = "not cool";
 personMap[per3] = "not cool";
 personMap[per4] = "cool";

 for (map::const_iterator p =
 personMap.begin( ); p != personMap.end( ); ++p) {
 cout << p->first.getFirstName( ) << " " << p->first.getLastName( )
 << " is " << p->second << endl;
 }
}

maps are a great way to store key/value pairs. Once you understand the subtle behavior, such as how operator[] works and how the pairs are actually stored (as pair objects), maps provide great ease of use and good performance.

See Also

Recipe 6.7