Noeud:Map, Noeud « Next »:Multimap, Noeud « Previous »:Multiset, Noeud « Up »:Containers and Iterators
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.