1 Introduction


Motivation. In the late 70s Alexander Stepanov first observed that some algorithms do not depend on some particular implementation of a data structure but only on a few fundamental semantic properties of the structure. Such properties can be - for example - the ability, to get from one element of the data structure to the next, and to be able to step through the elements from the beginning to the end of the structure. For a sort algorithm it is not essential if the elements to be sorted are stored in an array, a linked list, etc. Stepanov examined a number of algorithms and found that most of them could be abstracted away from a particular implementation and that this abstraction can be done in a way that efficiency is not lost. Efficiency is an essential point that Stepanov emphasizes on, he is convinced that no one would use an algorithm that becomes inefficient by instantiating it back.

The STL history. Stepanovs insight - which hasn't had much influence on software development so far - will lead to a new programming paradigm in future - so the hope of its discoverer. In 1985 Stepanov developed a generic Ada library and was asked, if he could do this in C++ as well. But in 1987 templates (see section 2.3) - an essential technique for this style of programming - weren't implemented in C++ and so his work was delayed. In 1988 Stepanov moved to the HP Labs and 1992 he was appointed as manager of an algorithm project. Within this project, Alexander Stepanov and Meng Lee wrote a huge library - the Standard Template Library (STL) - with the intention to show that one can have algorithms defined as generically as possible without losing efficiency.

STL and the ANSI/ISO C++ Draft Standard. The importance of STL is not only founded in its creation or existence, STL was adopted into the draft standard at the July 14, 1994 ANSI/ISO C++ Standards Committee meeting. That means that if not happened till now anyway, compiler vendors will soon be incorporating STL into their products. The broad availability of STL and the generic programming idea give this new programming paradigm the chance to positively influence software development - thus allow programmers to write code faster and to write less lines of code while focusing more on problem solution instead of writing low-level algorithms and data structures.

Document arrangement. In section 2 STL-required C++ basics are taught, especially classes, function object design and templates - also called parametrized types. In section 3 STL is overviewed and the key concepts are explained. Section 4 teaches STL step-by-step. Section 5 deals with STL components not explained in section 4. Section 6 containes copyright notices and section 7 shows the literature used.

Continue with section 2

Back to index


Johannes Weidl (J.Weidl@infosys.tuwien.ac.at) - Apr 16, 1996