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.
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 STLiterators.
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.
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 wayby 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 |
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.