© 1996 David Harvey. All rights reserved.
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
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.
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.
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);
...
};
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:
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().
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};
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"));
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)
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/.
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 implmenetation.
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
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.
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