This primer formed part of the workbook for a presentation at the Object Technology 96 Conference, held at Oxford, England, March 25-27^th 1996.

The STL is an innovative library of templated container, iterator and algorithm classes which bring true generic programming styles into the reach of the C++ language. The core idioms in the library itself

• allow straightforward implementation of software components in economic and expressive ways;
• generate remarkable levels of source code reuse;
• promote new and powerful programming techniques.

The STL has been incorporated in the ANSI draft specification for the C++ language, where it forms the containers, iterators and algorithms parts of the standard library. In the remainder of this primer, I will therefore refer to the SL template classes rather than STL, to characterise this library. 

Basics

template <size_t N> class bitset;
template <class T> class deque;
template <class T> class list;
template <class T> class vector;

template <class Key> class set;
template <class Key> 
class multiset;         // equivalent of bag
template <class Key, class T> class map;
template <class Key, class T> 
class multimap;         // possibly several values per key

The classes highlighted in bold will serve as the focus of our attention throughout the workshop: most of what will be covered applies to the others also.

Container members

template <class T> class vector {
vector::vector();
vector::vector(size_type n, const T& value = T());      

size_type size();       // size_type is a typedef for size_t
size_type max_size();

T& operator[](size_type n);
void push_back(const T& x);
...
};

Iterators

int v[10];
//... fill v;
int* i = v;
while (i != v + 10)
        cout << *i++;

vector<int> v;
//... fill v
vector<int>::iterator i = v.begin();    // 1
while (i != v.end())                    // 2
        cout << *i++;                   // 3

Important principles:

• Iterators can be used to move sequentially through containers
• These iterators behave like pointers - in fact, think of iterators as generalised pointers (3 above)
• Iterator classes are typedef-ed in the container classes themselves (2)
• A container's start and end (in fact, 'one past the end') are given by begin() and end() members;
• There are different classes of iterator - input, output, forward, reverse, bidirectional, random access - which correspond to increasingly flexible usages. For now, you won't need to worry about the differences between them.

template <class T> class vector {
iterator begin();
iterator end();
iterator insert(iterator position, const T& x);
...
};

vector<int> va, vb, vc;
for (int i = 1; i < 10; i ++)
{
        va.insert(va.end(), i * i);
        vb.push_back(i * i);
        vc.insert(vc.begin(), i * i);
}

template <class Key, class T> class map {
typedef Key key_type;
typedef pair<const Key, T> value_type;

T& operator[](const key_type& x);
pair<iterator,bool> insert(const value_type& x);
iterator find(const key_type& x);
...
};

Algorithms

vector<int> v;
//... fill v
// Sort the vector
sort(v.begin(), v.end());

// Print each element of a vector of integers
void print (int i) {cout << i;}
for_each(v.begin(), v.end(), print);

// Copy the vector
vector<int> v2(v.size())
copy(v.begin(), v.end(), v2.begin());

// Transform v2 - square each element
int square(int i) { return i * i; }
transform(v2.begin(),v2.end(), v2.begin(), square};

Adaptors

In the example illustrating the copy function, it was important to create the destination vector with enough room to hold each copied element as it is assigned. To make the destination grow with each assigned element, we can use a back_insert_iterator instead, which uses push_back() rather than assignment to place elements in the destination:

// Copy the vector using an iterator adaptor
vector<int> v2;
copy(v.begin(), v.end(), back_insert_iterator<vector<int> >(v2));

Further adaptors allow C++ stream library objects to act as iterators. Here is a single call to copy which copies strings from cin to cout, separating each in the output with a newline:

copy(istream_iterator<string, ptrdiff_t>(cin),  // create on cin
        istream_iterator<string, ptrdiff_t>(),  // stream end()
        ostream_iterator<string>(cout, "\n"));

SL/STL resources

STL Implementations

The first commercial implementation.

STL<Toolkit> - ObjectSpace Inc.

Available for many platforms, optimised and improved. Includes several non-STL extensions (clearly marked as such), all geared towards ease of use and flexibility.

Rogue Wave Tools.h++ v7

Silicon Graphics STL

Available free (se below)

HP Reference Implementation

Available free (see below)

C++ Draft Standard

Available in postscript and acrobat formats from ftp://research.att.com/dist/c++std/WP/, UK mirror at ftp://ftp.maths.warwick.ac.uk:/pub/c++/std/WP. HTML and ASCII versions are online at http://www.cygnus.com/.

SL/STL Online

ftp://butler.hpl.hp.com/stl/
Anonymous FTP for HP reference implementation. Also includes STL-style implementations of hashed collections, STL-related papers and documents, and sample programs from ObjectSpace's STL<Toolkit>.

http://www.cs.rpi.edu/~musser/stl.html
David Musser's STL home page at Rennslaer Polytechnic Institute. Includes on-line version of STL definition document and many examples. Also an FTP link with STL sources and further examples (including code from the Musser/Saini book mentioned below).

http://www.sgi.com/Technology/STL/
Silicon Graphics STL implementation. An excellent new (Jan 1997) site with good documentation, links, and a downloadable implementation.

http://www.metabyte.com/~fbp/stl/
STL Adaptation Page: a highly useful site which provides fixed-up versions of the SGI STL for several compilers (including MS, Borland).

http://www.xraylith.wisc.edu/~khan/software/stl/STL.newbie.html
Mumit Kahn's newbie guide, with notes on using STL collected over a period of time.

http://www.cs.brown.edu/people/jak/programming/stl-tutorial/home.html
Simple tutorial by Jak Kirman.

http://www-leland.stanford.edu/~iburrell/cpp/stl.html
Another STL home page, with links to several other sites.

http://weber.u.washington.edu/~bytewave/bytewave_stl.html
A collection of links to STL sites

http://www.cs.bham.ac.uk/~jdm/cpp.html
Extensive list of C++ links including several links to STL sites

Books

Graham Glass/Brett Schuchert: The STL <Primer>

Prentice-Hall 1995, ISBN 0-13-454976-7, 329pp

Glass is the founder of ObjectSpace, and both authors were instrumental in that company's implementation of the STL. The first off the blocks, though with some 100 pages of tutorial and 200 pages of reference you might feel it owes rather too large a debt to the STL<Toolkit> reference manual.

Mark Nelson: The C++ Programmer's Guide to the Standard Template Library

IDG 1996, ISBN 1-56884-314-3, 874pp

Written by another library guru (this time from Greenleaf Software Inc). A heavyweight book, with a great deal more supplementary material than Glass/Schuchert.

David R. Musser/Atul Saini: STL Tutorial and Reference Guide

Addison Wesley 1996, ISBN 0-201-63398-1, 432pp

Musser was an early collaborator with Alex Stepanov, and played a large part in bringing the STL into the C++ standard. Saini is President and CEO of Modena Software Inc., responsible for STL++. Between them they have produced what will probably end up as the standard book on the STL.

The SL is covered in some detail in

Bjarne Stroustrup: The C++ Programming Language (3rd edition)

Addison Wesley 1997, ISBN 0-201-88954-4, 910pp

Stroustrup maintains lists of errata in the various printings of the book.

Articles

A. Koenig, 'Generic input iterators', JOOP 9/i, March-April 1996

N. Myers, 'A new and useful template technique: "Traits"', C++ Report 7/v, June 1995

B. Stroustrup, 'Making a vector fit for a standard', C++ Report, October 1994

T. Veldhuizen, 'Using C++ template metaprograms', C++ Report 7/iv, May 1995

T. Veldhuizen, 'Expression Templates', C++ Report 7/v, June 1995

J. Vilot, 'An Introduction to the Standard Template Library', C++ Report 6/viii, October 1994