Papers on Smart Pointers in C++ and Evolutionary Delivery and a more detailed consideration of idiomatic use of the STL are also available at this site. For more information on the author, please take a look at my software and home pages. 

A Tiny STL Primer

David Harvey

© 1996 David Harvey. All rights reserved.
Revised 27/6/1997 (format)
Revised 30/11/1997 (new links)
Contact
Home: http://www.davethehat.com/

This primer formed part of the workbook for a presentation at the Object Technology 96 Conference, held at Oxford, England, March 25-27th 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.
    •  For more extensive information on the STL see the references at the end of this paper.

    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

    The SL template classes provide first and foremost a basic selection of containers: 
    template <size_t N> class bitset;
template <class T> class deque;
template <class T> class list;
template <class T> class vector;
    The library also provides associative containers: 
    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
    These declarations do not show the default template parameters which apply to these templates. Each container also takes an Allocator class, and in addition the associative containers are parameterised with a function class for internal ordering of the container. As default template parameters are not yet commonly implemented, current SL implementations compromise in their handling of these.

    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

    Each class offers member functions performing basic operations such as creation and basic element access. Some of the members of vector are: 
    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

    Other operations on vector require some notion of a position within the vector. Traditionally in C and C++ this is represented by a pointer: the SL abstracts the notion of a pointer into the generic concept of an iterator. These are best illustrated by example. First of all, with arrays and pointers: 
    int v[10];
//... fill v;
int* i = v;
while (i != v + 10)
        cout << *i++;
    The SL code for this is surprisingly similar: 
    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.
    •  Some members of vector which use or return iterators are: 
    template <class T> class vector {
iterator begin();
iterator end();
iterator insert(iterator position, const T& x);
...
};
    These can be used together to place elements in a vector: 
    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);
}
    Here are some equivalent members of the map container class. 
    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);
...
};
    The value of a map iterator (returned by dereferencing it using operator*()) is given by the typedef value_type, holding the key and its associated value. The overloaded operator[] allows associative look-up using an instance of the key type. Beware: it will create an element in the map if one doesn't exist. The insert() member returns a pair, the second element of which is true if the object didn't already exist in the map. If find() fails to locate an element corresponding to the passed key, it returns an iterator equal to end().

    Algorithms

    Container member functions and iterators between them provide the fundamental means for accessing elements of containers. More powerful operations are implemented using standard library algorithms. These are template functions parameterised on iterators and often also functions. More detailed discussion of these will follow: for now, some examples: 
    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

    The SL provides container adaptors, some which change the behaviour of an underlying container, some which allow a non-SL data structure to be used in SL algorithms.

    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));
    There are corresponding adaptors front_insert_iterator and insert_iterator to deal with building sequential containers from the front, or through insertion into containers such as set and map.

    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

    STL++ - Modena Software Inc.

    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

    ISO Working Paper for Draft Proposed International Standard for Information Systems-Programming Language C++, Doc No: X3J16/95-0087 WG21/N0687, April 1995

    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

    There are several WWW and other sites devoted to the STL These include

    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

    Expect to see a flurry of books on the STL and SL as the C++ standardisation effort nears its completion. Three titles currently available are

    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

    J. Lajoie, 'Templates:-New and improved, like your favorite detergent :-)', C++ Report 6/iv, May 1994

    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