//: C07:NoisyMap.cpp
// Mapping Noisy to Noisy
//{L} ../TestSuite/Test
#include "Noisy.h"
#include <map>
using namespace std;
int main() {
map<Noisy, Noisy> 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 <algorithm> 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 <algorithm> 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<class Assoc, class Count, class T>
void
assocFill_n(Assoc& a, Count n, const T& val) {
while(n-- > 0)
a.insert(val);
}
template<class Assoc, class Count, class Gen>
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.
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 <iostream>
#include <utility>
// A generator that increments its value:
template<typename T>
class IncrGen {
T i;
public:
IncrGen(T ii) : i (ii) {}
T operator()() { return i++; }
};
// A generator that produces an STL pair<>:
template<typename T1, typename T2>
class PairGen {
T1 i;
T2 j;
public:
PairGen(T1 ii, T2 jj) : i(ii), j(jj) {}
std::pair<T1,T2> operator()() {
return std::pair<T1,T2>(i++, j++);
}
};
namespace std {
// A generic global operator<<
// for printing any STL pair<>:
template<typename F, typename S> ostream&
operator<<(ostream& os, const pair<F,S>& p) {
return os << p.first << "\t"
<< p.second << endl;
}} ///:~