Chapter 15: Multiple Inheritance
201
ostream_iterator<string>(cout, "\n"));
} ///:~

This example was suggested by Nathan Myers, who invented the
istreambuf_iterator
and its
relatives. This iterator extracts information character-by-character from a stream. Although
the
istreambuf_iterator
template argument might suggest to you that you could extract, for
example,
int
s instead of
char
, that’s not the case. The argument must be of some character
type – a regular
char
or a wide character.
After the file is open, an
istreambuf_iterator
called
p
is attached to the
istream
so characters
can be extracted from it. The
set<string>
called

have a
push_back( )
(
string
does).
After the
while
loop sets everything up, it begins by looking for the first alpha character,
incrementing
start
until that character is found. Then it copies characters from one iterator to
the other, stopping when a non-alpha character is found. Each
word
, assuming it is non-
empty, is added to
wordlist
.
StreamTokenizer
:
a more flexible solution
The above program parses its input into strings of words containing only alpha characters, but
that’s still a special case compared to the generality of
strtok( )
. What we’d like now is an
actual replacement for
strtok( )
so we’re never tempted to use it.
WordList2.cpp
can be
modified to create a class called

StreamTokenizer(std::istream& is,
std::string delim = " \t\n;()\"<>:{}[]+-=&*#"
".,/\\~!0123456789") : p(is), end(It()),
delimiters(delim) {}
std::string next(); // Get next token
};
#endif STREAMTOKENIZER_H ///:~

The default delimiters for the
StreamTokenizer
constructor extract words with only alpha
characters, as before, but now you can choose different delimiters to parse different tokens.
The implementation of
next( )
looks similar to
Wordlist2.cpp
:
//: C04:StreamTokenizer.cpp {O}
#include "StreamTokenizer.h"
using namespace std;

string StreamTokenizer::next() {
string result;
if(p != end) {
insert_iterator<string>
ii(result, result.begin());
while(isDelimiter(*p) && p != end)
p++;
while (!isDelimiter(*p) && p != end)
*ii++ = *p++;

// Output results:
copy(wordlist.begin(), wordlist.end(),
ostream_iterator<string>(cout, "\n"));
} ///:~

Now the tool is more reusable than before, but it’s still inflexible, because it can only work
with an
istream
. This isn’t as bad as it first seems, since a
string
can be turned into an
istream
via an
istringstream
. But in the next section we’ll come up with the most general,
reusable tokenizing tool, and this should give you a feeling of what “reusable” really means,
and the effort necessary to create truly reusable code.
A completely reusable tokenizer
Since the STL containers and algorithms all revolve around iterators, the most flexible
solution will itself be an iterator. You could think of the
TokenIterator
as an iterator that
wraps itself around any other iterator that can produce characters. Because it is designed as an
input iterator (the most primitive type of iterator) it can be used with any STL algorithm. Not
only is it a useful tool in itself, the
TokenIterator
is also a good example of how you can
design your own iterators.
18


TokenIterator
:
//: C04:TokenIterator.h
#ifndef TOKENITERATOR_H
#define TOKENITERATOR_H
#include <string>
#include <iterator>
#include <algorithm>
#include <cctype>

struct Isalpha {
bool operator()(char c) {
using namespace std; //[[For a compiler bug]]
return isalpha(c);
}
};

class Delimiters {
std::string exclude;
public:
Delimiters() {}
Delimiters(const std::string& excl)
: exclude(excl) {}
bool operator()(char c) {
return exclude.find(c) == std::string::npos;
}
};

template <class InputIter, class Pred = Isalpha>
class TokenIterator: public std::iterator<

Proxy operator++(int) {
Proxy d(word);
++*this;
return d;
}
// Produce the actual value:
std::string operator*() const { return word; }
std::string* operator->() const {
return &(operator*());
}
// Compare iterators:
bool operator==(const TokenIterator&) {
return word.size() == 0 && first == last;
}
bool operator!=(const TokenIterator& rv) {
return !(*this == rv);
}
};
#endif // TOKENITERATOR_H ///:~

TokenIterator
is inherited from the
std::iterator
template. It might appear that there’s some
kind of functionality that comes with
std::iterator
, but it is purely a way of tagging an
iterator so that a container that uses it knows what it’s capable of. Here, you can see
input_iterator_tag
as a template argument – this tells anyone who asks that a

beginning of the new token) using
find_if( )
(from the STL algorithms, discussed in the
following chapter). The resulting iterator is assigned to
first
, thus moving
first
forward to the
beginning of the token. Then, as long as the end of the input is not reached and the predicate
is satisfied, characters are copied into the word from the input. Finally, the TokenIterator
object is returned, and must be dereferenced to access the new token.
The postfix increment requires a proxy object to hold the value before the increment, so it can
be returned (see the operator overloading chapter for more details of this). Producing the
actual value is a straightforward
operator*
. The only other functions that must be defined for
an output iterator are the
operator==
and
operator!=
to indicate whether the
TokenIterator

has reached the end of its input. You can see that the argument for
operator==
is ignored – it
only cares about whether it has reached its internal
last
iterator. Notice that
operator!=

typedef istreambuf_iterator<char> IsbIt;

Chapter 15: Multiple Inheritance
207
IsbIt begin(in), isbEnd;
Delimiters
delimiters(" \t\n~;()\"<>:{}[]+-=&*#.,/\\");
TokenIterator<IsbIt, Delimiters>
wordIter(begin, isbEnd, delimiters),
end;
vector<string> wordlist;
copy(wordIter, end, back_inserter(wordlist));
// Output results:
copy(wordlist.begin(), wordlist.end(), out);
*out++ = " ";
// Use a char array as the source:
char* cp =
"typedef std::istreambuf_iterator<char> It";
TokenIterator<char*, Delimiters>
charIter(cp, cp + strlen(cp), delimiters),
end2;
vector<string> wordlist2;
copy(charIter, end2, back_inserter(wordlist2));
copy(wordlist2.begin(), wordlist2.end(), out);
*out++ = " ";
// Use a deque<char> as the source:
ifstream in2("TokenIteratorTest.cpp");
deque<char> dc;
copy(IsbIt(in2), IsbIt(), back_inserter(dc));
TokenIterator<deque<char>::iterator,Delimiters>

TokenIterator
produces
string
s that are inserted into a container
which must, naturally, be a container of
string
– here a
vector<string>
is used in all cases
except the last (you could also concatenate the results onto a
string
). Other than that, a
TokenIterator
works like any other input iterator.
stack
The
stack
, along with the
queue
and
priority_queue
, are classified as
adapters
, which means
they are implemented using one of the basic sequence containers:
vector
,
list
or
deque

using namespace std;

// Default: deque<string>:
typedef stack<string> Stack1;
// Use a vector<string>:
typedef stack<string, vector<string> > Stack2;
// Use a list<string>:
typedef stack<string, list<string> > Stack3;

Chapter 15: Multiple Inheritance
209

int main(int argc, char* argv[]) {
requireArgs(argc, 1); // File name is argument
ifstream in(argv[1]);
assure(in, argv[1]);
Stack1 textlines; // Try the different versions
// Read file and store lines in the stack:
string line;
while(getline(in, line))
textlines.push(line + "\n");
// Print lines from the stack and pop them:
while(!textlines.empty()) {
cout << textlines.top();
textlines.pop();
}
} ///:~

The
top( )

can use the underlying container that the
stack
is implemented upon. For example, suppose
you have a function that expects a
stack
interface but in the rest of your program you need the
objects stored in a
list
. The following program stores each line of a file along with the leading
number of spaces in that line (you might imagine it as a starting point for performing some
kinds of source-code reformatting):
//: C04:Stack2.cpp
// Converting a list to a stack
#include " /require.h"
#include <iostream>
#include <fstream>
#include <stack>
#include <list>
#include <string>
using namespace std;

// Expects a stack:

Chapter 15: Multiple Inheritance
210
template<class Stk>
void stackOut(Stk& s, ostream& os = cout) {
while(!s.empty()) {
os << s.top() << "\n";
s.pop();

lines.push_front(s);
// Turn the list into a stack for printing:
stack<Line, list<Line> > stk(lines);
stackOut(stk);
} ///:~

The function that requires the
stack
interface just sends each
top( )
object to an
ostream
and
then removes it by calling
pop( )
. The
Line
class determines the number of leading spaces,
then stores the contents of the line
without
the leading spaces. The
ostream

operator<<
re-

Chapter 15: Multiple Inheritance
211
inserts the leading spaces so the line prints properly, but you can easily change the number of
spaces by changing the value of

.
Stack1.cpp
can be rewritten to show this:
//: C04:Stack3.cpp
// Using a vector as a stack; modified Stack1.cpp
#include " /require.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;

int main(int argc, char* argv[]) {
requireArgs(argc, 1);
ifstream in(argv[1]);
assure(in, argv[1]);
vector<string> textlines;
string line;
while(getline(in, line))
textlines.push_back(line + "\n");
while(!textlines.empty()) {
cout << textlines.back();
textlines.pop_back();
}
} ///:~

You’ll see this produces the same output as
Stack1.cpp
, but you can now perform
vector

212
to use a
queue
rather than a
deque
, then, is if you want to emphasize that you will only be
performing queue-like behavior.
The
queue
is an adapter class like
stack
, in that it is built on top of another sequence
container. As you might guess, the ideal implementation for a
queue
is a
deque
, and that is
the default template argument for the
queue
; you’ll rarely need a different implementation.
Queues are often used when modeling systems where some elements of the system are
waiting to be served by other elements in the system. A classic example of this is the “bank-
teller problem,” where you have customers arriving at random intervals, getting into a line,
and then being served by a set of tellers. Since the customers arrive randomly and each take a
random amount of time to be served, there’s no way to deterministically know how long the
line will be at any time. However, it’s possible to simulate the situation and see what happens.
A problem in performing this simulation is the fact that, in effect, each customer and teller
should be run by a separate process. What we’d like is a multithreaded environment, then
each customer or teller would have their own thread. However, Standard C++ has no model
for multithreading so there is no standard solution to this problem. On the other hand, with a

simulation:
//: C04:BankTeller.cpp
// Using a queue and simulated multithreading
// To model a bank teller system
#include <iostream>
#include <queue>

Chapter 15: Multiple Inheritance
213
#include <list>
#include <cstdlib>
#include <ctime>
using namespace std;

class Customer {
int serviceTime;
public:
Customer() : serviceTime(0) {}
Customer(int tm) : serviceTime(tm) {}
int getTime() { return serviceTime; }
void setTime(int newtime) {
serviceTime = newtime;
}
friend ostream&
operator<<(ostream& os, const Customer& c) {
return os << '[' << c.serviceTime << ']';
}
};

class Teller {

ttime -= servtime;
if(!customers.empty()) {
current = customers.front();
customers.pop(); // Remove it
busy = true;
run(true); // Recurse
}
return;
}
if(servtime == ttime) {
// Done with current, set to empty:
current = Customer(0);
busy = false;
return; // No more time in this slice
}
}
};

