Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |
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
sequences, which doesn t make sense with associative containers), but the job
is fairly easy, since you have the <algorithm> header file to work
from:
//: 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).
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. (It can also be used with multimap and multiset.)
First, some templatized 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;
}
} ///:~
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,
and explained once again after Thesaurus.cpp later on in this chapter.)
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 <iterator>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include "SimpleGenerators.h"
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 won t work if the operator<< isn t created. Since it s a
template, it is automatically instantiated for pair<int, int>.
Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |