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 that the limits change, depending on what else is being done in the program. What this comes down to is that you can’t assume that a well-formed program that compiles with one compiler will also compile with another compiler, including a different version of the “same” compiler. The program can run up against more restrictive resource limits when you change compilers.
A conforming implementation is a compiler that correctly compiles wellformed programs that do not exceed its resource limits. The resulting executable must, of course, do what the C++ standard says it should do. That’s not quite as clear-cut as it seems, though; in many cases, the standard allows executables compiled from the same source code to behave differently.
The C++ standard sometimes says that code has unspecified behavior. Usually, this means that it could do several reasonable things, and the C++ standard doesn’t require any particular one of them. For example, the order of evaluation of arguments to a function is unspecified. This means that for code like f(g(), h()), the compiler is free to call the function g before it calls the function h or to call h before it calls g. If your code assumes that g will be called before h, you may be in for a surprise when you change compilers or when you change the optimization settings for the compiler you’ve been using.
The standard also says that some code has implementation-defined behavior. Like code with unspecified behavior, there are usually several reasonable alternatives, and the standard doesn’t require any particular one. It does, however, require the implementation to document what it does. For example, the basic type char can be either signed or unsigned, and the compiler’s documentation must tell you which one you get.
Finally, the normative text in the standard is what you look to for the syntactic and semantic requirements. Text enclosed by “Note: ... -- end note”, examples, text in footnotes, and chapter and section titles are non-normative; they help you find your way through the standard, but they do not impose requirements. For example, if a footnote and a piece of ordinary text conflict, the ordinary text wins.
1 See www.iso.ch.
2 In April, 2006, all of the TR1 library except the special math functions was added to the draft of the next C++ standard.
3 See www.boost.org
4 That’s not a criticism of the work done by the folks at Boost; they began by writing documentation for their library contributions, then turned that documentation into preliminary specifications for their proposals. That second step is difficult, and it rarely goes smoothly.
5 www.microsoft.com
6 www.gnu.org
7 www.dinkumware.com
8 www.petebecker.com/tr1book
9 Technically, they should not include it, because it adds names that could conflict with names that are already in use in valid programs. In practice, this won’t be a significant problem. The TR1 library puts its names in the namespace tr1, which is nested in the namespace std. As a result, the directive using namespace std; will hoist the name tr1 into the global namespace, possibly clashing with existing code that uses that name. In addition, code that defines macros with the same names as any of the contents of the TR1 library will run into problems. Of course, we all write macro names in capitals, so this shouldn’t cause any problems.
10 In fact, many of the original proposals that turned into the TR1 library misused them; the Library Working Group tried to fix these misuses, but a few mistakes may still be left in the Technical Report.
11 The standard uses the term implementation to refer to the compiler, linker, and whatever else is needed to convert source code into an executable program. I’ll use the conventional shorthand term compiler to mean the same thing.
12 You’ll often hear that the compiler should refuse to compile code that violates a diagnosable rule. That’s wrong. The only requirement is that the compiler must issue a diagnostic. That’s the hook for language extensions: Once it has issued a diagnostic, the compiler can do whatever the compiler writer thinks is appropriate.
