Footnotes
Preface
[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.
[6] www.gnu.org
[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.
Chapter 1
[1] Each library implementation is allowed to put an upper limit on the value of N. The Library Technical Report recommends that this upper limit be at least 10.
[2] Note that n is zero based: For the first element, n == 0. This numbering is different from the numbering that we use for the template’s type arguments, which starts at 1. If we tried to give the type arguments names that started with 0, we’d end up with the last argument being named something like TN-1, which isn’t a valid identifier.
[3] This is what you do when you alphabetize a list of words; andy comes before ants because d comes before t.
[4] A tuple holding int values is more natural, but technically, you can’t copy or display uninitialized values of integral types other than the three forms of char in portable code. Although this is rarely a problem in practice, the behavior of a program that does this is not defined by the C++ standard.
[5] This function could be called distance and suitably overloaded, but that would get confusing when we start talking about a template with that name later on.
Chapter 2
[1] This reference count doesn’t have to actually exist anywhere; these templates can be implemented with linked lists, and in that case the reference count is the number of elements in a list.
[2] Typically by exiting from a block where the object was defined or by destroying an object that holds a shared_ptr object; you’ll rarely, if ever, need to create shared_ptr objects with new.
[3] This typically happens when not enough memory is available to create a manager object to track the original pointer and its reference count.
[4] Actually, a copy of sp1 is in the container; the copy owns the same resource as the original.
[5] Don’t do this from C’s constructor. It probably won’t work.
[6] Typically, the implementation allocates a manager object that holds the original pointer and its reference count; when the shared_ptr object is copied, the new object gets a pointer to the same manager object.
[7] This is not a conclusive test for correctness. If the resource was being deleted through the pointer to base1, the behavior would be undefined; one possible symptom of this undefined behavior would be running the “right” destructor. However, with every compiler I’ve used, that wouldn’t happen, so getting the right destructor usually means that the right pointer was deleted.
[8] The most obvious implementation technique is to make every update a critical section, guarded by a mutex lock; that could be quite slow. It would be much faster to use atomic updates to avoid locking whenever possible, but the resulting code is rather fragile and notoriously difficult to test thoroughly.
Chapter 3
[1] Please don’t refer to the standard C++ library as the STL.
[2] More commonly known by the rather confusing terms “function objects” and “functors,” which we’ll dismiss in Chapter 6.
[3] Iterators are more sophisticated than this sketch implies, but the additional details aren’t needed here.
[4] We’ll look at callable objects in more detail in Chapter 6.
[5] Associative containers are typically implemented with red-black trees.
[6] Unordered associative containers are typically implemented with hash tables.
[7] If you haven’t looked ahead, use the header <unordered_set>. The template class unordered_set is in the namespace std::tr1.
Chapter 4
[1] Thus, given an object arr of type array<Ty, N>, for all values of n in the half-open range
[2] For class types with non-trivial default constructors, value-initialization uses the default constructor. For class types with trivial default constructors, it value-initializes each member. For non-class types, it sets the value to 0.
Chapter 5
[1] Well, they’re as happy as compiler guys ever get. It’s a tough job.
[2] The more obvious names, hash_map, and so on, were rejected because they are already widely used for hash tables that are somewhat different from the hashed containers in TR1.
[3] Despite what some compilers may tell you, this conversion is well defined and meaningful. If you get a warning for this code, either complain to the compiler writer or add a cast.
[4] The actual algorithm used in the unordered containers is more sophisticated than this, but it still degenerates into linear time when the buckets are over-filled.
[5] The reason is that the unordered containers are unordered. Deciding whether two unordered containers hold sets of equal elements is expensive, and it is not at all clear what it would mean for one unordered container to be less than another.
[6] The main difference between associative containers and unordered associative containers is in the time-complexity requirements. The complexity of inserting an object into an associative container and of searching an associative container is O(log n). As we’ve seen, in unordered associative containers, it is often O(1) but sometimes O(n).
[7] You can look at the details in Appendix A.2 and Appendix A.3.
[8] This requirement means that the simple implementation of a hash table in the example in Section 5.2 can’t be used as an unordered container. It doesn’t group elements that compare equal together, so there might not be a valid range that holds all elements that compare equal to a given key and no others.
[9] Based on an example in The C++ Standard Library [Jos99, 209–211].
Chapter 6
[1] So, a less_than_value object can hold the value that you want to compare to; a less_-than_three function always compares against the same value.
[2] You might be surprised to see pointer to member data in this list; a pointer to member data is obviously not like a function. But the new function template mem_fn can create objects that bind a pointer to member data and a pointer or reference to an object; this uses the same function call syntax as an actual function call, so pointers to member data are callable types.
[3] This wording may seem a little convoluted, but it was carefully written to not require that the type define a function call operator. That leaves open the possibility that a function object can provide a conversion operator that returns a pointer to function; when such an object appears to the left of a function call operator, the compiler uses the conversion function to get the function pointer and then calls the function it points to.
[4] Writing forwarding call wrappers as templates is a tricky problem. Some lvalues are modifiable, and some aren’t. Modifiable lvalues have to be passed by reference, so that the called function can modify them. Nonmodifiable lvalues have to be passed by value or by reference to const, so that the called function can’t modify them. At present, nobody has figured out how to detect which is which, so a function call operator that’s written as a template can’t simply forward its arguments to its target object.
[5] In the TR, this metafunction is named INVOKE; although I’m one of the people responsible for this name overloading, I’ve now concluded that it’s too clever and shouldn’t be used.
[6] That is, not defined as a consequence of having a weak result type. Some call wrapper types have a weak result type in certain circumstances, have a specific type named result_type
[7] That is, its const and volatile qualifiers are determined in part by the type of the object.
[8] Since it does not describe a function returning the callable type, the template argument is not, in fact, a function type. The compiler doesn’t care, though, so smuggling in the callable type in the guise of a return type works.
[9] If you really want to know, when you have a pointer to function, the argument type list goes immediately after the *:result_of<int(*(float))(double)>::type.
[10] This also means that you can’t use result_of to determine which of several overloaded versions of operator() will be called.
[11] This requirement is not in TR1, so an implementation that conforms to the TR1 spec-ification does not have to satisfy it. It was accidentally left out and will be added in the future.
[12] That is, if F defines a nested template named result, result_of uses that template; if F doesn’t define that template, it’s an error.
[13] The function objects in the standard C++ library are required to be derived from one of these two templates. However, the call wrappers defined in the standard C++ library don’t rely on this inheritance; rather, they rely on the presence of the member type names that these bases provide. If you write your own function objects, you don’t have to use unary_function or binary_function, but you do have to provide the required type names.
[14] In particular, I’ve used explicit typedefs for argument_type and result_type to make it clearer where they come from. The library code uses the template std::unary_function to define these names.
[15] For example, the object returned by mem_fn (Chapter 7) can be called with an object or a pointer, but there’s no way to say that in a single typedef, so TR1 chooses Ty* as its argument_type or first_argument_type.
Chapter 7
[1] That is, it asserts that a mem_fn object that holds a pointer to a member of class Ty can be called with an argument of type Ty* but does not assert that it can be called with an argument of type Ty.
Chapter 9
[1] Of course, template programming zealots declare that this is primarily a compiler problem and that someday wonderful compilers will eliminate template code bloat. Today, however, the problem is real and has to be considered in any library design.
[2] In the old-fashioned sense, now sometimes referred to as “runtime polymorphism.”
[3] Unlike direct calls from template code, the virtual function calls from the common code to the specialized types typically won’t be inlined.
[4] Unfortunately, the cast is needed to choose among the overloaded versions of cos.
Chapter 10
[1] This example also works if you use the standard algorithm count_if, which is remarkably similar to count_elements. The example uses count_elements to show you how the algorithm is implemented.
[2] More generally, the problem arises for all rvalues. A value defined by the expression int() also can’t be passed by reference.
[3] Language changes could make it easier to write these function templates. If those changes are made, you can expect bind, reference_wrapper, and mem_fn to take advantage of them.
[4] However, adding your own specializations does not change the bind implementation’s upper limit on the number of placeholders. So the value you put in the specialization must be greater than zero and less than the upper limit.
Chapter 11
[1] The header <cmath>, for example, provides three versions of the function named abs: one that takes an argument of type double, one that takes float, and one that takes long double. When code calls this function, the compiler looks at the type of the argument that is being passed and determines from that which version of the function to call.
[2] Strictly speaking, less visible repetition. The obvious implementation of the class template is_integral provides a specialization for each integral type, so the repetition is in the library code. That’s a big improvement over writing all the overloads wherever you need them; in addition, if the compiler provides a way of asking about type properties, is_-integral can ask the compiler, with no need to list all the possible integral types.
[3] These terms, however, aren’t used anywhere else in the TR1 library specification.
[4] In most cases, these predicates are used to choose optimizations; the unoptimized version works but is slower.
[5] Plain old data. If you want the exact details of its definition, you’ll have to dig through the C++ standard.
[6] The wording in TR1 doesn’t quite say that, but that’s the intention.
[7] This means, in part, that aligned_storage cannot be used to create a typical DMA buffer, which usually must be aligned on a boundary that’s a multiple of a fairly large number, such as 16K.
[8] In order to use memcpy, the data being copied must be contiguous. No iterator type guarantees contiguous data, so you must know the source of your data if you’re going to do this.
[9] The transpose of an array arr0 of type Ty[M][N] is an array arr1 of type Ty[N][M] such that arr1[j][i] == arr0[i][j] for all values of i in the half-open range [0, M) and all values of j in the half-open range [0, N).
Chapter 12
[1] The revision made changes in other areas, as well. See Chapter 22.
[2] The C++ standard was revised in 2003, but the Standards Committee only made changes needed to fix defects.
[3] TR1 is entirely library extensions and doesn’t add anything to the language itself.
[4] People get PhDs in how to do floating-point math accurately. A little closer to home, P.J. Plauger and Chris Walker, both also at Dinkumware, have burned thousands of hours of computer time refining the Dinkumware implementation of the TR1 Math Special Functions (Section 12.8), producing results that are far more accurate than any other implementation of these functions that we know of.
[5] Thus, in a normalized representation, the value of the significand of a nonzero number is always greater than or equal to 1/β and less than 1.
[6] The full contents of this header are presented in Appendix A, in Section A.4.
[7] Similar macros, with names that begin with FLT and LDBL instead of DBL, describe the properties of the types float and long double, respectively. The members of the template specializations numeric_limits<float> and numeric_limits<long double> describe float and long double.
[8] Which are, of course, exact when the base of the representation is 10.
[9] Since floating-point values are written in base 10, the requirements are given for the base 10 versions of the various properties.
[10] The C99 standard gives more details.
[11] In particular, many implementations allow installing a trap handler, which will be called when a particular floating-point exception occurs.
[12] Don’t confuse floating-point exceptions with C++ exceptions; they’re completely unrelated.
[13] And C99 and IEC 60559.
[14] Or, of course, within a related set of functions that are within your control.
[15] In fact, it permits two flavors of NaN, as well: quiet NaNs and signaling NaNs. Any operation on a signaling NaN produces a quiet NaN, so you can do very little with signaling NaNs.
[16] The complete synopsis is in Appendix A.5.
[17] The complete synopsis is in Appendix A.5.
Chapter 13
[1] Or, more generally, for any simulation of a real-world process.
[2] The TR1 library calls these things pseudo-random number engines. However, since the other two categories also involve pseudo-random sequences, consistency dictates using either pseudo-random or random for all three.
[3] This circumlocution avoids overspecifying these types. It’s not significant here, but when we look at the requirements for an engine, for example, a more natural formulation might require a member function seed() and a member function seed(numeric-type ), but that would prohibit implementing these functions as a single function with a default argument.
[4] That is, the result is in the closed range [min(), max()].
[5] That is, the result is in the half-open range [min(), max()).
[6] This sounds a lot like the definition of a distribution. The key difference is that a compound engine applies a specified algorithm to its input to produce its output values. A distribution produces values distributed in a particular way but without specifying the algorithm to use. Thus, every conforming implementation of a compound engine, given the same engine or engines for input, will produce the same sequence of values. This is not the case for distributions.
[7] Thus, eng == eng1 after executing os << eng followed immediately by is >> eng1.
[8] Of course, this doesn’t mean that every implementation must exactly follow these details, just that it must act as if it did. In particular, several of the TR1 engines can be implemented more efficiently by holding more state values than TR1 requires. However, in all cases, the text written to a stream must be as specified.
[9] Conceptually, that is. That value can’t be represented in an object of type UType.
[10] This avoids the degenerate case of a generator that produces nothing but 0 values.
[11] For example, the most common form of the Mersenne Twister, embodied in mt19937, requires 624 32-bit values to store its state.
[12] Don’t worry about the modulus operation; mathematically, that requires division, but in fact, it’s simply a test and a subtraction.
[13] The TR requires 0 <= R <= P, but passing 0 for the template argument R has the same effect as passing 1. There’s no benefit from using 0.
[14] But heed Knuth’s warning that modifying random number generators often makes them worse. See [Knu98a, 26].
[15] Yes, technically, floating-point values aren’t really continuous and could be considered discrete. But for computational purposes, floating-point numbers are close enough to continuous that, with a bit of care, we can treat them as continuous. That’s important, because we use them to model real-world processes that are, above the quantum level, continuous.
[16] If you need to use a generator that doesn’t return values in this range, you can adjust the result with variate_generator (see Section 13.8).
[17] Unlike engines, distributions cannot be written and read portably. The details of writing and reading are implementation specific. This means that you can use a distribution’s inserter and extractor for checkpointing but not for parallelizing (see Section 13.2).
[18] So in the preceding example, it’s possible that the last two generated numbers will be the same.
[19] This allows use of uniform_int objects with such algorithms as std::random_shuffle, which change the desired range as they progress through their data.
[20] The meaning of a nonintegral number of state changes (i.e., A not an integer) is left to philosophers.
[21] The TR1 library specification says that min0 must be less than or equal to max0. That’s not right, because the distribution returns values that are strictly less than max0. If min0 and max0 were equal, the distribution could not return any values.
[22] These lags are far too small to generate good values, and the seed values that we use later are not particularly good, but they have the advantage of being easy to describe and easy to code. When you use random number engines in real programs, neither of these factors is important.
[23] By now, you’ve probably guessed that InIt represents an input iterator.
Chapter 15
[1] The ECMAScript grammar in the TR1 library is a superset of the ECMAScript language.
[2] The UNIX utilities grep and egrep can take a file as the source of the regular expression that they try to match. In that case, each line in the file is a separate concatenated regular expression.
[3] Capture group 1 begins with the first ‘(’, and capture group 2 begins with the second.
Chapter 16
[1] Well, not necessarily. Implementations of the TR1 library are allowed—but not required— to provide traits classes in addition to the ones needed for char and wchar_t. But for portable code, you need your own traits class for any type other than char or wchar_t.
[2] The conversion to lowercase is done by calling use_facet<ctype<Elem> >(getloc()).tolower(ch). We look at that call in more detail in Chapter 21; for now, it converts the character ch to lowercase in accordance with the rules for the traits object’s current locale. That is, case-insensitive comparisons depend on the locale.
[3] That may sound like a distinction without a difference, but when writing character ranges, it’s important to understand which characters are represented by the range. The regular expression “[A-z]” doesn’t change meaning with the icase flag. Either way, it’s probably a mistake.
[4] In the C locale, the representations of the digits ‘0’ through ‘9’ are required to be contiguous and increasing. That’s also why you can translate single digits into numeric values with ch - ‘0’.
[5] In ASCII, characters are represented by 7 bits, so the representations in the ASCII character set are all in the range [0, 127].
[6] The TR1 library specification doesn’t talk about raw matching speed, so there are no formal requirements here. However, this flag makes it possible in many cases to simplify the internal representation of the regular expression object and to simplify the algorithm used to detect matches.
[7] This optimization typically means converting a nondeterministic finite automaton into a deterministic finite automaton. There are well-understood algorithms for doing this. Unfortunately, this conversion can sometimes be very complex; hence, very slow. So don’t ask for it if you don’t need it.
Chapter 17
[1] Discussed in Chapter 20.
[2] Technically, match_default is required to have a value of 0, so it can be combined with any of the other flags without changing their meanings.
[3] This one is somewhat limited. For a good discussion of the problems involved in recognizing hostnames, see [Fri02].
Chapter 18
[1] Technically, this comparison requires converting the sub_match object to a basic_string object, then calling its compare member function. That’s a fairly expensive operation, which can usually be skipped. For sequences of characters of type char and wchar_t, the corresponding string types are basic_string<char> and basic_string<wchar_t>. Portable code can’t tell, in these cases, whether the conversion to string was done, so under the as-if rule, the implementation doesn’t have to do the conversion so long as it returns the right answer. For user-defined character types, the conversion is necessary because users are allowed to specialize basic_string for user-defined types. Such a specialization could make notes about whether it was used, so the as-if rule can’t be used to eliminate the conversion.
[2] That rather hairy regular expression is taken from [Fri02], which explains its limitations and discusses possible improvements.
[3] If you want to see the full list, it’s in Appendix A.1.
[4] That is, it’s not modifiable by ordinary code. The regular expression search functions that take a regex_match object, of course, modify its contents during a search.
[5] As defined in the C++ standard.
Chapter 19
[1] That is, unless “reuse” means “cut and paste,” as is often the case, for example, in Java.
[2] The type cregex_iterator is a regex_iterator that looks at sequences delineated by char*s.
[3] Note that the iterator holds the address of the regular expression object, not a copy. Once the regular expression object is destroyed, the iterator can no longer be used.
[4] That is, search for text matching the regular expression “<CODE>(.*?)</CODE>”; for each successful match, write out the contents of capture group 1.
[5] Hint: Read the entire text file into a string object by creating an if stream object to read the file and a basic_ostringstream object to build the string, and inserting the buffer returned by the ifstream’s member function rdbuf() into the basic_ostringstream object.
[6] You’ll have to write a callable type whose function call operator takes a match_results object and copies the first capture group to cout.
[7] That is, search for text matching the regular expression “<(CODE|PRE)>(.*?)</1>”; for each successful match, write out the contents of capture group 2.
[8] See Exercise 2 in Chapter 17 for a suitable regular expression.
[9] Hint: Write a regular expression that describes the separator, and use an iterator that shows the text that doesn’t match the separator.
Chapter 20
[1] Of course, real pet owners often have more than one pet. But let’s not make things too complicated.
[2] In this example, I’ve put the address file in a text string rather than write a separate file. In the real world, of course, instead of using an istringstream to read the address information, you’d use an ifstream.
[3] Of course, you don’t have to write obscure code just because you can. This particular example would be much clearer if it simply appended the contents of tail to the string after calling format. But if it did, that it wouldn’t use the return value, so it wouldn’t be here as an example.
[4] That intriguing coinage in the last sentence of the result happened in draft documentation at a company where I worked.
[5] See Exercise 2 in Chapter 17 for a suitable regular expression.
Chapter 21
[1] And with wide characters, L“w”, presumably; this omission seems to be an oversight.
[2] And L“blank”.
Chapter 22
[1] Or 1989, depending on which standards organization you’re talking about.
[3] The C++ standard uses similar words.
[4] That is, -32767 through 32767.
[5] That is, -2, 147, 483, 647 through 2,147,483,647.
[6] That is, -922337203685… Well, you get the idea.
[7] Which is what standards are supposed to do, which is why I grudgingly agree that the ugly name long long int ought to be part of the language.
[8] At the time of this writing, the appropriate changes have been approved. It’s unlikely that they’ll be removed.
[9] It doesn’t say that, but it wouldn’t bother me a bit if an implementation of the TR1 library documented that it doesn’t provide the functions that take 64-bit integer types, because the compiler it’s targeting doesn’t support them.
[10] TR1 does not add a requirement that the template numeric_limits, defined in <limits>, support these types.
[11] Thus, if int32_t is a synonym for int, uint32_t must be a synonym for unsigned int.
[12] Whatever that means. In fact, the C99 standard acknowledges that the designated type need not be fastest for all purposes.
[13] The n specifier takes the address of an integer variable and stores the number of characters written so far into the variable that it points at.
[14] The h length modifier, which was part of the C standard before C99, does the same thing for arguments of type signed short and unsigned short.
[15] You get extra credit if you know what the value returned by printf means.