Borland Online And The Cobb Group Present:


April, 1995 - Vol. 2 No. 4

Standard C++ - Standard Template Library overview

In the lead article, Using Standard Template Library (STL) containers and iterators we compare the STL with the Borland International Data Structures (BIDS) library. However, the capability of the STL goes far beyond simply replacing the BIDS library. It provides a thorough set of tools for manipulating common data structures in a C++ program.

There are three major parts of the STL: containers, iterators, and algorithms. Here, we'll look at how these components interact. In future issues, we'll take a closer look at the individual pieces of the STL.

Contain yourself

At the heart of the STL are the container classes. In the STL, containers have two responsibilities: providing a standard interface for manipulating their elements and generating iterators.

For the most part, the standard interface that the container classes provide is generic. That is, it's not specific to just one type of container. Table A lists the member functions that are common to the different types of containers. (For clarity, we're not showing the function arguments.) Table A: Functions common to STL containers
Container
function
Action
begin( ) Returns an iterator to the first item in the container
end( ) Returns an iterator that's one element past the end of the container
rbegin( ) Returns a reverse iterator to the last item in the container
rend( ) Returns a reverse iterator that's one element ahead of the beginning of the container
insert( ) Inserts an element into a container at a specific iterator's position
insert( ) Inserts a range of elements into a container beginning at a specific iterator's position and ending at another iterator's position
push_back( ) Inserts an item at the end of the container
pop_back( ) Destroys and removes the last item in the container
swap( ) Exchanges two items in the container
size( ) Returns the number of items in the container
max_size( ) Returns the maximum possible size for this container
empty( ) Returns 1 if the container is empty; returns zero otherwise
erase( ) Destroys an item in the container
erase( ) Destroys a range of elements in a container beginning at a specific iterator's position and ending at another iterator's position

It's possible to manipulate the elements in a container using the direct interface these functions provide. However, the STL doesn't really display its power until you begin to manipulate the elements using the second component of the STL­­iterators.

Iterator, information

The documentation that comes with the STL (in the form of a Postscript printer file) describes iterators as a type of pointer. In fact, the vector class includes a typedef statement that defines its iterators as simple pointers.

For the other container classes, the STL defines nested iterator classes that maintain enough information about their companion container to allow them to navigate through the container appropriately. However, even these more sophisticated iterators define operator *( ), which allows you to use iterators as you would a pointer, including de-referencing them to access the element they address.

In addition to simulating simple pointer de-referencing behavior, all of the iterator classes provide a basic set of operators you can use to traverse a container with an iterator or to compare relative positions of two iterators within a given container. Table B lists the operators that all iterator classes define.

Table B: Operators all iterators must define.
Operator or
function
Action
operator ==( ) Tests equality between two iterators of the same type
operator !=( ) Tests inequality between two iterators of the same type
operator *( ) De-references by using pointer syntax
operator ++( ) Points to the next element via a pre-increment iterator
operator ++(int) Points to the next element via a post-increment iterator

As with the containers, you can use these operators to manipulate one or more iterators and, thereby, manipulate the contents of the associated container. However, there is another level at which the STL operates. To perform complex operations on a given container, you can pass iterators for that container to one of the STL template functions or algorithms.

Algorithm section

The final component of the STL is actually the easiest to explain. If you imagine that iterators are simply pointers (which, you'll recall, is literally true for iterators of a vector) and you consider that each of the STL algorithms will work correctly for these pointers, you'll soon realize that the algorithms use iterators in a fairly simple way­­by using standard pointer syntax.

For example, when you write the following program:

#include "\stl\algobase.h"
#include <iostream.h>
int main( ) { char name[] = "Borland C++ Developer's Journal"; sort(&name[0], &name[31]); cout << name << endl; return 0; }

you'll see the following output

   '++BCDJaaddeeelllnnoooprrrsuv

As you can tell, the sort( ) function will correctly sort the ASCII values of the characters and store the results back in the original container.

Similarly, if you replace the sort( ) function with

rotate(&name[0], &name[15], &name[31]);

you'll see

Developer's JournalBorland C++

This means you won't have to worry about whether a given function is available for a particular container. If the container can supply iterators to its elements, you can call any of the algorithm template functions the STL provides. Table C lists some of the STL algorithms.

Table C: STL algorithms
Algorithm Action
for_each( ) Calls a function for each element in the container
find( ) Returns an iterator that points to the first element that matches the test argument
count( ) Returns (via a reference argument) the number of elements between two iterators that are equal to a certain value
mismatch( ) Returns two iterators (from different containers) that address the first elements that don't match in the containers
equal( ) Returns 1 if the ranges specified by two iterators match exactly.
search( ) Returns an iterator to the first element of a sub-range in a container
copy( ) Copies a range of elements to a container addressed by an output iterator
copy_backward( ) Reverse-copies a range of elements to a container addressed by an output iterator
swap( ) Exchanges the values in two variables
iter_swap( ) Exchanges the values addressed by two iterators
swap_ranges( ) Exchanges a series of values between two iterators with a corresponding size range addressed by a third iterator
transform( ) Applies an operation to each element in a range specified by two iterators and places the results in a container specified by an output iterator
replace( ) Replaces each element in the range specified by two iterators with a new element
fill( ) Assigns a specified value to each element in a range specified by two iterators
remove( ) Destroys and removes each element in the range specified by two iterators
unique( ) Removes duplicate, consecutive elements from a range specified by two iterators

Return to the Borland C++ Developer's Journal index

Subscribe to the Borland C++ Developer's Journal


Copyright (c) 1996 The Cobb Group, a division of Ziff-Davis Publishing Company. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of Ziff-Davis Publishing Company is prohibited. The Cobb Group and The Cobb Group logo are trademarks of Ziff-Davis Publishing Company.