Item 35:  Familiarize yourself with °the language standard.

Since its publication in 1990, °The Annotated C++ Reference Manual (see page 285) has been the definitive reference for working programmers needing to know what is in C++ and what is not. In the years since the ARM (as it's fondly known) came out, the °ISO/ANSI committee standardizing the language has changed (primarily extended) the language in ways both big and small. As a definitive reference, the ARM no longer suffices.

The post-ARM changes to C++ significantly affect how good programs are written. As a result, it is important for C++ programmers to be familiar with the primary ways in which the C++ specified by the standard differs from that described by the ARM.

The °ISO/ANSI standard for C++ is what vendors will consult when implementing compilers, what authors will examine when preparing books, and what programmers will look to for definitive answers to questions about C++. Among the most important changes to C++ since the ARM are the following:

• New features have been added: RTTI, namespaces, bool, the mutable and explicit keywords, the ability to overload operators for enums, and the ability to initialize constant integral static class members within a class definition.
• Templates have been extended: member templates are now allowed, there is a standard syntax for forcing template instantiations, non-type arguments are now allowed in function templates, and class templates may themselves be used as template arguments.
• Exception handling has been refined: exception specifications are now more rigorously checked during compilation, and the unexpected function may now throw a bad_exception object.
• Memory allocation routines have been modified: operator new[] and operator delete[] have been added, the operators new/new[] now throw an exception if memory can't be allocated, and there are now alternative versions of the operators new/new[] that return 0 when an allocation fails (see Item E7).
• New casting forms have been added: static_cast, dynamic_cast, const_cast, and reinterpret_cast.
• Language rules have been refined: redefinitions of virtual functions need no longer have a return type that exactly matches that of the function they redefine, and the lifetime of temporary objects has been defined precisely.

Almost all these changes are described in °The Design and Evolution of C++ (see page 285). Current C++ textbooks (those written after 1994) should include them, too. (If you find one that doesn't, reject it.) In addition, More Effective C++ (that's this book) contains examples of how to use most of these new features. If you're curious about something on this list, try looking it up in the index.

The changes to C++ proper pale in comparison to what's happened to the standard library. Furthermore, the evolution of the standard library has not been as well publicized as that of the language. The Design and Evolution of C++, for example, makes almost no mention of the standard library. The books that do discuss the library are sometimes out of date, because the library changed quite substantially in 1994.

The capabilities of the standard library can be broken down into the following general categories (see also Item E49):

• Support for the standard C library. Fear not, C++ still remembers its roots. Some minor tweaks have brought the C++ version of the C library into conformance with C++'s stricter type checking, but for all intents and purposes, everything you know and love (or hate) about the C library continues to be knowable and lovable (or hateable) in C++, too.
• Support for strings. As Chair of the working group for the standard C++ library, Mike Vilot was told, "If there isn't a standard string type, there will be blood in the streets!" (Some people get so emotional.) Calm yourself and put away those hatchets and truncheons — the standard C++ library has strings.
• Support for localization. Different cultures use different character sets and follow different conventions when displaying dates and times, sorting strings, printing monetary values, etc. Localization support within the standard library facilitates the development of programs that accommodate such cultural differences.
• Support for I/O. The iostream library remains part of the C++ standard, but the committee has tinkered with it a bit. Though some classes have been eliminated (notably iostream and fstream) and some have been replaced (e.g., string-based stringstreams replace char*-based strstreams, which are now deprecated), the basic capabilities of the standard iostream classes mirror those of the implementations that have existed for several years.
• Support for numeric applications. Complex numbers, long a mainstay of examples in C++ texts, have finally been enshrined in the standard library. In addition, the library contains special array classes (valarrays) that restrict aliasing. These arrays are eligible for more aggressive optimization than are built-in arrays, especially on multiprocessing architectures. The library also provides a few commonly useful numeric functions, including partial sum and adjacent difference.
• Support for general-purpose containers and algorithms. Contained within the standard C++ library is a set of class and function templates collectively known as the Standard Template Library (STL). The STL is the most revolutionary part of the standard C++ library. I summarize its features below.

Before I describe the STL, though, I must dispense with two idiosyncrasies of the standard C++ library you need to know about.

First, almost everything in the library is a template. In this book, I may have referred to the standard string class, but in fact there is no such class. Instead, there is a class template called basic_string that represents sequences of characters, and this template takes as a parameter the type of the characters making up the sequences. This allows for strings to be made up of chars, wide chars, Unicode chars, whatever.

What we normally think of as the string class is really the template instantiation basic_string<char>. Because its use is so common, the standard library provides a typedef:

typedef basic_string<char> string;

Even this glosses over many details, because the basic_string template takes three arguments; all but the first have default values. To really understand the string type, you must face this full, unexpurgated declaration of basic_string:

template<class charT,
         class traits = string_char_traits<charT>,
         class Allocator = allocator>
  class basic_string;

You don't need to understand this gobbledygook to use the string type, because even though string is a typedef for The Template Instantiation from Hell, it behaves as if it were the unassuming non-template class the typedef makes it appear to be. Just tuck away in the back of your mind the fact that if you ever need to customize the types of characters that go into strings, or if you want to fine-tune the behavior of those characters, or if you want to seize control over the way memory for strings is allocated, the basic_string template allows you to do these things.

The approach taken in the design of the string type — generalize it and make the generalization a template — is repeated throughout the standard C++ library. IOstreams? They're templates; a type parameter defines the type of character making up the streams. Complex numbers? Also templates; a type parameter defines how the components of the numbers should be stored. Valarrays? Templates; a type parameter specifies what's in each array. And of course the STL consists almost entirely of templates. If you are not comfortable with templates, now would be an excellent time to start making serious headway toward that goal.

The other thing to know about the standard library is that virtually everything it contains is inside the namespace std. To use things in the standard library without explicitly qualifying their names, you'll have to employ a using directive or (preferably) using declarations (see Item E28). Fortunately, this syntactic administrivia is automatically taken care of when you #include the appropriate headers.

The Standard Template Library

The biggest news in the standard C++ library is the STL, the Standard Template Library. (Since almost everything in the C++ library is a template, the name STL is not particularly descriptive. Nevertheless, this is the name of the containers and algorithms portion of the library, so good name or bad, this is what we use.)

The STL is likely to influence the organization of many — perhaps most — C++ libraries, so it's important that you be familiar with its general principles. They are not difficult to understand. The STL is based on three fundamental concepts: containers, iterators, and algorithms. Containers hold collections of objects. Iterators are pointer-like objects that let you walk through STL containers just as you'd use pointers to walk through built-in arrays. Algorithms are functions that work on STL containers and that use iterators to help them do their work.

It is easiest to understand the STL view of the world if we remind ourselves of the C++ (and C) rules for arrays. There is really only one rule we need to know: a pointer to an array can legitimately point to any element of the array or to one element beyond the end of the array. If the pointer points to the element beyond the end of the array, it can be compared only to other pointers to the array; the results of dereferencing it are undefined.

We can take advantage of this rule to write a function to find a particular value in an array. For an array of integers, our function might look like this:

int * find(int *begin, int *end, int value)
{
  while (begin != end && *begin != value) ++begin;
  return begin;
}

This function looks for value in the range between begin and end (excluding end — end points to one beyond the end of the array) and returns a pointer to the first occurrence of value in the array; if none is found, it returns end.

Returning end seems like a funny way to signal a fruitless search. Wouldn't 0 (the null pointer) be better? Certainly null seems more natural, but that doesn't make it "better." The find function must return some distinctive pointer value to indicate the search failed, and for this purpose, the end pointer is as good as the null pointer. In addition, as we'll soon see, the end pointer generalizes to other types of containers better than the null pointer.

Frankly, this is probably not the way you'd write the find function, but it's not unreasonable, and it generalizes astonishingly well. If you followed this simple example, you have mastered most of the ideas on which the STL is founded.

You could use the find function like this:

int values[50];

...

int *firstFive = find(values,        // search the range
                      values+50,     // values[0] - values[49]
                      5);            // for the value 5

if (firstFive != values+50) {        // did the search succeed?

...                                // yes

}
else {
  ...                                // no, the search failed
}

You can also use find to search subranges of the array:

int *firstFive = find(values,        // search the range
                      values+10,     // values[0] - values[9]
                      5);            // for the value 5

int age = 36;

...

int *firstValue = find(values+10,    // search the range
                       values+20,    // values[10] - values[19]
                       age);         // for the value in age

There's nothing inherent in the find function that limits its applicability to arrays of ints, so it should really be a template:

template<class T>
T * find(T *begin, T *end, const T& value)
{
  while (begin != end && *begin != value) ++begin;
  return begin;
}

In the transformation to a template, notice how we switched from pass-by-value for value to pass-by-reference-to-const. That's because now that we're passing arbitrary types around, we have to worry about the cost of pass-by-value. Each by-value parameter costs us a call to the parameter's constructor and destructor every time the function is invoked. We avoid these costs by using pass-by-reference, which involves no object construction or destruction (see Item E22).

This template is nice, but it can be generalized further. Look at the operations on begin and end. The only ones used are comparison for inequality, dereferencing, prefix increment (see Item 6), and copying (for the function's return value — see Item 19). These are all operations we can overload, so why limit find to using pointers? Why not allow any object that supports these operations to be used in addition to pointers? Doing so would free the find function from the built-in meaning of pointer operations. For example, we could define a pointer-like object for a linked list whose prefix increment operator moved us to the next element in the list.

This is the concept behind STL iterators. Iterators are pointer-like objects designed for use with STL containers. They are first cousins to the smart pointers of Item 28, but smart pointers tend to be more ambitious in what they do than do STL iterators. From a technical viewpoint, however, they are implemented using the same techniques.

Embracing the notion of iterators as pointer-like objects, we can replace the pointers in find with iterators, thus rewriting find like this:

template<class Iterator, class T>
Iterator find(Iterator begin, Iterator end, const T& value)
{
  while (begin != end && *begin != value) ++begin;
  return begin;
}

Congratulations! You have just written part of the Standard Template Library. The STL contains dozens of algorithms that work with containers and iterators, and find is one of them.

Containers in STL include bitset, vector, list, deque, queue, priority_queue, stack, set, and map, and you can apply find to any of these container types:

list<char> charList;                  // create STL list object
                                      // for holding chars
...

// find the first occurrence of 'x' in charList
list<char>::iterator it = find(charList.begin(),
                               charList.end(),
                               'x');

"Whoa!", I hear you cry, "This doesn't look anything like it did in the array examples above!" Ah, but it does; you just have to know what to look for.

To call find for a list object, you need to come up with iterators that point to the first element of the list and to one past the last element of the list. Without some help from the list class, this is a difficult task, because you have no idea how a list is implemented. Fortunately, list (like all STL containers) obliges by providing the member functions begin and end. These member functions return the iterators you need, and it is those iterators that are passed into the first two parameters of find above.

When find is finished, it returns an iterator object that points to the found element (if there is one) or to charList.end() (if there's not). Because you know nothing about how list is implemented, you also know nothing about how iterators into lists are implemented. How, then, are you to know what type of object is returned by find? Again, the list class, like all STL containers, comes to the rescue: it provides a typedef, iterator, that is the type of iterators into lists. Since charList is a list of chars, the type of an iterator into such a list is list<char>::iterator, and that's what's used in the example above. (Each STL container class actually defines two iterator types, iterator and const_iterator. The former acts like a normal pointer, the latter like a pointer-to-const.)

Exactly the same approach can be used with the other STL containers. Furthermore, C++ pointers are STL iterators, so the original array examples work with the STL find function, too:

int values[50];

...

int *firstFive = find(values, values+50, 5);       // fine, calls
                                                   // STL find

At its core, STL is very simple. It is just a collection of class and function templates that adhere to a set of conventions. The STL collection classes provide functions like begin and end that return iterator objects of types defined by the classes. The STL algorithm functions move through collections of objects by using iterator objects over STL collections. STL iterators act like pointers. That's really all there is to it. There's no big inheritance hierarchy, no virtual functions, none of that stuff. Just some class and function templates and a set of conventions to which they all subscribe.

Which leads to another revelation: STL is extensible. You can add your own collections, algorithms, and iterators to the STL family. As long as you follow the STL conventions, the standard STL collections will work with your algorithms and your collections will work with the standard STL algorithms. Of course, your templates won't be part of the standard C++ library, but they'll be built on the same principles and will be just as reusable.

There is much more to the C++ library than I've described here. Before you can use the library effectively, you must learn more about it than I've had room to summarize, and before you can write your own STL-compliant templates, you must learn more about the conventions of the STL. The standard C++ library is far richer than the C library, and the time you take to familiarize yourself with it is time well spent (see also Item E49). Furthermore, the design principles embodied by the library — those of generality, extensibility, customizability, efficiency, and reusability — are well worth learning in their own right. By studying the standard C++ library, you not only increase your knowledge of the ready-made components available for use in your software, you learn how to apply the features of C++ more effectively, and you gain insight into how to design better libraries of your own.