implementation in C++, with particular emphasis on the relationship of these data structures to those in the
C++ Standard Template Library (STL). To that end, most chapters follow the same pattern:
1. A description of the data structure itself.
2. A description of the relevant STL interface, but only those functions that are absolutely necessary for
an understanding of the structure.
3. One or more examples of how the data structure might be used in practice. These examples are in the
form of algorithms, rather than C++ code.
4. A complete implementation of the data structure, based on the described STL interface. To avoid
confusion with the types defined in the STL, I name my versions with an initial capital letter (e.g.,
Vector rather than vector).
The implementations are not necessarily the best, nor do they adhere to “standard” STL
implementation techniques. The focus here is on the data structure itself, not on the STL. The code also
follows the “minimalist” approach: just enough to help you understand what’s “under the hood.” New
C++ concepts are introduced only when absolutely necessary.
The STL makes great use of all the facilities of the C++ programming language, most of which are not
necessary for an understanding of the underlying data structures. For example, the member function size
returns an unsigned value of type size_type, which is usually the same as another unsigned type called
size_t (don’t ask). In this book, I use int for all integral types, whether signed or not. Unless a data
structure contains a huge number of elements, the difference between signed and unsigned integer types
isn’t relevant, and can only complicate explanations. In keeping with the minimalist approach, no
advanced features of the language are used when a more basic one will do.