Follow Techotopia on Twitter

On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
System/Network Admin
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Mail Systems
Eclipse Documentation

How To Guides
General System Admin
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Problem Solutions
Privacy Policy




Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

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 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)
template<class Assoc, class Count, class Gen>
void assocGen_n(Assoc& a, Count n, Gen g) {
while(n-- > 0)
#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;
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;
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,
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

   Reproduced courtesy of Bruce Eckel, MindView, Inc. Design by Interspire