// Inherit to access protected implementation:
class CustomerQ : public queue<Customer> {
public:
friend ostream&
operator<<(ostream& os, const CustomerQ& cd) {
copy(cd.c.begin(), cd.c.end(),
ostream_iterator<Customer>(os, ""));
return os;
}
};

int main() {

tellers.erase(i);
break; // Out of for loop
}
}
} ///:~

Each customer requires a certain amount of service time, which is the number of time units
that a teller must spend on the customer in order to serve that customer’s needs. Of course, the
amount of service time will be different for each customer, and will be determined randomly.
In addition, you won’t know how many customers will be arriving in each interval, so this
will also be determined randomly.
The
Customer
objects are kept in a
queue<Customer>
, and each
Teller
object keeps a
reference to that queue.

When a
Teller
object is finished with its current
Customer
object,
that
Teller
will get another
Customer
from the queue and begin working on the new

queue
is built upon) is held as a
protected
member inside the
queue
, and the identifier for

Chapter 15: Multiple Inheritance
216
this member is specified in the C++ Standard as ‘
c
’, which means that you can inherit from
queue
in order to access the underlying implementation. The
CustomerQ
class does exactly
that, for the sole purpose of defining an
ostream

operator<<
that can iterate through the
queue
and print out its members.
The driver for the simulation is the infinite
while
loop in
main( )
. At the beginning of each
pass through the loop, a random number of customers are added, with random service times.
Both the number of tellers and the queue contents are displayed so you can see the state of the

queue
,
priority_queue
is an adapter which is built on top of one of the basic
sequences – the default is
vector
.
It’s trivial to make a
priority_queue
that works with
int
s:
//: C04:PriorityQueue1.cpp
#include <iostream>
#include <queue>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
priority_queue<int> pqi;
srand(time(0)); // Seed random number generator
for(int i = 0; i < 100; i++)
pqi.push(rand() % 25);
while(!pqi.empty()) {
cout << pqi.top() << ' ';
pqi.pop();
}

Chapter 15: Multiple Inheritance

pqi.push(rand() % 25);
while(!pqi.empty()) {
cout << pqi.top() << ' ';
pqi.pop();
}
} ///:~

Although you can easily use the Standard Library
greater
template to produce the predicate, I
went to the trouble of creating
Reverse
so you could see how to do it in case you have a more
complex scheme for ordering your objects.
If you look at the description for
priority_queue
, you see that the constructor can be handed a
“Compare” object, as shown above. If you don’t use your own “Compare” object, the default
template behavior is the
less
template function. You might think (as I did) that it would make
sense to leave the template instantiation as
priority_queue<int>
, thus using the default
template arguments of
vector<int>
and
less<int>
. Then you could inherit a new class from
less<int>

operator( )
is
called, it is the base-class version that is used. While it is generally reasonable to expect
ordinary classes to behave polymorphically, you cannot make this assumption when using the
STL.
Of course, a
priority_queue
of
int
is trivial. A more interesting problem is a to-do list, where
each object contains a
string
and a primary and secondary priority value:
//: C04:PriorityQueue3.cpp
// A more complex use of priority_queue
#include <iostream>
#include <queue>
#include <string>
using namespace std;

