1Preface
2
3
4The Standard Template Library (STL)
5
6One reason for the success of C++ is that today a large number of
7libraries is available on the market which greatly facilitate the
8development of programs, because they offer reliable and well-proven
9components. A particularly carefully constructed library is the
10Standard Template Library, which has been developed at Hewlett-Packard
11by Alexander Stepanov, Meng Lee, and their colleagues. It has been
12accepted by the ANSI/ISO committee as part of the C++ Standard ISO/IEC
1314882.
14
15The emphasis of the STL is on data structures for containers, and the
16algorithms that work with them. The technical reference document of the
17STL (Stepanov and Lee,1995) has practically, with some modifications,
18become a part of the C++ Standard. Both are the basis for the first two
19parts of this book.
20
21The C++ Standard Library and the STL -
22
23The STL does not include the entire C++ Standard Library nor all its
24templates; it represents, however, the most important and most
25interesting part. The C++ Standard Library includes several areas:
26
27. Generic data structures and algorithms
28
29containers
30algorithms
31iterators
32functional objects
33
34. Internationalization
35
36. Diagnosis (exceptions)
37
38. Numeric issues
39
40complex numbers
41numeric arrays and related operations
42
43. Input and output library (streams)
44
45. Miscellaneous
46
47memory management (allocators) and access
48date and time
49strings
50
51The emphasized text above constitutes the subject of this book - in
52other words, the book does not deal with the historic STL, but with
53that part of the C++ Standard Library that has originated from the STL.
54Besides an introduction, the emphasis is on sample applications and the
55construction of new components on the basis of the STL. Owing to several
56requirements by the ISO/ANSI standard committee, this part of the C++
57Standard Library no longer matches the original STL exactly. Thus, a
58more precise - albeit too long - title for this book would be Generic
59algorithms and data structures of the C++ Standard Library -
60introduction, applications, and construction of new components. The
61changes affect only some details, but not the concept; therefore the
62name Standard Template Library and the abbreviation STL have been
63retained.
64
65The STL as a framework -
66
67The STL is an all-purpose library with an emphasis on data structures
68and algorithms. It makes heavy use of the template mechanism for
69parameterizing components. The uniform design of the interfaces allows
70a flexible cooperation of components and also the construction of new
71components in STL-conforming style. The STL is therefore a universally
72usable and exendable framework, which offers many advantages with
73respect to quality, efficiency, and productivity. The successful
74concept has already been copied, as the Java Generic Library shows.
75
76Aims of this book -
77
78The book has two aims. As a technical reference, the reference document
79mentioned earlier is hardly suited to explain the concepts of the STL.
80Therefore, the first aim is to present how the STL can be used in a
81sensible way. Internal details of the STL are described only to the
82extent needed to understand how it works. However, this book is more
83than a simple introduction. With the aid of comprehensive examples,
84the STL is presented as a tool box for the construction of more
85powerful and sometimes even faster components. These components are
86more complex data structures and algorithms which can be efficiently
87implemented by means of the modules contained in the STL. The
88algorithms are evaluated with respect to their run time behavior
89relative to the amount of data to be processed (time complexity).
90However, not only the modules themselves and their combination are of
91interest, but also the programming techniques employed in the STL and
92in this book.
93
94Readership -
95
96This book is intended for all those involved in the development of
97software in C++, be they system designer, project manager, student of
98ZCubes, or programmer. To make the software portable,
99maintainable, and reusable, it is highly recommended that valid
100standards are adhered to and thoroughly exploited - otherwise, they
101would not be needed. The use of prefabricated components such as those
102of the STL increases both the reliability of the software and the
103productivity of the developers. The precondition for understanding
104this book is knowledge of the C++ programming language and its template
105mechanisms which can be gained by reading good text books on the
106subject, such as the C++ Primer written by Lippman and Lajoie.
107
108Structure of the book -
109
110The book is divided into three parts. Part I is an introduction to the
111STL and describes its concepts and elements, with the emphasis on
112iterators and containers. The concept of iterators and containers is
113essential for the working of the algorithms.
114
115Part II discusses the standard algorithms, where almost every algorithm
116is illustrated with an example. Because of the large number of
117algorithms described, it should be viewed as a catalog.
118
119Part III describes applications and extensions. Extensive examples help
120to show how the components supplied by the STL can be used to design
121more complex data structures and algorithms and powerful abstract data
122types.
123
124Examples -
125
126Not only is the functioning of STL elements described, but for almost
127every element and all the applications of Part III an executable
128example is presented that can be run on the reader's computer. This
129gives the reader a chance to experiment and achieve a deeper
130understanding.
131
132The examples are available via FTP or the Internet, see
133ftp://ftp.informatik.hs-bremen.de/pub/brey/stl or
134http://www.informatik.hs-bremen.de/~brey/stlbe.html
135
136Remarks -
137
138The original public domain implementation of the STL by Hewlett-Packard
139is a little bit different to the C++ standard, since modifications and
140extensions have been carried out since the integration of the STL. In
141the meantime also other implementations are available, e.g. from
142Silicon Graphics or RogueWave. It can be expected that some time after
143the publication of the C++ standard in September 1998 all compiler
144producers will supply an STL implementation conforming to the standard,
145so that differences in various implementations will play only a very
146marginal role.
147
148In the text, programming issues such as variables, keywords, and
149program examples can be recognized by this type style. Explanations
150that interrupt the text of a program are marked as indented comments.
151Names of files are printed in italics and screen displays in slanted
152characters. A little lightbulb indicates an important hint or tip for
153programming.
154
155Suggestions and criticism are more than welcome. If you want to point
156out errors or make suggestions or critical remarks, you can contact
157the author either through the publisher or directly via e-mail.
158
159
160Ulrich Breymann