Thinking In C++. Volume 2: Practical Programming

So to retrace the steps, map::value_type is a pair of the key and the value of the map—actually, it’s a single entry for the map. But notice that pair packages its objects by value, which means that copy-constructions are necessary to get the objects into the pair. Thus, the creation of tmp in map::operator[ ] will involve at least a copy-constructor call and destructor call for each object in the pair. Here, we’re getting off easy because the key is an int. But if you want to really see what kind of activity can result from map::operator[ ], try running this:

//: C07:NoisyMap.cpp

// Mapping Noisy to Noisy

//{L} ../TestSuite/Test

#include "Noisy.h"

#include

using namespace std;

int main() {

  map mnn;

  Noisy n1, n2;

  cout << "\n--------\n";

  mnn[n1] = n2;

  cout << "\n--------\n";

  cout << mnn[n1] << endl;

  cout << "\n--------\n";

} ///:~

You’ll see that both the insertion and lookup generate a lot of extra objects, and that’s because of the creation of the tmp object. If you look back up at map::operator[ ], you’ll see that the second line calls insert( ), passing it tmp—that is, operator[ ] does an insertion every time. The return value of insert( ) is a different kind of pair, in which first is an iterator pointing to the key-value pair that was just inserted, and second is a bool indicating whether the insertion took place. You can see that operator[ ] grabs first (the iterator), dereferences it to produce the pair, and then returns the second, which is the value at that location^.

So on the upside, map has this fancy "make a new entry if one isn’t there" behavior, but the downside is that you always get a lot of extra object creations and destructions when you use map::operator[ ]. Fortunately, AssociativeBasics.cpp also demonstrates how to reduce the overhead of insertions and deletions, by not using operator[ ] if you don’t have to. The insert( ) member function is slightly more efficient than operator[ ]. With a set, you hold only one object, but with a map, you hold key-value pairs; so insert( ) requires a pair as its argument. Here’s where make_pair( ) comes in handy, as you can see.

For looking objects up in a map, you can use count( ) to see whether a key is in the map, or you can use find( ) to produce an iterator pointing directly at the key-value pair. Again, since the map contains pairs, that’s what the iterator produces when you dereference it; so you have to select first and second. When you run AssociativeBasics.cpp, you’ll notice that the iterator approach involves no extra object creations or destructions at all. It’s not as easy to write or read, though.

Generators and fillers for associative containers

You’ve seen how useful the fill( ), fill_n( ), generate( ), and generate_n( ) function templates in have been for filling the sequential containers (vector, list, and deque) with data. However, these are implemented by using operator= to assign values into the sequential containers, and the way that you add objects to associative containers is with their respective insert( ) member functions. Thus, the default "assignment" behavior causes a problem when trying to use the "fill" and "generate" functions with associative containers.

One solution is to duplicate the "fill" and "generate" functions, creating new ones that can be used with associative containers. It turns out that only the fill_n( ) and generate_n( ) functions can be duplicated (fill( ) and generate( ) copy in between two iterators, which doesn’t make sense with associative containers), but the job is fairly easy, since you have the header file to work from (and since it contains templates, all the source code is there):

//: C07:assocGen.h

// The fill_n() and generate_n() equivalents

// for associative containers.

#ifndef ASSOCGEN_H

#define ASSOCGEN_H

template

void

assocFill_n(Assoc& a, Count n, const T& val) {

  while(n-- > 0)

    a.insert(val);

}

template

void assocGen_n(Assoc& a, Count n, Gen g) {

  while(n-- > 0)

    a.insert(g());

}

#endif // ASSOCGEN_H ///:~

You can see that instead of using iterators, the container class itself is passed (by reference, of course, since you wouldn’t want to make a local copy, fill it, and then have it discarded at the end of the scope).

This code demonstrates two valuable lessons. The first is that if the algorithms don’t do what you want, copy the nearest thing and modify it. You have the example at hand in the STL header, so most of the work has already been done.