- •Thinking in C++ 2nd edition Volume 2: Standard Libraries & Advanced Topics
- •Preface
- •What’s new in the second edition
- •What’s in Volume 2 of this book
- •How to get Volume 2
- •Prerequisites
- •Learning C++
- •Goals
- •Chapters
- •Exercises
- •Exercise solutions
- •Source code
- •Language standards
- •Language support
- •The book’s CD ROM
- •Seminars, CD Roms & consulting
- •Errors
- •Acknowledgements
- •Library overview
- •1: Strings
- •What’s in a string
- •Creating and initializing C++ strings
- •Initialization limitations
- •Operating on strings
- •Appending, inserting and concatenating strings
- •Replacing string characters
- •Concatenation using non-member overloaded operators
- •Searching in strings
- •Finding in reverse
- •Finding first/last of a set
- •Removing characters from strings
- •Stripping HTML tags
- •Comparing strings
- •Using iterators
- •Iterating in reverse
- •Strings and character traits
- •A string application
- •Summary
- •Exercises
- •2: Iostreams
- •Why iostreams?
- •True wrapping
- •Iostreams to the rescue
- •Sneak preview of operator overloading
- •Inserters and extractors
- •Manipulators
- •Common usage
- •Line-oriented input
- •Overloaded versions of get( )
- •Reading raw bytes
- •Error handling
- •File iostreams
- •Open modes
- •Iostream buffering
- •Seeking in iostreams
- •Creating read/write files
- •User-allocated storage
- •Output strstreams
- •Automatic storage allocation
- •Proving movement
- •A better way
- •Output stream formatting
- •Internal formatting data
- •Format fields
- •Width, fill and precision
- •An exhaustive example
- •Formatting manipulators
- •Manipulators with arguments
- •Creating manipulators
- •Effectors
- •Iostream examples
- •Code generation
- •Maintaining class library source
- •Detecting compiler errors
- •A simple datalogger
- •Generating test data
- •Verifying & viewing the data
- •Counting editor
- •Breaking up big files
- •Summary
- •Exercises
- •3: Templates in depth
- •Nontype template arguments
- •Typedefing a typename
- •Using typename instead of class
- •Function templates
- •A string conversion system
- •A memory allocation system
- •Type induction in function templates
- •Taking the address of a generated function template
- •Local classes in templates
- •Applying a function to an STL sequence
- •Template-templates
- •Member function templates
- •Why virtual member template functions are disallowed
- •Nested template classes
- •Template specializations
- •A practical example
- •Pointer specialization
- •Partial ordering of function templates
- •Design & efficiency
- •Preventing template bloat
- •Explicit instantiation
- •Explicit specification of template functions
- •Controlling template instantiation
- •Template programming idioms
- •Summary
- •Containers and iterators
- •STL reference documentation
- •The Standard Template Library
- •The basic concepts
- •Containers of strings
- •Inheriting from STL containers
- •A plethora of iterators
- •Iterators in reversible containers
- •Iterator categories
- •Input: read-only, one pass
- •Output: write-only, one pass
- •Forward: multiple read/write
- •Bidirectional: operator--
- •Random-access: like a pointer
- •Is this really important?
- •Predefined iterators
- •IO stream iterators
- •Manipulating raw storage
- •Basic sequences: vector, list & deque
- •Basic sequence operations
- •vector
- •Cost of overflowing allocated storage
- •Inserting and erasing elements
- •deque
- •Converting between sequences
- •Cost of overflowing allocated storage
- •Checked random-access
- •list
- •Special list operations
- •list vs. set
- •Swapping all basic sequences
- •Robustness of lists
- •Performance comparison
- •A completely reusable tokenizer
- •stack
- •queue
- •Priority queues
- •Holding bits
- •bitset<n>
- •vector<bool>
- •Associative containers
- •Generators and fillers for associative containers
- •The magic of maps
- •A command-line argument tool
- •Multimaps and duplicate keys
- •Multisets
- •Combining STL containers
- •Creating your own containers
- •Summary
- •Exercises
- •5: STL Algorithms
- •Function objects
- •Classification of function objects
- •Automatic creation of function objects
- •Binders
- •Function pointer adapters
- •SGI extensions
- •A catalog of STL algorithms
- •Support tools for example creation
- •Filling & generating
- •Example
- •Counting
- •Example
- •Manipulating sequences
- •Example
- •Searching & replacing
- •Example
- •Comparing ranges
- •Example
- •Removing elements
- •Example
- •Sorting and operations on sorted ranges
- •Sorting
- •Example
- •Locating elements in sorted ranges
- •Example
- •Merging sorted ranges
- •Example
- •Set operations on sorted ranges
- •Example
- •Heap operations
- •Applying an operation to each element in a range
- •Examples
- •Numeric algorithms
- •Example
- •General utilities
- •Creating your own STL-style algorithms
- •Summary
- •Exercises
- •Perspective
- •Duplicate subobjects
- •Ambiguous upcasting
- •virtual base classes
- •The "most derived" class and virtual base initialization
- •"Tying off" virtual bases with a default constructor
- •Overhead
- •Upcasting
- •Persistence
- •MI-based persistence
- •Improved persistence
- •Avoiding MI
- •Mixin types
- •Repairing an interface
- •Summary
- •Exercises
- •7: Exception handling
- •Error handling in C
- •Throwing an exception
- •Catching an exception
- •The try block
- •Exception handlers
- •Termination vs. resumption
- •The exception specification
- •Better exception specifications?
- •Catching any exception
- •Rethrowing an exception
- •Uncaught exceptions
- •Function-level try blocks
- •Cleaning up
- •Constructors
- •Making everything an object
- •Exception matching
- •Standard exceptions
- •Programming with exceptions
- •When to avoid exceptions
- •Not for asynchronous events
- •Not for ordinary error conditions
- •Not for flow-of-control
- •You’re not forced to use exceptions
- •New exceptions, old code
- •Typical uses of exceptions
- •Always use exception specifications
- •Start with standard exceptions
- •Nest your own exceptions
- •Use exception hierarchies
- •Multiple inheritance
- •Catch by reference, not by value
- •Throw exceptions in constructors
- •Don’t cause exceptions in destructors
- •Avoid naked pointers
- •Overhead
- •Summary
- •Exercises
- •8: Run-time type identification
- •The “Shape” example
- •What is RTTI?
- •Two syntaxes for RTTI
- •Syntax specifics
- •Producing the proper type name
- •Nonpolymorphic types
- •Casting to intermediate levels
- •void pointers
- •Using RTTI with templates
- •References
- •Exceptions
- •Multiple inheritance
- •Sensible uses for RTTI
- •Revisiting the trash recycler
- •Mechanism & overhead of RTTI
- •Creating your own RTTI
- •Explicit cast syntax
- •Summary
- •Exercises
- •9: Building stable systems
- •Shared objects & reference counting
- •Reference-counted class hierarchies
- •Finding memory leaks
- •An extended canonical form
- •Exercises
- •10: Design patterns
- •The pattern concept
- •The singleton
- •Variations on singleton
- •Classifying patterns
- •Features, idioms, patterns
- •Basic complexity hiding
- •Factories: encapsulating object creation
- •Polymorphic factories
- •Abstract factories
- •Virtual constructors
- •Destructor operation
- •Callbacks
- •Observer
- •The “interface” idiom
- •The “inner class” idiom
- •The observer example
- •Multiple dispatching
- •Visitor, a type of multiple dispatching
- •Efficiency
- •Flyweight
- •The composite
- •Evolving a design: the trash recycler
- •Improving the design
- •“Make more objects”
- •A pattern for prototyping creation
- •Trash subclasses
- •Parsing Trash from an external file
- •Recycling with prototyping
- •Abstracting usage
- •Applying double dispatching
- •Implementing the double dispatch
- •Applying the visitor pattern
- •More coupling?
- •RTTI considered harmful?
- •Summary
- •Exercises
- •11: Tools & topics
- •The code extractor
- •Debugging
- •Trace macros
- •Trace file
- •Abstract base class for debugging
- •Tracking new/delete & malloc/free
- •CGI programming in C++
- •Encoding data for CGI
- •The CGI parser
- •Testing the CGI parser
- •Using POST
- •Handling mailing lists
- •Maintaining your list
- •Mailing to your list
- •A general information-extraction CGI program
- •Parsing the data files
- •Summary
- •Exercises
- •General C++
- •My own list of books
- •Depth & dark corners
- •Design Patterns
- •Index
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 system. After running each teller, the display is repeated. At this point, the system adapts by comparing the number of customers and the number of tellers; if the line is too long another teller is added and if it is short enough a teller can be removed. It is in this adaptation section of the program that you can experiment with policies regarding the optimal addition and removal of tellers. If this is the only section that you’re modifying, you may want to encapsulate policies inside of different objects.
Priority queues
When you push( ) an object onto a priority_queue, that object is sorted into the queue according to a function or function object (you can allow the default less template to supply this, or provide one of your own). The priority_queue ensures that when you look at the top( ) element it will be the one with the highest priority. When you’re done with it, you call pop( ) to remove it and bring the next one into place. Thus, the priority_queue has nearly the same interface as a stack, but it behaves differently.
Like stack and 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 ints:
//: 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
216
} ///:~
This pushes into the priority_queue 100 random values from 0 to 24. When you run this program you’ll see that duplicates are allowed, and the highest values appear first. To show how you can change the ordering by providing your own function or function object, the following program gives lower-valued numbers the highest priority:
//: C04:PriorityQueue2.cpp // Changing the priority #include <iostream> #include <queue>
#include <cstdlib> #include <ctime> using namespace std;
struct Reverse {
bool operator()(int x, int y) { return y < x;
}
};
int main() {
priority_queue<int, vector<int>, Reverse> pqi;
//Could also say:
//priority_queue<int, vector<int>,
//greater<int> > pqi; srand(time(0));
for(int i = 0; i < 100; i++) 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>, redefine operator( ) and hand an object of that type to the priority_queue
Chapter 15: Multiple Inheritance
217
constructor. I tried this, and got it to compile, but the resulting program produced the same old less<int> behavior. The answer lies in the less< > template:
template <class T>
struct less : binary_function<T, T, bool> { // Other stuff...
bool operator()(const T& x, const T& y) const { return x < y;
}
};
The operator( ) is not virtual, so even though the constructor takes your subclass of less<int> by reference (thus it doesn’t slice it down to a plain less<int>), when 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)
return true; if(x.primary == y.primary)
if(x.secondary > y.secondary) return true;
return false;
}
friend ostream&
operator<<(ostream& os, const ToDoItem& td) {
Chapter 15: Multiple Inheritance
218
return os << td.primary << td.secondary << ": " << td.item;
}
};
int main() { priority_queue<ToDoItem> toDoList;
toDoList.push(ToDoItem("Empty trash", 'C', 4)); toDoList.push(ToDoItem("Feed dog", 'A', 2)); toDoList.push(ToDoItem("Feed bird", 'B', 7)); toDoList.push(ToDoItem("Mow lawn", 'C', 3)); toDoList.push(ToDoItem("Water lawn", 'A', 1)); toDoList.push(ToDoItem("Feed cat", 'B', 1)); while(!toDoList.empty()) {
cout << toDoList.top() << endl; toDoList.pop();
}
} ///:~
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( ) and pop_heap( ) (they are the soul of the priority_queue; in fact you could say that the heap is the priority queue and priority_queue is just a wrapper around it). This turns out to be reasonably straightforward, but you might think that a shortcut is possible. Since the container used by priority_queue is protected (and has the identifier, according to the Standard C++ specification, named c) you can inherit a new class which provides access to the underlying implementation:
//: C04:PriorityQueue4.cpp
// Manipulating the underlying implementation #include <iostream>
#include <queue> #include <cstdlib> #include <ctime>
Chapter 15: Multiple Inheritance
219
using namespace std;
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:
//: C04:PriorityQueue5.cpp
// Building your own priority queue #include <iostream>
#include <queue> #include <cstdlib> #include <ctime> using namespace std;
template<class T, class Compare> class PQV : public vector<T> {
Compare comp; public:
PQV(Compare cmp = Compare()) : comp(cmp) { make_heap(begin(), end(), comp);
}
const T& top() { return front(); } void push(const T& x) {
push_back(x);
Chapter 15: Multiple Inheritance
220
push_heap(begin(), end(), comp);
}
void pop() {
pop_heap(begin(), end(), comp); pop_back();
}
};
int main() {
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( ) first. This can be encapsulated into your custom priority queue:
//: C04:PriorityQueue6.cpp #include <iostream> #include <queue>
#include <algorithm> #include <cstdlib> #include <ctime> using namespace std;
template<class T, class Compare> class PQV : public vector<T> {
Compare comp; bool sorted;
void assureHeap() { if(sorted) {
Chapter 15: Multiple Inheritance
221
// Turn it back into a heap: make_heap(begin(), end(), comp); sorted = false;
}
}
public:
PQV(Compare cmp = Compare()) : comp(cmp) { make_heap(begin(), end(), comp);
sorted = false;
}
const T& top() { 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++) { pqi.push(rand() % 25); copy(pqi.begin(), pqi.end(),
Chapter 15: Multiple Inheritance
222
ostream_iterator<int>(cout, " ")); cout << "\n-----\n";
}
pqi.sort(); copy(pqi.begin(), pqi.end(),
ostream_iterator<int>(cout, " ")); cout << "\n-----\n"; while(!pqi.empty()) {
cout << pqi.top() << ' '; pqi.pop();
}
} ///:~
If sorted is true, then the vector is not organized as a heap, but instead as a sorted sequence. assureHeap( ) guarantees that it’s put back into heap form before performing any heap operations on it.
The first for loop in main( ) 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: v.push_back(x);
//Re-adjust the heap:
Chapter 15: Multiple Inheritance
223
push_heap(v.begin(), v.end(), comp);
}
void pop() {
//Move the top element to the last position: pop_heap(v.begin(), v.end(), comp);
//Remove that element:
v.pop_back();
}
const T& top() { return v.front(); } bool empty() const { return v.empty(); } int size() const { return v.size(); } typedef vector<T> TVec;
TVec vector() {
TVec r(v.begin(), v.end()); // It’s already a heap
sort_heap(r.begin(), r.end(), comp); // Put it into priority-queue order: reverse(r.begin(), r.end());
return r;
}
};
int main() {
PQV<int, less<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();
}
} ///:~
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 priority queue.
Chapter 15: Multiple Inheritance
224
You may observe that the approach of inheriting from priority_queue used in PriorityQueue4.cpp could be used with the above technique to produce more succinct code:
//: C04:PriorityQueue8.cpp
// A more compact version of PriorityQueue7.cpp #include <iostream>
#include <queue> #include <algorithm> #include <cstdlib> #include <ctime> using namespace std;
template<class T>
class PQV : public priority_queue<T> { public:
typedef vector<T> TVec; TVec vector() {
TVec r(c.begin(), c.end()); // c is already a heap
sort_heap(r.begin(), r.end(), comp); // Put it into priority-queue order: reverse(r.begin(), r.end());
return r;
}
};
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
Chapter 15: Multiple Inheritance
225