STL Added to C++ Standard

First Commercial Application of Generic Programming Enables True Software Reuse, Seen As Boon To Programmer Productivity

PALO ALTO, Calif., -- Hailed by many in the software industry as a significant programming breakthrough, Hewlett-Packard Company today announced that the Standard Template Library has been accepted as part of the emerging international standard for the C++ programming language. Developed at HP Labs by Alexander Stepanov and Meng Lee, STL provides the first comprehensive set of programming style guidelines and a large collection of generic software building blocks programmers can use to double their productivity and guarantee interoperability of their software components. Demonstrating its support of STL, HP also announced it was placing its implementation of STL in the public domain to help promote STL's wide acceptance.

The guaranteed interoperability offered by STL makes real the much ballyhooed productivity benefits of reusable software components -- reduced development costs, reduced training costs, reduced maintenance costs and greater portability. But the generic programming approach embodied in STL takes these benefits much further by greatly reducing the number of software components programmers need to create in the first place to build a program. And unlike previous attempts at generic programming, STL accomplishes this without incurring any significant run-time performance penalty, running as fast as hand-crafted code.

"We are in great debt to Alex, his co-workers and HP for what may be the single greatest contribution to the C++ standards effort," proclaimed Bjarne Stroustrup, the designer of the C++ programming language, and a researcher at AT&T Bell Laboratories. "The inclusion of STL into the standard library remedies a serious problem by providing for the first time a set of container classes and fundamental algorithms to go with them."

STL was adopted into the draft standard at the July 14, 1994 ANSI/ISO C++ Standards Committee meeting. As with previously adopted proposals for extensions to C++ or its library, it is expected that compiler vendors will soon be incorporating STL into their products.

In support of the growing demand for a working version of STL that programmers can actually use, HP has placed into the public domain the full source code of the STL implementation developed by Stepanov, Lee and Professor David Musser of Rensselaer Polytechnic Institute.

"If HP wants to establish a reputation as a major contributor to C++, I can't imagine how it could have been done more effectively," said Andrew Koenig, the ANSI/ISO C++ project editor and researcher at AT&T Bell Laboratories.

Broad Appeal

Already, STL has attracted the attention of the major object database vendors, who are looking at STL as a way of providing programmers with uniform access to the underlying data structures of their products. STL could be the key to standardizing data structures and algorithms for databases as well as for persistent object stores. Until now, database programmers have had to contend with fairly complex layers of interface code between databases and programming languages like C++, and these interfaces are different for each database.

STL is being looked at closely by businesses who are attracted to its potential cost-saving benefits. Andersen Consulting, for example, is interested in STL for its capabilities as a component library, the added benefit of greatly improved portability and its ability to greatly reduce training costs for the company's programmers.

"STL has more useful features than any of the commercial libraries we use today, but more importantly, because it's part of the C++ standard we can use it to write portable code we can take from project to project, compiler to compiler," said Larry Podmolik, senior technical manager for Andersen Consulting in Chicago. "Our people don't have to learn a new library for every project, and can at last work with a truly standard set of tools."

Others in the software community are equally enthusiastic about STL, seeing it as creating the foundation for a fundamental change in the way software is written.

"Using STL, both as a tool and as a guide for building new tools, is as significant an advance over object-oriented programming as object-oriented programming was over traditional procedural programming," claims P.J. Plauger, author of numerous programming books, including "The Draft Standard C++ Library" published by Prentice-Hall.

STL can play a very important role in higher education computer science courses because it provides a rich source of solid, useful and openly available examples of many of the abstract concepts educators want their students to learn. STL is already being used in the Computer Science Department at Rensselaer Polytechnic Institute in upstate New York by Professor David R. Musser to illustrate notions of generic algorithms, data abstraction, reuse, time complexity bounds and storage management.

"Having STL available means programming assignments can be made much more significant and interesting than if students have to program all the basic data structures and algorithms from scratch," explains Professor Musser.

Generic Advantage

Unlike GUI components or application frameworks, STL provides a consistent library of general-purpose components for common programming tasks that will be portable across platforms. It provides efficient and reliable implementations that work not only on the data structures provided in the library, but also on built-in C++ data types and pointers, and STL eliminates the need to hand craft the low-level algorithms and data structures programmers typically waste their time with. As such, it allows programmers to write code faster and write less code, and the code they do write can be focused more on the problem solution instead of the creation of intermediate tools. STL also can be used as the foundation for building more ambitious libraries.

Unlike the C++ component libraries programmers currently use, STL is the first to focus primarily on algorithms. STL contains a broad set of generic algorithms, in addition to data structures, that perform the most common kinds of data manipulations all programmers use, including searching, sorting, merging, copying and transforming. The STL algorithms have the added benefit of working with all data types, meaning a single algorithm can have very broad utility, yet they have been carefully crafted to run as quickly as hand-coded algorithms.

According to Bjarne Stroustrup, STL "can mean a doubling of productivity on medium-sized projects and more for small, one-off jobs. It provides programmers with a large, systematic, clean, formally sound, comprehensible, elegant and efficient framework that allows C++ programmers to start their work at a noticeably higher level."

Until now, programmers had to create individual versions of each algorithm for all data types and data structures an algorithm would operate with. In large programming efforts, it is not unusual for the number of algorithm variations needed to handle all the data types and data structures they work on to reach into the hundreds or even thousands.

Because of the generic nature of STL, however, the data types do not have to be considered at all. Instead, programmers need create only one version of each algorithm along with a "template" for each required data structure. The number of components, therefore, is reduced dramatically to simply the sum of these two items. In technical terms, this is referred to as the orthogonal decomposition of the component space. The tremendous simplification offered by the generic nature of STL translates into quicker development times, easier debugging and maintenance and greater portability of code.

Iterators to the Rescue

In 1976, the renowned computer scientist Niklaus Wirth postulated:

Algorithms + Data Structures = Programs

Unfortunately, Wirth did not formally define how the algorithms and data structures should work together. STL provides a conceptual framework for how algorithms should access data, and for the first time formally defines the standard data accessing concept as the iterator.

Iterators provide the "glue" between the algorithms and the data structures they work with, called containers. Iterators act like tour guides, enabling the algorithms to move through the information stored in the containers, with different iterators offering different "tours" of the data.

STL defines five categories of iterators, each providing a different way of accessing data in a container. For example, a forward iterator guides the algorithm through a container from beginning to end, like reading the words in a book. A bidirectional iterator lets the algorithm move forward and backward through the container, like the fast forward and rewind functions for searching a VCR tape. A random access iterator can jump around more wildly, like looking up individual words in a dictionary. STL also provides input and output iterators.

What makes STL so powerful is the way iterators hide the actual structure of the data from the algorithms. Because of this, a single generic algorithm can access data in any type of container, eliminating the need to create a specific version of the algorithm to work with each data structure and each type of data that might be in each data structure.

Proper Behavior

In addition to the algorithms, iterators and containers provided by STL, STL also establishes strict programming style guidelines, based on a firm mathematical foundation, for how these components are used and how new ones are created. Programmers who follow these guidelines are guaranteed the overwhelming benefit of interoperability of the software components they create.

"To transform programming from an art to a science, it is necessary to develop a fundamental conceptual taxonomy of software components together with a system of fundamental laws governing their behavior," said Alexander Stepanov, one of the creators of STL and project manager for generic programming at HP Labs. "STL formally defines for the first time what proper behavior is for C++ programmers."

STL provides a fundamentally mathematical way of describing what a container is, what an iterator is, etc. so that a programmer using or extending the library can know exactly what to expect. To be useful as a standard, a library must be extensible (e.g. add new containers, add run-time checked iterators) and policy-free. That is, a programmer must be able to add to the library and be allowed to set policy (e.g. specify how memory is to be allocated, how character strings are compared, etc.). Without firm guidelines for how extension is done, chaos will erupt because each programmer will do it their own, incompatible way.

The fundamental laws developed by Stepanov for STL can be thought of as a programming "etiquette" all C++ programmers are encouraged follow, and although not forced to follow them, there are compelling reasons for programmers to do so. In this regard, Stepanov could become known as the Amy Vanderbilt of computer programming.

As P.J Plauger puts it, "If STL fulfills its promise, it could emerge as one of the most important civilizing influences on the C++ community as a whole."

On-Line STL Information and Availability

Professor Musser also operates a World Wide Web site on the internet providing extensive information on STL, including a hypermedia guide for all STL generic algorithms. Brief overviews of containers and other kinds of STL components are offered, and the ANSI/ISO specification document and some related research materials are provided, too.

The Standard Template Library home page can be reached at:

http://www.cs.rpi.edu/~musser/stl.html

and is supported, in part, by grants from Hewlett-Packard and the National Science Foundation.

The free, public domain Hewlett-Packard implementation of STL may be obtained by anonymous ftp from butler.hpl.hp.com in directory stl, or from ftp.cs.rpi.edu in directory stl.

Hewlett-Packard Company

Hewlett-Packard Company is an international manufacturer of measurement and computation products and systems recognized for excellence in quality and support. The company's products and services are used in industry, business, engineering, science, medicine and education in approximately 110 countries. HP has 96,600 employees and had revenue of $20.3 billion in its 1993 fiscal year.

# # #