Presentation on BTL - January 1998

Implementation

Templates

Parameterized classes and functions e.g.template <class T> class list {...};

The Standard Template Library

Included in the proposed draft ANSI standard for C++.
A library containing, amongst other things, containers and generic algorithms e.g. list, vector, map, find, sort
Uses iterators to 'glue' containers and algorithm components together

Iterators

A data structure, or container, component provides a certain type of iterator that can be used to navigate through its individual data elements. Examples of STL iterator types are forward that allow sequential traversal and random access that also allow direct access. An algorithm component often takes two iterators as input which indicate a range of elements within a container (see figure).

Compatible containers and algorithms can be combined in an orthogonal manner. To be compatible particular algorithm a container with a must provide iterators that allows that algorithm to navigate through a container in the way that it needs. The simpler the demands made by an algorithm upon its input parameters, the more generic it is. The greater the functionality of the iterators that a container provides, the greater the range of algorithms that can operate on it.

// Construct a STL vector
vector<float> container;

// Put some data in it.
container.push_back(8.98);
container.push_back(-7.8);
...

// Construct iterators that can be used to navigate through
// the container
vector<float>::iterator
begin = container.begin(),
end = container.end();

// Sort the elements using the STL generic sort component
sort(begin,end);

Ilustration of how iterators form the interface between container and generic algorithm components