Thinking In C++. Volume 2: Practical Programming

The second lesson is more pointed: if you look long enough, there’s probably a way to do it in the STL without inventing anything new. The present problem can instead be solved by using an insert_iterator (produced by a call to inserter( )), which calls insert( ) to place items in the container instead of operator=. This is not simply a variation of front_insert_iterator or back_insert_iterator, because those iterators use push_front( ) and push_back( ), respectively. Each of the insert iterators is different by virtue of the member function it uses for insertion, and insert( ) is the one we need. Here’s a demonstration that shows filling and generating both a map and a set. (Of course, it can also be used with multimap and multiset.) First, some templatized, simple generators are created. (This may seem like overkill, but you never know when you’ll need them; for that reason they’re placed in a header file.)

//: C07:SimpleGenerators.h

// Generic generators, including

// one that creates pairs

#include

#include

// A generator that increments its value:

template

class IncrGen {

  T i;

public:

  IncrGen(T ii) : i (ii) {}

  T operator()() { return i++; }

};

// A generator that produces an STL pair<>:

template

class PairGen {

  T1 i;

  T2 j;

public:

  PairGen(T1 ii, T2 jj) : i(ii), j(jj) {}

  std::pair operator()() {

    return std::pair(i++, j++);

  }

};

namespace std {

// A generic global operator<<

// for printing any STL pair<>:

template ostream&

operator<<(ostream& os, const pair& p) {

  return os << p.first << "\t"

    << p.second << endl;

}} ///:~

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

#include

#include

#include

#include

using namespace std;

int main() {

  set s;

  fill_n(inserter(s, s.begin()), 10, 47);

  generate_n(inserter(s, s.begin()), 10,

    IncrGen(12));

  copy(s.begin(), s.end(),

    ostream_iterator(cout, "\n"));

  map m;

  fill_n(inserter(m, m.begin()), 10,

    make_pair(90,120));

  generate_n(inserter(m, m.begin()), 10,

    PairGen(3, 9));

  copy(m.begin(), m.end(),

    ostream_iterator >(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.

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.