- •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
// Test StreamTokenizer #include "StreamTokenizer.h" #include "../require.h" #include <iostream>
#include <fstream> #include <set>
using namespace std;
int main(int argc, char* argv[]) { requireArgs(argc, 1);
ifstream in(argv[1]); assure(in, argv[1]); StreamTokenizer words(in); set<string> wordlist; string word;
while((word = words.next()).size() != 0) wordlist.insert(word);
// 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
The TokenIterator is doubly flexible: first, you can choose the type of iterator that will produce the char input. Second, instead of just saying what characters represent the delimiters, TokenIterator will use a predicate which is a function object whose operator( ) takes a char and decides if it should be in the token or not. Although the two examples given
18 This is another example coached by Nathan Myers.
Chapter 15: Multiple Inheritance
203
here have a static concept of what characters belong in a token, you could easily design your own function object to change its state as the characters are read, producing a more sophisticated parser.
The following header file contains the two basic predicates Isalpha and Delimiters, along with the template for 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<
std::input_iterator_tag,std::string,ptrdiff_t>{ InputIter first;
InputIter last; std::string word; Pred predicate;
public:
TokenIterator(InputIter begin, InputIter end, Pred pred = Pred())
: first(begin), last(end), predicate(pred) {
Chapter 15: Multiple Inheritance
204
++*this;
}
TokenIterator() {} // End sentinel
//Prefix increment: TokenIterator& operator++() {
word.resize(0);
first = std::find_if(first, last, predicate); while (first != last && predicate(*first))
word += *first++; return *this;
}
//Postfix increment
class Proxy { std::string word;
public:
Proxy(const std::string& w) : word(w) {} std::string operator*() { return word; }
};
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 TokenIterator only has the capabilities of an input iterator, and cannot be used with algorithms requiring
Chapter 15: Multiple Inheritance
205
more sophisticated iterators. Apart from the tagging, std::iterator doesn’t do anything else, which means you must design all the other functionality in yourself.
TokenIterator may look a little strange at first, because the first constructor requires both a “begin” and “end” iterator as arguments, along with the predicate. Remember that this is a “wrapper” iterator that has no idea of how to tell whether it’s at the end of its input source, so the ending iterator is necessary in the first constructor. The reason for the second (default) constructor is that the STL algorithms (and any algorithms you write) need a TokenIterator sentinel to be the past-the-end value. Since all the information necessary to see if the TokenIterator has reached the end of its input is collected in the first constructor, this second constructor creates a TokenIterator that is merely used as a placeholder in algorithms.
The core of the behavior happens in operator++. This erases the current value of word using string::resize( ), then finds the first character that satisfies the predicate (thus discovering the 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!= is defined in terms of operator==.
A good test of TokenIterator includes a number of different sources of input characters including a streambuf_iterator, a char*, and a deque<char>::iterator. Finally, the original
Wordlist.cpp problem is solved:
//: C04:TokenIteratorTest.cpp #include "TokenIterator.h" #include "../require.h" #include <fstream>
#include <iostream> #include <vector> #include <deque> #include <set>
using namespace std;
int main() {
ifstream in("TokenIteratorTest.cpp"); assure(in, "TokenIteratorTest.cpp"); ostream_iterator<string> out(cout, "\n"); typedef istreambuf_iterator<char> IsbIt;
Chapter 15: Multiple Inheritance
206
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>
dcIter(dc.begin(), dc.end(), delimiters), end3;
vector<string> wordlist3;
copy(dcIter, end3, back_inserter(wordlist3)); copy(wordlist3.begin(), wordlist3.end(), out); *out++ = "-----------------------------------"; // Reproduce the Wordlist.cpp example:
ifstream in3("TokenIteratorTest.cpp"); TokenIterator<IsbIt, Delimiters>
wordIter2(IsbIt(in3), isbEnd, delimiters); set<string> wordlist4;
while(wordIter2 != end) wordlist4.insert(*wordIter2++);
copy(wordlist4.begin(), wordlist4.end(), out); } ///:~
Chapter 15: Multiple Inheritance
207