Section 2 - STL Maps

9B.2.1 Map as Key-Value Pairs

The STL map is very much like a set of STL pairs (first, second) in which the first item of the pair determines equality (i.e., two pairs are considered "equal" if and only if the first items in each pair are equal). In fact, the map is implemented, internally as just such a container.

Every element in a map is a pair (even if we don't use the pair terminology).
The first element of the pair is always used as the key, and must be unique. You cannot have two items in a map with the same first element, or key.
The second element of the pair is called the value. The same value can appear in more than one key-value pair in the map.
You insert elements into a map using the array brackets notation:
```
myMap[aKey] =  aValue ;  
```
You access elements in the map using the array brackets notation:
```
cout << myMap[aKey] ;
```
You mutate an element already in the map, by changing its value (i.e., second component) using array bracket notation:

myMap[aKeyAlreadyInTable] = aNewValue ;

If you have a map iterator, you can apply a pair's first/second terminology to get either component of the pair.

There are other properties of maps, but these are the big points. Let's see an example.

// A Map
// CS 2C Foothill College
#include <iostream>
#include <string>
#include <map>
#include <utility>
using namespace std;

int main()
{
   typedef map<string, int> FriendAgePair;
   typedef FriendAgePair::iterator FAIter;
 
   FriendAgePair myFriends;
   FAIter iter;

   myFriends["lisa"] = 49;
   myFriends["keith"] = 26;
   myFriends["adrian"] = 4;


   cout << "---------- The contents of the Map ------ " << endl;
   for ( iter = myFriends.begin(); iter != myFriends.end(); iter++)
      cout << (*iter).first << " is " 
         << iter->second << " years old. " << endl;

   // let's give adrian a birthday;
   myFriends["adrian"] ++;

   cout << "\nNow, Adrian is " << myFriends["adrian"] << endl;
}

The run:

---------- The contents of the Map ------
adrian is 4 years old.
keith is 26 years old.
lisa is 49 years old.

Now, Adrian is 5
Press any key to continue . . .

The example shows two different ways to access the iterator (*iter).first and iter->second -- you will see them both and neither should feel uncomfortable. As iterators act like pointers, this is nothing new to you.

I used the typedef notation again, to reinforce the syntax for you.

9B.2.2 Ordering in Maps

Like sets, maps imply an ordering. However in the case of maps, the ordering only need be present in the key type - the value does not have to be ordered. You will note that when you iterate through the map, the result is listed in increasing order, regardless of how we insert the elements. Indeed, this was true of sets (look at the last page -- the output was arranged alphabetically or numerically, depending on the < operation).

Everything we said about sets and ordering holds true here. You can change the definition of the < operator and get a totally different behavior. In the above example we used primitive types, but if we had user-defined types, we would easily be able to change < to mean whatever we wanted.

9B.2.3 A Little More Layered Example

Let's layer the data structure just a bit now. We start with a data structure called Star, similar to an Employee - it has a name (string) and mag (meaning magnitude, which is a double). Here is an outline of the class:

class Star
{
public:
   string name;
   double mag;
   Star(string n, double m) : name(n), mag(m) {}
   void show() { cout << name << " " << mag << endl; }
   bool operator<(const Star &rhs) const
   {
      return (name < rhs.name);
   }
};

As is commonly done with classes in C++, we will work with pointers to the objects, rather than the objects themselves. To this end, we define a StarPtr type:

   typedef Star* StarPtr;

We'll make a map whose pairs consist of StarPtrs and ints. The int associated with the Star object (pointed to) will represent the distance (in light years) from that start to some reference that is application dependent. In our application, we'll create a map with each element being a star (pointer) and its distance to Earth. Don't confuse the distance (an int that will be the value in the key-value pair of the map, completely outside the Star object) with the mag (which is a double and lives inside the Star object).

Here is some code to clarify that description.

typedef Star* StarPtr;
typedef map<StarPtr, int> StarList; // (star ptr, dist to reference)
typedef StarList::iterator StarListIter;

int main()
{
   Star sir("sirius", -1.42), can("canopus", -0.72), arc("archernar", 0.45),
      sun("sun", -26.7);

   StarList earthNeighbors;
   StarListIter iter;

   sir.show();  can.show(); arc.show(); sun.show();

   // put three stars into the list along with their dist to earth
   earthNeighbors[&sir] = 8 ;
   earthNeighbors[&can] = 316 ;
   earthNeighbors[&arc] = 144 ;

   cout << "---------- The contents of the Map ------ " << endl;
   for ( iter = earthNeighbors.begin(); 
      iter != earthNeighbors.end(); iter++)
      cout << iter->first->name << " (mag "<<  iter->first->mag 
         << ") is " << iter->second << " lyrs from earth. " << endl;
}

We now have more levels of indirection when we iterate through the map. We can't cout << iter->first, because first is a Star pointer and we have not overloaded the << operator for that type. Thus, it is necessary to get at the data. cout << iter->first->name is a very common construct.

cout << iter->first->name

The iterator is pointing to a pair in the map; the first element is a pointer to an object; that object has a name member that we will print.

In examples like this, I am using all public members to make the code easier to show in its entirety. If the name had been private, then we would need to write cout << iter->first->getName().

This is good code for you to study in preparation for next week's study in graphs. One of its features that you should really laser-down on is the notion that the map is built from StarPtr (or Star*) items -- pointers not objects. This is very common in C++.

The pointers are lightweight and require very little overhead when we pass them around.
They always admit a built-in ordering. We may not use the ordering directly, but at least it satisfies the implied < operation required of data types like map.
They are eminently unique, something that is very important when we are comparing two pointers for equality.
It allows us to store one master object somewhere. All the pointers will point to those master objects. If something changes in the object, all pointers know about it. If not, at least we don't have redundant data lying around.

The use and advantage of pointers noted here should be something you take away from the course. Pointers are not used when they're not needed, but at times like these, they really are.

Here is the output:

sirius -1.42
canopus -0.72
archernar 0.45
sun -26.7
---------- The contents of the Map ------
archernar (mag 0.45) is 144 lyrs from earth.
canopus (mag -0.72) is 316 lyrs from earth.
sirius (mag -1.42) is 8 lyrs from earth.
Press any key to continue . . .