Map

map stores elements via a key:value pairing. The key can be any data type, providing there exists a sorting criterion for it. The elements themselves do not need to have any such ordering since they are inserted and ordered depending on their key. So whereas with the previous examples regarding sets, we ordered elements via the name of each Address, because the key was the Address object itself, now we can store the Address objects via some independent key. For example, we could provide an identification number for each Address inserted; or come up with some other way of identifying a key for each element. As with set, map does not allow for duplicate elements; you have to use multimap for this. You use map by including <map>.

Since you add a key and a value, elements are added as a pair object. Let's begin with an example where we insert Address objects into a map, giving them an int key based on the order that they were inserted:

     /* map1.cc
        Compiled using g++ map1.cc Address.cc -o map1 */
     #include <map>
     #include "AddressRepository.hh"
     
     int main()
     {
       std::map<int, Address> map1;
       /* first way of inserting an element: */
       map1.insert(std::pair<int, Address>(1, addr1));
       /* second way of inserting an element: */
       map1.insert(std::map<int, Address>::value_type(2, addr2));
       /* third way of inserting an element: */
       map1.insert(std::make_pair(3, addr3));
       /* finally, add the rest using the first method of insertion: */
       map1.insert(std::pair<int, Address>(4, addr4));
       map1.insert(std::pair<int, Address>(5, addr5));
     
       std::map<int, Address>::iterator pos;
       for (pos = map1.begin(); pos != map1.end(); ++pos)
         {
           cout << "(" << pos->first << ") ";
           Address addr = pos->second;
           addr.print();
         }
       exit(0);
     }
     

     Example 3.14: map1.cc
     

As you can see, there are a few more complexities to deal with with map regarding inserting elements. What exactly are we putting in the map? With the previous containers, we inserted the object in question - for containers of integers, we used integers; for containers of Address objects we added the Address object itself. However, since a map contains a key:value pairing, the most obvious way to store elements is in a pair; this is achieved by using the pair class. There are three ways to insert elements into a map (and multimap) in a pair. Let's look at them each in turn:

pair is defined in <utility>, although we don't need to include the header file since map and multimap include it. pair is used to store (not surprisingly) two values. The insert method for map is the same as for the other containers - in other words, it takes one value, namely an element. However, since map has a key:value paring, we need some way to deal with this. In this instance, when we declare

map1.insert(std::pair<int, Address>(1, addr1));

we're saying that the object inserted is a pair object; it takes an int and and Address (in the declaration <int, Address>), the first element is 1 (the key) and the second element is addr1 (the value).

Another way to insert a pair into a map is to use value_type, which is defined differently for different containers. For map and multimap, it is a pair. So the declaration std::map<int, Address>::value_type(2, addr2) in the second call to insert is saying that the arguments 2 and addr2 are passed to the map container, which is implicitly a pair object per element inserted.

The third way of inserting a pair is to call make_pair, which simply returns a pair object from the two arguments passed to it.

So when we put objects into a map, we've got to put - yes, you've got it - a pair object. That's fine; so how do we access elements of a pair?

This is demonstrated in the for loop:

       std::map<int, Address>::iterator pos;
       for (pos = map1.begin(); pos != map1.end(); ++pos)
         {
           cout << "(" << pos->first << ") ";
           Address addr = pos->second;
           addr.print();
         }
     

We first create an iterator to be able to traverse the container, and in the body of the for loop make the usual calls to begin() and end(). The key:value pairings are stored in the members first (for the key) and second (for the value) of the pair.

The output is obvious, so it's been omitted here; it's just the different Address objects preceeded by (n) where n is the number assigned to the map for that specific element. The Address object with the name of "Jane" exists twice within the map; this is because we are now inserting elements according to a different sorting criterion - int - and since there are no duplicates (our integers go from 1 to 5 in the above example), all elements are inserted successfully. However, if we'd have decided to give each element a key value of 1 (or any other number, providing the number's the same), only one Address object would have been inserted.

Let's talk about efficiency. If elements are stored as key:value pairings, it makes sense that we'll be able to access keys efficiently; this is true, and can be achieved in logarithmic time. This raises an important issue: if we want to change the key, how will elements be reordered and be consistent?

The answer is that we cannot change the key. Instead we have to remove the element with the key we wish to change and insert a new key (the one we wish to change the old key to) with the old value.