Maps

A map holds an arbitrary number of items of the same type, indexed by a key. Maps store one unique value per key. Maps have good random access and insertion performance. If a new value is assigned to an existing key, the old value is replaced by the new value.

Figure 11.3. A map of Films

Since maps contain keyvalue pairs, it is common to design data structures that work with maps in a slightly different way from those that are designed for use with vectors and lists. Here's a version of the Film class that we will use to illustrate map usage:

class Film { public: Film(const QString &title = "", int duration = 0); QString title() const { return myTitle; } void setTitle(const QString &title) { myTitle = title; } int duration() const { return myDuration; } void setDuration(int minutes) { myDuration = minutes; } private: QString myTitle; int myDuration; }; Film::Film(const QString &title, int duration) { myTitle = title; myDuration = duration; }

We don't store the catalog ID in the Film class since we will use that as the key to the map. Nor do we need the comparison operators for Film. Maps are ordered by their keys, not by their values.

The STL's map class is called std::map and is defined in . Here's an example of a map whose keys are ints (catalog IDs) and whose values are Films:

map films;

The Qt equivalent is QMap:

QMap films;

The most natural way to insert items into a map is to assign a value to a given key:

films[4812] = Film("A Hard Day's Night", 85); films[5051] = Film("Seven Days to Noon", 94); films[1301] = Film("Day of Wrath", 105); films[9227] = Film("A Special Day", 110); films[1817] = Film("Day for Night", 116);

The map iterator provides a keypair value. The key part is extracted using (*it).first and the value part using (*it).second:

map::const_iterator it = films.begin(); while (it != films.end()) { cerr << (*it).first << ": " << (*it).second.title().ascii() << endl; ++it; }

Most compilers also allow us to write it->first and it->second, but it's more portable to write (*it).first and (*it).second.

The Qt map's iterator differs slightly from the STL one. In a Qt map, the key is retrieved from an iterator using it.key() and the value with it.data():

QMap::const_iterator it = films.begin(); while (it != films.end()) { cerr << it.key() << ": " << it.data().title().ascii() << endl; ++it; }

When iterating over a map, the items are always ordered by key.

The [] operator can be used for both insertion and retrieval, but if [] is used to retrieve a value for a non-existent key, a new item will be created with the given key and an empty value. To avoid accidentally creating empty values, use the find() member function to retrieve items:

map::const_iterator it = films.find(1817); if (it != films.end()) cerr << "Found " << (*it).second.title().ascii() << endl;

This function returns the end() iterator if the key is not in the map.

In the example we have used an integer key, but other types of keys are possible, one popular choice being a QString key. For example:

map actorToNationality; actorToNationality["Doris Day"] = "American"; actorToNationality["Greta Garbo"] = "Swedish";

If we need to store multiple values for the same key, we can use multimap. If we only need to store keys, we can use set or multiset. Qt provides no equivalent for these classes.

Qt's QMap class has a couple of additional convenience functions that are especially useful when dealing with small data sets. QMap::keys() and QMap::values() return QValueLists of a map's keys and values.