Both generators expect that T can be incremented, and they simply use operator++ to generate new values from whatever you used for initialization. PairGen creates an STL pair object as its return value, and that’s what can be placed into a map or multimap using insert( ).
The last function is a generalization of operator<< for ostreams, so that any pair can be printed, assuming each element of the pair supports a stream operator<<. (It is in namespace std for the strange name lookup reasons discussed in Chapter 5.) As you can see in the following, this allows the use of copy( ) to output the map:
//: C07:AssocInserter.cpp
// Using an insert_iterator so fill_n() and
// generate_n() can be used with associative
// containers
#include "SimpleGenerators.h"
#include <iterator>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
int main() {
set<int> s;
fill_n(inserter(s, s.begin()), 10, 47);
generate_n(inserter(s, s.begin()), 10,
IncrGen<int>(12));
copy(s.begin(), s.end(),
ostream_iterator<int>(cout, "\n"));
map<int, int> m;
fill_n(inserter(m, m.begin()), 10,
make_pair(90,120));
generate_n(inserter(m, m.begin()), 10,
PairGen<int, int>(3, 9));
copy(m.begin(), m.end(),
ostream_iterator<pair<int,int> >(cout,"\n"));
} ///:~
The second argument to inserter is an iterator, which is an optimization hint to help the insertion go faster (instead of always starting the search at the root of the underlying tree). Since an insert_iterator can be used with many different types of containers, with non-associative containers it is more than a hint—it is required.
Note how the ostream_iterator is created to output a pair; this wouldn’t have worked if the operator<< hadn’t been created, and since it’s a template, it is automatically instantiated for pair<int, int>.
The magic of maps
An ordinary array uses an integral value to index into a sequential set of elements of some type. A map is an associative array, which means you associate one object with another in an array-like fashion, but instead of selecting an array element with a number as you do with an ordinary array, you look it up with an object! The example that follows counts the words in a text file, so the index is the string object representing the word, and the value being looked up is the object that keeps count of the strings.
In a single-item container such as a vector or a list, only one thing is being held. But in a map, you’ve got two things: the key (what you look up by, as in mapname[key]) and the value that results from the lookup with the key. If you simply want to move through the entire map and list each key-value pair, you use an iterator, which when dereferenced produces a pair object containing both the key and the value. You access the members of a pair by selecting first or second.
This same philosophy of packaging two items together is also used to insert elements into the map, but the pair is created as part of the instantiated map and is called value_type, containing the key and the value. So one option for inserting a new element is to create a value_type object, loading it with the appropriate objects and then calling the insert( ) member function for the map. Instead, the following example uses the aforementioned special feature of map: if you’re trying to find an object by passing in a key to operator[ ] and that object doesn’t exist, operator[ ] will automatically insert a new key-value pair for you, using the default constructor for the value object. With that in mind, consider an implementation of a word-counting program:
//: C07:WordCount.cpp
// Count occurrences of words using a map
#include "../require.h"
#include <string>
#include <map>
#include <iostream>
#include <fstream>
using namespace std;
typedef map<string, int> WordMap;
typedef WordMap::iterator WMIter;
int main(int argc, char* argv[]) {
char* fname = "WordCount.cpp";
if(argc > 1) fname = argv[1];
ifstream in(fname);
assure(in, fname);
WordMap wordmap;
string word;
while(in >> word)
wordmap[word]++;
for(WMIter w = wordmap.begin(); w != wordmap.end(); w++)
cout << w->first << ": "
<< w->second << endl;
} ///:~
This example shows the power of zero-initialization. Consider this line of code from the program above:.
wordmap[word]++;
This increments the int associated with word. If there isn’t such a word yet in the map, a key-value pair for the word is automatically inserted, with the value initialized to zero by a call to the pseudo-constructor int( ), which returns a 0.
Printing the entire list requires traversing it with an iterator. (There’s no copy( ) shortcut for a map unless you want to write an operator<< for the pair in the map.) As previously mentioned, dereferencing this iterator produces a pair object, with the first member the key and the second member the value.
If you want to find the count for a particular word, you can use the array index operator, like this:
cout << "the: " << wordmap["the"] << endl;
You can see that one of the great advantages of the map is the clarity of the syntax; an associative array makes intuitive sense to the reader. (Note, however, that if "the" isn’t already in the wordmap, a new entry will be created!)
Multimaps and duplicate keys
A multimap is a map that can contain duplicate keys. At first this may seem like a strange idea, but it can occur surprisingly often. A phone book, for example, can have many entries with the same name.
Suppose you are monitoring wildlife, and you want to keep track of where and when each type of animal is spotted. Thus, you may see many animals of the same kind, all in different locations and at different times. So if the type of animal is the key, you’ll need a multimap. Here’s what it looks like: