Standard Template Library Programmer's Guide

This is a minor release. It consists only of bug fixes (the most important ones are in rope), small changes to reflect changes in the Final Draft International Standard (FDIS), and performance improvements in single-element insertion into containers.

• Major reorganization of header files. Headers now have the names described in the draft C++ standard. (Old header names are provided as well for backward compatibility.) The new-style headers declare their contents in namespace std; the old-style headers do too, but they import those declarations into the global namespace with using declarations. So, for example, #include is roughly equivalent to #include followed by the declaration using std::vector;.

Note that namespace std is only enabled for compilers whose support for namespaces is sufficient; this is controlled by the header .

• Bug fixes, and minor changes for standard conformance.

• Bug fixes, most importantly in rope.

• New version of reverse_iterator that takes only a single template parameter, as described in the draft standard. (This relies on iterator_traits, so you can only use the new version of reverse_iterator if your compiler supports partial specialization.)

• New algorithms: find_first_of, search_n, find_end

• Changed the iterator tag classes so that they form an inheritance hierarchy.

• Added the -> operator to all predefined iterators (except for output iterators).

• Bug fixes, most importantly in rope and deque.

• New feature: function object adaptors for member functions. This is a family of classes: mem_fun_t, mem_fun_ref_t, mem_fun1_t, mem_fun1_ref_t.

Bug fixes only, no new features.

This is a major release, with many new features. Here are some of the most important.

• Exception safety. All STL components are now exception safe.

• New container class: rope. A scalable string representation.

• New container class: slist. Singly linked lists.

• Member templates. If your compiler supports member templates, then you will be able to use the fully general form of containers' copy constructors and insert member functions.

• New mechanism for accessing iterators' associated type information: iterator_traits. (Note: you can only use iterator_traits if your compiler supports "partial specialization".) The algorithms count, count_if, and distance have been rewritten in terms of iterator_traits.

• Reimplementation of deque. deque has been completely rewritten, for higher performance.

• type_traits mechanism, which allows omission of null constructor and destructor calls.

• New temporary_buffer class. This was partially motivated by exception safety, but it is also more convenient and more efficient than the old get_temporary_buffer and return_temporary_buffer functions.

• New allocator, debug_alloc, which is useful for verifying the correctness of memory allocation and deallocation.

• New algorithms: copy_n, lexicographical_compare_3way, power, uninitialized_copy_n.

• Greater portability. The SGI STL can now be compiled using Microsoft Visual C++ 5.0, and Borland C++ 5.02; it should not be difficult to port it to any other compiler that has good support for templates. (Specifically, any compiler that has default template parameters.) Most compiler-specific code is isolated in the file stl_config.h.

• The Matrix Template Libraryat Notre Dame. A high-performance generic linear algebra library.

• The Rensselaer STL siteby David Musser

• The Renssalaer STL online reference The STL tutorial at Technical University Vienna Port of the SGI STL to other compilers, by Boris Fomitchev.

• Port of the SGI STL to Microsoft Windows CE compilers, by Giuseppe Govi.

• The STL Newbie Guideby Mumit Khan

• A Tiny STL Primerby David Harvey

• A Very Modest STL Tutorialby Jak Kirman

• The Dinkum Standard Template Library Referenceby P. J. Plauger.

• Overview of the STLby G. Bowden Wise

• Ian Burrell's STL page

• Cay Horstmann's "Safe STL"

• The Binder Library. A versatile function argument binding mechanism that interoperates with STL algorithms.

• The STL Resource Listby Warren Young

• The Standard Template Library Overviewby Rob Kremer

• Alexander Stepanov's Byte Magazine's article

• Dr. Dobb's Journal interview with Alexander Stepanov

• STL for C Programmers, by Leen Ammeraal. John Wiley, 1996. ISBN 0-471-97181-2.

• Generic Programming and the STL, by Matthew Austern. Addison-Wesley, 1998. ISBN 0-201-30956-4.

• Designing Components with the C STL, by Ulrich Breymann. Addison Wesley Longman, 1998. ISBN 0-201-17816-8.

• Data Structures in C Using the Standard Template Library, by Timothy Budd. Addison-Wesley, 1997.

• The STL Primer, by Graham Glass and Brett Schuchert. Prentice-Hall, 1996. ISBN 0134549767

• The C Standard Library - A Tutorial and Reference, by Nicolai Josuttis. Addison Wesley Longman, 1999. ISBN 0-201-37926-0. (English translation of Die CStandardbibliothek.)

• STL Tutorial and Reference Guide, by David Musser and Atul Saini. Addison-Wesley, 1996. ISBN 0-201-63398-1.

• C Programmer's Guide to the Standard Template Library, by Mark Nelson. IDG Books, 1995. ISBN 1-56884-314-3. (No longer in print.)

• The Standard Template Library, by P. J. Plauger, Alexander Stepanov, Meng Lee, and David Musser. Prentice-Hall. ISBN 0-13-437633-1. (forthcoming)

• Using the STL, by Robert Robson. Springer-Verlag, 1998.

• STL Programming from the Ground Up, by Herbert Schildt. Osborne McGraw-Hill, 1999.

We welcome additions to this list. Please send suggestions to stl@sgi.com.

This interview appeared in the March 1995 issue of Dr. Dobb's Journal, and is reprinted with permission.

Tell us something about your long-term interest in generic programming.

I started thinking about generic programming in the late 70s when I observed that some algorithms depended not on some particular implementation of a data structure but only on a few fundamental semantic properties of the structure. I started going through many different algorithms, and I found that most algorithms can be abstracted away from a particular implementation in such a way that efficiency is not lost. Efficiency is a fundamental concern of mine. It is silly to abstract an algorithm in such a way that when you instantiate it back it becomes inefficient.

At that time I thought that the right way of doing this kind of research was to develop a programming language, which is what I started doing with two of my friends, Deepak Kapur, who at present is a professor at State University of New York, Albany, and David Musser, professor at Rensselaer Polytechnic Institute. At that time the three of us worked at the General Electric Research Center at Schenectady, NY. We started working on a language called Tecton, which would allow people to describe algorithms associated with what we called generic structures, which is just a collection of formal types and properties of these types. Sort of mathematical stuff. We realized that one can define an algebra of operations on these structures, you can refine them, you can enrich them, and do all sorts of things.