class ToDoItem {
char primary;
int secondary;
string item;
public:
ToDoItem(string td, char pri ='A', int sec =1)
: item(td), primary(pri), secondary(sec) {}
friend bool operator<(
const ToDoItem& x, const ToDoItem& y) {
if(x.primary > y.primary)

ToDoItem
’s
operator<
must be a non-member function for it to work with
less< >
. Other
than that, everything happens automatically. The output is:
A1: Water lawn
A2: Feed dog
B1: Feed cat
B7: Feed bird
C3: Mow lawn
C4: Empty trash

Note that you cannot iterate through a
priority_queue
. However, it is possible to emulate the
behavior of a
priority_queue
using a
vector
, thus allowing you access to that
vector
. You
can do this by looking at the implementation of
priority_queue
, which uses
make_heap( )
,
push_heap( )


class PQI : public priority_queue<int> {
public:
vector<int>& impl() { return c; }
};

int main() {
PQI pqi;
srand(time(0));
for(int i = 0; i < 100; i++)
pqi.push(rand() % 25);
copy(pqi.impl().begin(), pqi.impl().end(),
ostream_iterator<int>(cout, " "));
cout << endl;
while(!pqi.empty()) {
cout << pqi.top() << ' ';
pqi.pop();
}
} ///:~

However, if you run this program you’ll discover that the
vector
doesn’t contain the items in
the descending order that you get when you call
pop( )
, the order that you want from the
priority queue. It would seem that if you want to create a
vector
that is a priority queue, you
have to do it by hand, like this:

PQV<int, less<int> > pqi;
srand(time(0));
for(int i = 0; i < 100; i++)
pqi.push(rand() % 25);
copy(pqi.begin(), pqi.end(),
ostream_iterator<int>(cout, " "));
cout << endl;
while(!pqi.empty()) {
cout << pqi.top() << ' ';
pqi.pop();
}
} ///:~

But this program behaves in the same way as the previous one! What you are seeing in the
underlying
vector
is called a
heap
.

This heap represents the tree of the priority queue (stored
in the linear structure of the
vector
), but when you iterate through it you do not get a linear
priority-queue order. You might think that you can simply call
sort_heap( )
, but that only
works once, and then you don’t have a heap anymore, but instead a sorted list. This means
that to go back to using it as a heap the user must remember to call
make_heap( )

assureHeap();
return front();
}
void push(const T& x) {
assureHeap();
// Put it at the end:
push_back(x);
// Re-adjust the heap:
push_heap(begin(), end(), comp);
}
void pop() {
assureHeap();
// Move the top element to the last position:
pop_heap(begin(), end(), comp);
// Remove that element:
pop_back();
}
void sort() {
if(!sorted) {
sort_heap(begin(), end(), comp);
reverse(begin(), end());
sorted = true;
}
}
};

int main() {
PQV<int, less<int> > pqi;
srand(time(0));
for(int i = 0; i < 100; i++) {

now has the additional quality that it displays the heap as it’s
being built.
The only drawback to this solution is that the user must remember to call
sort( )
before
viewing it as a sorted sequence (although one could conceivably override all the methods that
produce iterators so that they guarantee sorting). Another solution is to build a priority queue
that is not a
vector
, but will build you a
vector
whenever you want one:
//: C04:PriorityQueue7.cpp
// A priority queue that will hand you a vector
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;

template<class T, class Compare>
class PQV {
vector<T> v;
Compare comp;
public:
// Don't need to call make_heap(); it's empty:
PQV(Compare cmp = Compare()) : comp(cmp) {}
void push(const T& x) {
// Put it at the end:

for(int i = 0; i < 100; i++)
pqi.push(rand() % 25);
const vector<int>& v = pqi.vector();
copy(v.begin(), v.end(),
ostream_iterator<int>(cout, " "));
cout << "\n \n";
while(!pqi.empty()) {
cout << pqi.top() << ' ';
pqi.pop();
}
} ///:~

PQV
follows the same form as the STL’s
priority_queue
, but has the additional member
vector( )
, which creates a new
vector
that’s a copy of the one in
PQV
(which means that it’s
already a heap), then sorts it (thus it leave’s
PQV
’s
vector
untouched), then reverses the order
so that traversing the new
vector
produces the same effect as popping the elements from the

};

int main() {
PQV<int> pqi;
srand(time(0));
for(int i = 0; i < 100; i++)
pqi.push(rand() % 25);
const vector<int>& v = pqi.vector();
copy(v.begin(), v.end(),
ostream_iterator<int>(cout, " "));
cout << "\n \n";
while(!pqi.empty()) {
cout << pqi.top() << ' ';
pqi.pop();
}
} ///:~

The brevity of this solution makes it the simplest and most desirable, plus it’s guaranteed that
the user will not have a
vector
in the unsorted state. The only potential problem is that the