- •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
parsed, seekg( ) is used to move the file pointer back to the beginning so all the code files can be extracted.
Each line is read and if one of the start markers is found in the line, a CodeFile object is created using that line (which has essential information) and the input stream. The constructor returns when it finishes reading its file, and at that point you can turn around and call write( ) for the code file, and it is automatically written to the correct spot (an earlier version of this program collected all the CodeFile objects first and put them in a container, then wrote one directory at a time, but the approach shown above has code that’s easier to understand and the performance impact is not really significant for a tool like this.
For makefile management, a map<string, Makefile> is created, where the string is the path where the makefile exists. The nice thing about this approach is that the Makefile objects will be automatically created whenever you access a new path, as you can see in the line
makeFiles[cf.path()].addEntry(cf);
then to write all the makefiles you simply iterate through the makeFiles map.
Debugging
This section contains some tips and techniques which may help during debugging.
assert( )
The Standard C library assert( ) macro is brief, to the point and portable. In addition, when you’re finished debugging you can remove all the code by defining NDEBUG, either on the command-line or in code.
Also, assert( ) can be used while roughing out the code. Later, the calls to assert( ) that are actually providing information to the end user can be replaced with more civilized messages.
Trace macros
Sometimes it’s very helpful to print the code of each statement before it is executed, either to cout or to a trace file. Here’s a preprocessor macro to accomplish this:
#define TRACE(ARG) cout << #ARG << endl; ARG
Now you can go through and surround the statements you trace with this macro. Of course, it can introduce problems. For example, if you take the statement:
for(int i = 0; i < 100; i++) cout << i << endl;
And put both lines inside TRACE( ) macros, you get this:
Appendix B: Programming Guidelines
531
TRACE(for(int i = 0; i < 100; i++))
TRACE( cout << i << endl;)
Which expands to this:
cout << "for(int i = 0; i < 100; i++)" << endl; for(int i = 0; i < 100; i++)
cout << "cout << i << endl;" << endl; cout << i << endl;
Which isn’t what you want. Thus, this technique must be used carefully. A variation on the TRACE( ) macro is this:
#define D(a) cout << #a "=[" << a << "]" << nl;
If there’s an expression you want to display, you simply put it inside a call to D( ) and the expression will be printed, followed by its value (assuming there’s an overloaded operator << for the result type). For example, you can say D(a + b). Thus you can use it anytime you want to test an intermediate value to make sure things are OK.
Of course, the above two macros are actually just the two most fundamental things you do with a debugger: trace through the code execution and print values. A good debugger is an excellent productivity tool, but sometimes debuggers are not available, or it’s not convenient to use them. The above techniques always work, regardless of the situation.
Trace file
This code allows you to easily create a trace file and send all the output that would normally go to cout into the file. All you have to do is #define TRACEON and include the header file (of course, it’s fairly easy just to write the two key lines right into your file):
//: C10:Trace.h
// Creating a trace file #ifndef TRACE_H
#define TRACE_H #include <fstream>
#ifdef TRACEON
ofstream TRACEFILE__("TRACE.OUT"); #define cout TRACEFILE__
#endif
#endif // TRACE_H ///:~
Here’s a simple test of the above file:
//: C10:Tracetst.cpp
Appendix B: Programming Guidelines
532
// Test of trace.h #include "../require.h" #include <iostream> #include <fstream> using namespace std;
#define TRACEON #include "Trace.h"
int main() {
ifstream f("Tracetst.cpp"); assure(f, "Tracetst.cpp"); cout << f.rdbuf();
} ///:~
This also uses the assure( ) function defined earlier in the book.
Abstract base class for debugging
In the Smalltalk tradition, you can create your own object-based hierarchy, and install pure virtual functions to perform debugging. Then everyone on the team must inherit from this class and redefine the debugging functions. All objects in the system will then have debugging functions available.
Tracking new/delete & malloc/free
Common problems with memory allocation include calling delete for things you have malloced, calling free for things you allocated with new, forgetting to release objects from the free store, and releasing them more than once. This section provides a system to help you track these kinds of problems down.
To use the memory checking system, you simply link the obj file in and all the calls to malloc( ), realloc( ), calloc( ), free( ), new and delete are intercepted. However, if you also include the following file (which is optional), all the calls to new will store information about the file and line where they were called. This is accomplished with a use of the placement syntax for operator new (this trick was suggested by Reg Charney of the C++ Standards Committee). The placement syntax is intended for situations where you need to place objects at a specific point in memory. However, it allows you to create an operator new with any number of arguments. This is used to advantage here to store the results of the __FILE__ and __LINE__ macros whenever new is called:
//: C10:MemCheck.h
//Memory testing system
//This file is only included if you want to
//use the special placement syntax to find
Appendix B: Programming Guidelines
533
//out the line number where "new" was called. #ifndef MEMCHECK_H
#define MEMCHECK_H
#include <cstdlib> // size_t
//Use placement syntax to pass extra arguments.
//From an idea by Reg Charney:
void* operator new(
std::size_t sz, char* file, int line); #define new new(__FILE__, __LINE__)
#endif // MEMCHECK_H ///:~
In the following file containing the function definitions, you will note that everything is done with standard IO rather than iostreams. This is because, for example, the cout constructor allocates memory. Standard IO ensures against cyclical conditions that can lock up the system.
//: C10:MemCheck.cpp {O}
//Memory allocation tester #include <cstdlib>
#include <cstring> #include <cstdio> using namespace std;
//MemCheck.h must not be included here
//Output file object using cstdio
//(cout constructor calls malloc()) class OFile {
FILE* f; public:
OFile(char* name) : f(fopen(name, "w")) {} ~OFile() { fclose(f); }
operator FILE*() { return f; }
};
extern OFile memtrace;
//Comment out the following to send all the
//information to the trace file:
#define memtrace stdout
const unsigned long _pool_sz = 50000L; static unsigned char _memory_pool[_pool_sz];
static unsigned char* _pool_ptr = _memory_pool;
Appendix B: Programming Guidelines
534
void* getmem(size_t sz) {
if(_memory_pool + _pool_sz - _pool_ptr < sz) { fprintf(stderr,
"Out of memory. Use bigger model\n"); exit(1);
}
void* p = _pool_ptr; _pool_ptr += sz; return p;
}
// Holds information about allocated pointers: class MemBag {
public:
enum type { Malloc, New }; private:
char* typestr(type t) { switch(t) {
case Malloc: return "malloc"; case New: return "new"; default: return "?unknown?";
} |
|
} |
|
struct M { |
|
void* mp; |
// Memory pointer |
type t; |
// Allocation type |
char* file; // File name where allocated |
|
int line; |
// Line number where allocated |
M(void* v, type tt, char* f, int l)
: mp(v), t(tt), file(f), line(l) {} }* v;
int sz, next;
static const int increment = 50 ; public:
MemBag() : v(0), sz(0), next(0) {} void* add(void* p, type tt = Malloc,
char* s = "library", int l = 0) { if(next >= sz) {
sz += increment;
//This memory is never freed, so it
//doesn't "get involved" in the test: const int memsize = sz * sizeof(M);
//Equivalent of realloc, no registration:
Appendix B: Programming Guidelines
535
void* p = getmem(memsize); if(v) memmove(p, v, memsize); v = (M*)p;
memset(&v[next], 0,
increment * sizeof(M));
}
v[next++] = M(p, tt, s, l); return p;
}
// Print information about allocation: void allocation(int i) {
fprintf(memtrace, "pointer %p" " allocated with %s", v[i].mp, typestr(v[i].t));
if(v[i].t == New) fprintf(memtrace, " at %s: %d",
v[i].file, v[i].line); fprintf(memtrace, "\n");
}
void validate(void* p, type T = Malloc) { for(int i = 0; i < next; i++)
if(v[i].mp == p) { if(v[i].t != T) {
allocation(i);
fprintf(memtrace,
"\t was released as if it were " "allocated with %s \n", typestr(T));
}
v[i].mp = 0; // Erase it return;
}
fprintf(memtrace,
"pointer not in memory list: %p\n", p);
}
~MemBag() {
for(int i = 0; i < next; i++) if(v[i].mp != 0) {
fprintf(memtrace,
"pointer not released: "); allocation(i);
}
}
};
Appendix B: Programming Guidelines
536
extern MemBag MEMBAG_;
void* malloc(size_t sz) { void* p = getmem(sz);
return MEMBAG_.add(p, MemBag::Malloc);
}
void* calloc(size_t num_elems, size_t elem_sz) { void* p = getmem(num_elems * elem_sz); memset(p, 0, num_elems * elem_sz);
return MEMBAG_.add(p, MemBag::Malloc);
}
void* realloc(void* block, size_t sz) { void* p = getmem(sz);
if(block) memmove(p, block, sz); return MEMBAG_.add(p, MemBag::Malloc);
}
void free(void* v) { MEMBAG_.validate(v, MemBag::Malloc);
}
void* operator new(size_t sz) { void* p = getmem(sz);
return MEMBAG_.add(p, MemBag::New);
}
void*
operator new(size_t sz, char* file, int line) { void* p = getmem(sz);
return MEMBAG_.add(p, MemBag::New, file, line);
}
void operator delete(void* v) { MEMBAG_.validate(v, MemBag::New);
}
MemBag MEMBAG_;
//Placed here so the constructor is called
//AFTER that of MEMBAG_ :
#ifdef memtrace #undef memtrace
Appendix B: Programming Guidelines
537
#endif
OFile memtrace("memtrace.out");
// Causes 1 "pointer not in memory list" message
///:~
OFile is a simple wrapper around a FILE*; the constructor opens the file and the destructor closes it. The operator FILE*( ) allows you to simply use the OFile object anyplace you would ordinarily use a FILE* (in the fprintf( ) statements in this example). The #define that follows simply sends everything to standard output, but if you need to put it in a trace file you simply comment out that line.
Memory is allocated from an array called _memory_pool. The _pool_ptr is moved forward every time storage is allocated. For simplicity, the storage is never reclaimed, and realloc( ) doesn’t try to resize the storage in the same place.
All the storage allocation functions call getmem( ) which ensures there is enough space left and moves the _pool_ptr to allocate your storage. Then they store the pointer in a special container of class MemBag called MEMBAG_, along with pertinent information (notice the two versions of operator new; one which just stores the pointer and the other which stores the file and line number). The MemBag class is the heart of the system.
You will see many similarities to xbag in MemBag. A distinct difference is realloc( ) is replaced by a call to getmem( ) and memmove( ), so that storage allocated for the MemBag is not registered. In addition, the type enum allows you to store the way the memory was allocated; the typestr( ) function takes a type and produces a string for use with printing.
The nested struct M holds the pointer, the type, a pointer to the file name (which is assumed to be statically allocated) and the line where the allocation occurred. v is a pointer to an array of M objects – this is the array which is dynamically sized.
The allocation( ) function prints out a different message depending on whether the storage was allocated with new (where it has line and file information) or malloc( ) (where it doesn’t). This function is used inside validate( ), which is called by free( ) and delete( ) to ensure everything is OK, and in the destructor, to ensure the pointer was cleaned up (note that in validate( ) the pointer value v[i].mp is set to zero, to indicate it has been cleaned up).
The following is a simple test using the memcheck facility. The MemCheck.obj file must be linked in for it to work:
//: C10:MemTest.cpp //{L} MemCheck
// Test of MemCheck system #include "MemCheck.h"
int main() {
void* v = std::malloc(100); delete v;
int* x = new int;
Appendix B: Programming Guidelines
538