He who has begun has half done. Dare to be wise; begin!
—Epistles, I, ii, Horace
This book is for C++ programmers who are frustrated with some of the limitations of the standard C++ library. The book is a tutorial and reference for the library described in the first C++ Library Technical Report, which was approved in 2006 by the International Organization for Standardization (ISO).1 This library, which I’ll call the TR1 library, isn’t part of the C++ Standard. The TR is only “an informative document,” but you can expect to see the library shipped with some compilers and provided as an add-on library from various library vendors. You can also expect to see many of its components incorporated into the standard library in the next C++ standard.2
The TR1 library extends the standard C++ library with new facilities in several areas:
- Utilities: a reference-counted smart pointer; a class template
tuple that generalizes the std::pair class template to handle various numbers of arguments - Containers: sets and maps implemented with hash tables; a fixed-size array
- Call wrappers: more powerful and more flexible templates that provide wrappers around functions, member functions, and other function objects, allowing them to be used more easily as arguments to algorithms
- Type traits: a set of templates that extract properties of types or modify types at compile time, simplifying template metaprogramming
- Numerics: a rich set of random number generators; advanced mathematical special functions; numeric facilities like those added to the C language in 1999
- Regular expressions: classes and functions to describe and search for patterns in text
- C compatibility: types, functions, and macros like those added to the C language in 1995 and 1999
Formal work on the TR1 library began in 2001, when the C++ Standards Committee, through its Library Working Group, asked for proposals. Most of the proposals that made it into the library came from members of Boost,3 an organization set up in 1998 by Standards Committee members who were looking for a way to develop new libraries without the constraints imposed by the process of standardization. The added flexibility from working outside that formal process made it possible to develop the pieces of the Boost libraries on independent schedules far more rapidly than is possible within a standards committee. Boost is a thriving organization, and its library has many useful things that are not in the TR1 library.
The Standards Committee meets twice a year. From 2001 to 2005, the Library Working Group spent most of its time at those meetings, as well as a great deal of e-mail time between meetings, working on the TR1 library. During that time, the working group refined the proposals it had received: simplifying where appropriate, rewriting both for clarity and for the formalism required in an ISO standard, and unifying the presentation of the pieces of the library.
Toward the end of 2002, the company I worked for, Dinkumware, Ltd., began implementing the TR1 library. Dinkumware sells standard libraries for C, C++, and Java, so this was a natural step for us. Our work also helped improve the Technical Report, as we found things that were vaguely described, overspecified, or simply missing.4 Dinkumware has a complete implementation of the TR1 library, and I’ve used it in all the examples in this book.
About This Book
This book is divided into seven parts, each one covering one area of the new facilities. Each part begins with an overview of those facilities. The overview usually includes some remarks about their history and, in some cases, reasons why some obvious features are not in the TR1 library.
Each part has a synopsis of the header or headers that define the librarycomponents discussed in that part. The synopsis is not, in general, compilable code but instead presents an overview of the components that the header defines, listing all the templates, classes, non-member functions, objects, constants, and so on, that are defined in that header. Each of those things is defined in more detail later. However, even the more detailed definitions often are not compilable code. Many of the details are implementation dependent, and nothing would be gained by slogging through them.
Each synopsis is highlighted in gray. Most are followed by the formal requirements from the C++ standard. These formal requirements are indented. Informal discussions are not indented.
Most chapters end with a set of exercises that review the concepts covered in the chapter. Some exercises are easy, and some are deliberately difficult. Don’t worry if you can’t solve all of them.
To avoid confusion, I often use formal language to identify the things that I’m talking about. It’s far too common for discussions to bog down because the participants don’t know whether they’re talking about templates, classes, or objects. For example, the TR1 library has a template named function that holds function objects. Rather than make you guess whether the word function refers to that template or to an object created from that template, I’ve tried to consistently use such phrases as “the class template function,” “specialization of the class template function,” and “object of type function.”
All the code examples are complete: They will compile with a suitable compiler and library. Examples that have a main function will also link and run. The examples have been tested with Microsoft’s C/C++ compiler,5 version 7.1; and with the GNU Project’s gcc compiler,6 version 3.4.3, using the Dinkum TR1 Library Version 1.0 from Dinkumware, Ltd.7 Source code for the examples can be downloaded from my Web site.8
ISO, Conformance, and the TR1 library
The ISO C++ standard is a specification for the C++ programming language, defining what is and is not a valid C++ program and for valid programs telling you, within certain limits, what that program should do. The TR1 library is not part of the C++ standard, although most of the library will almost certainly become part of the standard in its next revision, around 2010. In the meantime, compilers that conform to the C++ standard do not need to include the TR1 library.9
The standard defines and uses several technical terms to talk about valid and invalid programs and about the meaning of a valid program. The Library Technical Report uses the same terminology. Programmers are often confused about the meanings of these terms.10 They’re not particularly complicated, though, so if you’re interested, read on.
A diagnostic message is any compiler11 output message that results from a violation of the rules that the standard sets out. The compiler is allowed to give other messages as well, but the compiler’s documentation is required to tell you which messages are diagnostic messages.
When the standard says that some code results in undefined behavior, it means that the standard does not impose any requirements on what a compiler does when compiling a program that uses that code. Unfortunately, code whose behavior is undefined often results in a program that does exactly what you thought it would do but only until you change to a different compiler. This makes debugging very difficult, so it’s best to avoid writing code whose behavior is undefined.
A diagnosable rule is any standard rule that doesn’t say “no diagnostic required” and that doesn’t result in undefined behavior. If your code violates a rule that doesn’t require a diagnostic, the standard allows your compiler to do anything at all; you’ve done something that the C++ standard does not recognize, so you’re on your own. If your code violates a diagnosable rule, the compiler must issue at least one diagnostic message.12 That doesn’t mean that the compiler must report every diagnosable error; nor does it mean that it cannot give diagnostic messages when compiling a program without diagnosable errors. Technically, a compiler that reports “an error occurred” every time you compile code meets the requirements of the C++ standard. Of course, nobody would use a compiler that did that, if they could avoid it.
The One Definition Rule requires that definitions of things that ought to be the same must in fact be the same. For example, if you define a struct named data with two members of type int in one source file and you define a struct named data with three members of type double in another source file, you’ve violated the One Definition Rule. Such violations don’t require a diagnostic. They can lead to very mysterious problems.
A well-formed program is one that doesn’t violate any diagnosable rule and doesn’t violate the One Definition Rule. An ill-formed program is one that isn’t well formed.
Because they run on systems with finite amounts of storage, compilers have resource limits, which prevent them from compiling programs that are too complicated. The C++ standard recommends some minimum values for such things as the maximum nesting level of compound statements (256), the maximum number of case labels for a switch statement (16,384), and the maximum number of nested template instantiations (17). Compilers are required to document these limits when they are known. These days, however, compilers are getting away from fixed-size tables, instead allocating their internal data structures dynamically as needed; this means tha...
