ifstream in(argv[1]); assure(in, argv[1]); StreamTokenizer words(in); multiset<string> wordmset; string word;

while((word = words.next()).size() != 0) wordmset.insert(word);

typedef multiset<string>::iterator MSit; MSit it = wordmset.begin();

while(it != wordmset.end()) {

pair<MSit, MSit> p=wordmset.equal_range(*it); int count = distance(p.first, p.second);

cout << *it << ": " << count << endl; it = p.second; // Move to the next word

}

} ///:~

The setup in main( ) is identical to WordCount.cpp, but then each word is simply inserted into the multiset<string>. An iterator is created and initialized to the beginning of the multiset; dereferencing this iterator produces the current word. equal_range( ) produces the starting and ending iterators of the word that’s currently selected, and the STL algorithm distance( ) (which is in <iterator>) is used to count the number of elements in that range. Then the iterator it is moved forward to the end of the range, which puts it at the next word. Although if you’re unfamiliar with the multiset this code can seem more complex, the density of it and the lack of need for supporting classes like Count has a lot of appeal.

In the end, is this really a “set,” or should it be called something else? An alternative is the generic “bag” that has been defined in some container libraries, since a bag holds anything at all without discrimination – including duplicate objects. This is close, but it doesn’t quite fit since a bag has no specification about how elements should be ordered, while a multiset (which requires that all duplicate elements be adjacent to each other) is even more restrictive than the concept of a set, which could use a hashing function to order its elements, in which case they would not be in sorted order. Besides, if you wanted to store a bunch of objects without any special criterions, you’d probably just use a vector, deque or list.

Combining STL containers

When using a thesaurus, you have a word and you want to know all the words that are similar. When you look up a word, then, you want a list of words as the result. Here, the “multi” containers (multimap or multiset) are not appropriate. The solution is to combine containers, which is easily done using the STL. Here, we need a tool that turns out to be a powerful general concept, which is a map of vector:

//: C04:Thesaurus.cpp

Chapter 15: Multiple Inheritance

250

// A map of vectors #include <map> #include <vector> #include <string> #include <iostream> #include <algorithm> #include <ctime> using namespace std;

typedef map<string, vector<string> > Thesaurus; typedef pair<string, vector<string> > TEntry; typedef Thesaurus::iterator TIter;

ostream& operator<<(ostream& os,const TEntry& t){ os << t.first << ": ";

copy(t.second.begin(), t.second.end(), ostream_iterator<string>(os, " "));

return os;

}

// A generator for thesaurus test entries: class ThesaurusGen {

static const string letters; static int count;

public:

int maxSize() { return letters.size(); } ThesaurusGen() { srand(time(0)); } TEntry operator()() {

TEntry result;

if(count >= maxSize()) count = 0; result.first = letters[count++]; int entries = (rand() % 5) + 2; for(int i = 0; i < entries; i++) {

int choice = rand() % maxSize(); char cbuf[2] = { 0 };

cbuf[0] = letters[choice]; result.second.push_back(cbuf);

}

return result;

}

};

int ThesaurusGen::count = 0;

Chapter 15: Multiple Inheritance

251

const string ThesaurusGen::letters("ABCDEFGHIJKL" "MNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz");

int main() {

Thesaurus thesaurus;

//Fill with 10 entries: generate_n(

inserter(thesaurus, thesaurus.begin()), 10, ThesaurusGen());

//Print everything: copy(thesaurus.begin(), thesaurus.end(),

ostream_iterator<TEntry>(cout, "\n"));

//Ask for a "word" to look up: while(true) {

cout << "Select a \"word\", 0 to quit: "; for(TIter it = thesaurus.begin();

it != thesaurus.end(); it++) cout << (*it).first << ' ';

cout << endl; string reply; cin >> reply;

if(reply.at(0) == '0') return 0; // Quit if(thesaurus.find(reply) == thesaurus.end())

continue; // Not in list, try again vector<string>& v = thesaurus[reply]; copy(v.begin(), v.end(),

ostream_iterator<string>(cout, " ")); cout << endl;

}

}///:~

A Thesaurus maps a string (the word) to a vector<string> (the synonyms). A TEntry is a single entry in a Thesaurus. By creating an ostream operator<< for a TEntry, a single entry from the Thesaurus can easily be printed (and the whole Thesaurus can easily be printed with copy( )). The ThesaurusGen creates “words” (which are just single letters) and “synonyms” for those words (which are just other randomly-chosen single letters) to be used as thesaurus entries. It randomly chooses the number of synonym entries to make, but there must be at least two. All the letters are chosen by indexing into a static string that is part of

ThesaurusGen.

In main( ), a Thesaurus is created, filled with 10 entries and printed using the copy( ) algorithm. Then the user is requested to choose a “word” to look up by typing the letter of that word. The find( ) member function is used to find whether the entry exists in the map (remember, you don’t want to use operator[ ] or it will automatically make a new entry if it

Chapter 15: Multiple Inheritance

252

doesn’t find a match!). If so, operator[ ] is used to fetch out the vector<string> which is displayed.

Because templates make the expression of powerful concepts easy, you can take this concept much further, creating a map of vectors containing maps, etc. For that matter, you can combine any of the STL containers this way.

Cleaning up

containers of pointers

In Stlshape.cpp, the pointers did not clean themselves up automatically. It would be convenient to be able to do this easily, rather than writing out the code each time. Here is a function template that will clean up the pointers in any sequence container; note that it is placed in the book’s root directory for easy access:

//: :purge.h

// Delete pointers in an STL sequence container #ifndef PURGE_H

#define PURGE_H #include <algorithm>

template<class Seq> void purge(Seq& c) { typename Seq::iterator i;

for(i = c.begin(); i != c.end(); i++) { delete *i;

*i = 0;

}

}

// Iterator version: template<class InpIt>

void purge(InpIt begin, InpIt end) { while(begin != end) {

delete *begin; *begin = 0; begin++;

}

}

#endif // PURGE_H ///:~

In the first version of purge( ), note that typename is absolutely necessary; indeed this is exactly the case that the keyword was added for: Seq is a template argument, and iterator is

Chapter 15: Multiple Inheritance

253

something that is nested within that template. So what does Seq::iterator refer to? The typename keyword specifies that it refers to a type, and not something else.

While the container version of purge must work with an STL-style container, the iterator version of purge( ) will work with any range, including an array.

Here is Stlshape.cpp, modified to use the purge( ) function:

//: C04:Stlshape2.cpp

// Stlshape.cpp with the purge() function #include "../purge.h"

#include <vector> #include <iostream> using namespace std;

class Shape { public:

virtual void draw() = 0; virtual ~Shape() {};

};

class Circle : public Shape { public:

void draw() { cout << "Circle::draw\n"; } ~Circle() { cout << "~Circle\n"; }

};

class Triangle : public Shape { public:

void draw() { cout << "Triangle::draw\n"; } ~Triangle() { cout << "~Triangle\n"; }

};

class Square : public Shape { public:

void draw() { cout << "Square::draw\n"; } ~Square() { cout << "~Square\n"; }

};

typedef std::vector<Shape*> Container; typedef Container::iterator Iter;

int main() { Container shapes;

shapes.push_back(new Circle);

Chapter 15: Multiple Inheritance

254