- •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
LSI blank(LSI begin, LSI end) { return find_if(begin, end,
mem_fun_ref(&string::empty));
}
int main(int argc, char* argv[]) { requireArgs(argc, 1);
ifstream in(argv[1]); assure(in, argv[1]); list<string> ls; string s; while(getline(in, s))
ls.push_back(s);
LSI lsi = blank(ls.begin(), ls.end()); while(lsi != ls.end()) {
*lsi = "A BLANK LINE";
lsi = blank(lsi, ls.end());
}
string f(argv[1]); f += ".out";
ofstream out(f.c_str()); copy(ls.begin(), ls.end(),
ostream_iterator<string>(out, "\n")); } ///:~
The blank( ) function uses find_if( ) to locate the first blank line in the given range using mem_fun_ref( ) with string::empty( ). After the file is opened and read into the list, blank( ) is called repeated times to find every blank line in the file. Notice that subsequent calls to blank( ) use the current version of the iterator so it moves forward to the next one. Each time a blank line is found, it is replaced with the characters “A BLANK LINE.” All you have to do to accomplish this is dereference the iterator, and you select the current string.
SGI extensions
The SGI STL (mentioned at the end of the previous chapter) also includes additional function object templates, which allow you to write expressions that create even more complicated function objects. Consider a more involved program which converts strings of digits into floating point numbers, like PtrFun2.cpp but more general. First, here’s a generator that creates strings of integers that represent floating-point values (including an embedded decimal point):
//: C05:NumStringGen.h
//A random number generator that produces
//strings representing floating-point numbers
Chapter 15: Multiple Inheritance
279
#ifndef NUMSTRINGGEN_H #define NUMSTRINGGEN_H #include <string> #include <cstdlib> #include <ctime>
class NumStringGen {
const int sz; // Number of digits to make public:
NumStringGen(int ssz = 5) : sz(ssz) { std::srand(std::time(0));
}
std::string operator()() {
static char n[] = "0123456789"; const int nsz = 10;
std::string r(sz, ' '); for(int i = 0; i < sz; i++)
if(i == sz/2)
r[i] = '.'; // Insert a decimal point else
r[i] = n[std::rand() % nsz]; return r;
}
};
#endif // NUMSTRINGGEN_H ///:~
You tell it how big the strings should be when you create the NumStringGen object. The random number generator is used to select digits, and a decimal point is placed in the middle.
The following program (which works with the Standard C++ STL without the SGI extensions) uses NumStringGen to fill a vector<string>. However, to use the Standard C library function atof( ) to convert the strings to floating-point numbers, the string objects must first be turned into char pointers, since there is no automatic type conversion from string to char*. The transform( ) algorithm can be used with mem_fun_ref( ) and string::c_str( ) to convert all the strings to char*, and then these can be transformed using atof:
//: C05:MemFun3.cpp // Using mem_fun()
#include "NumStringGen.h" #include <algorithm> #include <vector> #include <string> #include <iostream> #include <functional>
Chapter 15: Multiple Inheritance
280
using namespace std;
int main() {
const int sz = 9; vector<string> vs(sz);
// Fill it with random number strings: generate(vs.begin(), vs.end(), NumStringGen()); copy(vs.begin(), vs.end(),
ostream_iterator<string>(cout, "\t")); cout << endl;
const char* vcp[sz]; transform(vs.begin(), vs.end(), vcp,
mem_fun_ref(&string::c_str)); vector<double> vd;
transform(vcp,vcp + sz,back_inserter(vd), std::atof);
copy(vd.begin(), vd.end(), ostream_iterator<double>(cout, "\t"));
cout << endl; } ///:~
The SGI extensions to the STL contain a number of additional function object templates that accomplish more detailed activities than the Standard C++ function object templates, including identity (returns its argument unchanged), project1st and project2nd (to take two arguments and return the first or second one, respectively), select1st and select2nd (to take a pair object and return the first or second element, respectively), and the “compose” function templates.
If you’re using the SGI extensions, you can make the above program denser using one of the two “compose” function templates. The first, compose1(f1, f2), takes the two function objects f1 and f2 as its arguments. It produces a function object that takes a single argument, passes it to f2, then takes the result of the call to f2 and passes it to f1. The result of f1 is returned. By using compose1( ), the process of converting the string objects to char*, then converting the char* to a floating-point number can be combined into a single operation, like this:
//: C05:MemFun4.cpp
// Using the SGI STL compose1 function #include "NumStringGen.h"
#include <algorithm> #include <vector> #include <string> #include <iostream> #include <functional> using namespace std;
Chapter 15: Multiple Inheritance
281
int main() {
const int sz = 9; vector<string> vs(sz);
// Fill it with random number strings: generate(vs.begin(), vs.end(), NumStringGen()); copy(vs.begin(), vs.end(),
ostream_iterator<string>(cout, "\t")); cout << endl;
vector<double> vd;
transform(vs.begin(), vs.end(), back_inserter(vd), compose1(ptr_fun(atof),
mem_fun_ref(&string::c_str))); copy(vd.begin(), vd.end(),
ostream_iterator<double>(cout, "\t")); cout << endl;
} ///:~
You can see there’s only a single call to transform( ) now, and no intermediate holder for the char pointers.
The second “compose” function is compose2( ), which takes three function objects as its arguments. The first function object is binary (it takes two arguments), and its arguments are the results of the second and third function objects, respectively. The function object that results from compose2( ) expects one argument, and it feeds that argument to the second and third function objects. Here is an example:
//: C05:Compose2.cpp
// Using the SGI STL compose2() function #include "copy_if.h"
#include <algorithm> #include <vector> #include <iostream> #include <functional> #include <cstdlib> #include <ctime> using namespace std;
int main() { srand(time(0)); vector<int> v(100);
generate(v.begin(), v.end(), rand); transform(v.begin(), v.end(), v.begin(),
bind2nd(divides<int>(), RAND_MAX/100)); vector<int> r;
copy_if(v.begin(), v.end(), back_inserter(r),
Chapter 15: Multiple Inheritance
282
compose2(logical_and<bool>(), bind2nd(greater_equal<int>(), 30), bind2nd(less_equal<int>(), 40)));
sort(r.begin(), r.end()); copy(r.begin(), r.end(),
ostream_iterator<int>(cout, " ")); cout << endl;
} ///:~
The vector<int> v is first filled with random numbers. To cut these down to size, the transform( ) algorithm is used to divide each value by RAND_MAX/100, which will force the values to be between 0 and 100 (making them more readable). The copy_if( ) algorithm defined later in this chapter is then used, along with a composed function object, to copy all the elements that are greater than or equal to 30 and less than or equal to 40 into the destination vector<int> r. Just to show how easy it is, r is sorted, and then displayed.
The arguments of compose2( ) say, in effect:
(x >= 30) && (x <= 40)
You could also take the function object that comes from a compose1( ) or compose2( ) call and pass it into another “compose” expression … but this could rapidly get very difficult to decipher.
Instead of all this composing and transforming, you can write your own function objects (without using the SGI extensions) as follows:
//: C05:NoCompose.cpp
// Writing out the function objects explicitly #include "copy_if.h"
#include <algorithm> #include <vector> #include <string> #include <iostream> #include <functional> #include <cstdlib> #include <ctime> using namespace std;
class Rgen { const int max;
public:
Rgen(int mx = 100) : max(RAND_MAX/mx) { srand(time(0));
}
int operator()() { return rand() / max; }
Chapter 15: Multiple Inheritance
283
};
class BoundTest { int top, bottom;
public:
BoundTest(int b, int t) : bottom(b), top(t) {} bool operator()(int arg) {
return (arg >= bottom) && (arg <= top);
}
};
int main() { vector<int> v(100);
generate(v.begin(), v.end(), Rgen()); vector<int> r;
copy_if(v.begin(), v.end(), back_inserter(r), BoundTest(30, 40));
sort(r.begin(), r.end()); copy(r.begin(), r.end(),
ostream_iterator<int>(cout, " ")); cout << endl;
} ///:~
There are a few more lines of code, but you can’t deny that it’s much clearer and easier to understand, and therefore to maintain.
We can thus observe two drawbacks to the SGI extensions to the STL. The first is simply that it’s an extension; yes, you can download and use them for free so the barriers to entry are low, but your company may be conservative and decide that if it’s not in Standard C++, they don’t want to use it. The second drawback is complexity. Once you get familiar and comfortable with the idea of composing complicated functions from simple ones you can visually parse complicated expressions and figure out what they mean. However, my guess is that most people will find anything more than what you can do with the Standard, non-extended STL function object notation to be overwhelming. At some point on the complexity curve you have to bite the bullet and write a regular class to produce your function object, and that point might as well be the point where you can’t use the Standard C++ STL. A stand-alone class for a function object is going to be much more readable and maintainable than a complicated function-composition expression (although my sense of adventure does lure me into wanting to experiment more with the SGI extensions…).
As a final note, you can’t compose generators; you can only create function objects whose operator( ) requires one or two arguments.
Chapter 15: Multiple Inheritance
284