Preface of the book

Designing Components with the C++ STL: A new approach to programming, ISBN 0-201-67488-2 (revised edition)
copyright 2000 and available from Addison Wesley Longman Limited.


The Standard Template Library (STL)

One reason for the success of C++ is that today a large number of libraries is available on the market which greatly facilitate the development of programs, because they offer reliable and well-proven components. A particularly carefully constructed library is the Standard Template Library, which has been developed at Hewlett-Packard by Alexander Stepanov, Meng Lee, and their colleagues. It has been accepted by the ANSI/ISO committee as part of the C++ Standard ISO/IEC 14882.

The emphasis of the STL is on data structures for containers, and the algorithms that work with them. The technical reference document of the STL (Stepanov and Lee,1995) has practically, with some modifications, become a part of the C++ Standard. Both are the basis for the first two parts of this book.

The C++ Standard Library and the STL

The STL does not include the entire C++ Standard Library nor all its templates; it represents, however, the most important and most interesting part. The C++ Standard Library includes several areas:

The emphasized text above constitutes the subject of this book -

in other words, the book does not deal with the historic STL, but with that part of the C++ Standard Library that has originated from the STL. Besides an introduction, the emphasis is on sample applications and the construction of new components on the basis of the STL. Owing to several requirements by the ISO/ANSI standard committee, this part of the C++ Standard Library no longer matches the original STL exactly. Thus, a more precise - albeit too long - title for this book would be Generic algorithms and data structures of the C++ Standard Library - introduction, applications, and construction of new components. The changes affect only some details, but not the concept; therefore the name Standard Template Library and the abbreviation STL have been retained.

The STL as a framework

The STL is an all-purpose library with an emphasis on data structures and algorithms. It makes heavy use of the template mechanism for parameterizing components. The uniform design of the interfaces allows a flexible cooperation of components and also the construction of new components in STL-conforming style. The STL is therefore a universally usable and extendable framework, which offers many advantages with respect to quality, efficiency, and productivity. The successful concept has already been copied, as the Java Generic Library shows.

Aims of this book

The book has two aims. As a technical reference, the reference document mentioned earlier is hardly suited to explain the concepts of the STL. Therefore, the first aim is to present how the STL can be used in a sensible way. Internal details of the STL are described only to the extent needed to understand how it works. However, this book is more than a simple introduction. With the aid of comprehensive examples, the STL is presented as a tool box for the construction of more powerful and sometimes even faster components. These components are more complex data structures and algorithms which can be efficiently implemented by means of the modules contained in the STL. The algorithms are evaluated with respect to their run time behavior relative to the amount of data to be processed (time complexity). However, not only the modules themselves and their combination are of interest, but also the programming techniques employed in the STL and in this book.


This book is intended for all those involved in the development of software in C++, be they system designer, project manager, student of computer science, or programmer. To make the software portable, maintainable, and reusable, it is highly recommended that valid standards are adhered to and thoroughly exploited - otherwise, they would not be needed. The use of prefabricated components such as those of the STL increases both the reliability of the software and the productivity of the developers. The precondition for understanding this book is knowledge of the C++ programming language and its template mechanisms which can be gained by reading good text books on the subject, such as the C++ Primer written by Lippman and Lajoie.

Structure of the book

The book is divided into three parts. Part I is an introduction to the STL and describes its concepts and elements, with the emphasis on iterators and containers. The concept of iterators and containers is essential for the working of the algorithms.

Part II discusses the standard algorithms, where almost every algorithm is illustrated with an example. Because of the large number of algorithms described, it should be viewed as a catalog.

Part III describes applications and extensions. Extensive examples help to show how the components supplied by the STL can be used to design more complex data structures and algorithms and powerful abstract data types.


Not only is the functioning of STL elements described, but for almost every element and all the applications of Part III an executable example is presented that can be run on the reader's computer. This gives the reader a chance to experiment and achieve a deeper understanding.
The examples are available via the Internet, see


The original public domain implementation of the STL by Hewlett-Packard is a little bit different to the C++ standard, since modifications and extensions have been carried out since the integration of the STL. In the meantime also other implementations are available, e.g. from Silicon Graphics or RogueWave. It can be expected that some time after the publication of the C++ standard in September 1998 all compiler producers will supply an STL implementation conforming to the standard, so that differences in various implementations will play only a very marginal role.

In the text, programming issues such as variables, keywords, and program examples can be recognized by this type style. Explanations that interrupt the text of a program are marked as indented comments /* ... */. Names of files are printed in italics and screen displays in slanted characters. A little lightbulb indicates an important hint or tip for programming.

Suggestions and criticism

are more than welcome. If you want to point out errors or make suggestions or critical remarks, you can contact the author either through the publisher or directly:


I have received many suggestions from my colleagues Ulrich Eisenecker (Fachhochschule Heidelberg), Andreas Spillner (Hochschule Bremen), Bernd Owsnicki-Klewe (Fachhochschule Hamburg) and Andreas Scherer (RWTH Aachen), and I am very grateful to them for their critical and thorough review of the manuscript and for their helpful hints and tips. All weaknesses and errors rest solely with the author.