One practical limitation of C++ has been the lack of a common set of generic data structures, called containers, for use in programs. C++ programmers have had to ``roll their own'' data structures whenever they needed them. Thousands of C++ programmers everywhere have been re-inventing the wheel time and time again. Those of you who have written a generic data structure, such as a binary tree, know how tedious and error-prone this undertaking can be.
The reason for this shortcoming is that, until recently, C++ lacked sufficient language mechanisms to enable developers to implement container classes that were type safe, flexible, and efficient for general use. As a result, Stroustrup and others of the Extensions Working Group (WG) of the ANSI C++ Standards Committee, embarked on a project to incorporate templates into the C++ language [6]. The first official proposal for templates appeared in the ARM [1] in 1990 and templates are now an official language construct as outlined in the April 1995 ANSI draft [2]. The Extensions WG was also responsible for the incorporation of exceptions into the language [4].
Without templates, there were only two approaches for creating generic components in C++: implement the data structure as a C struct with void pointers to hold the data; or, implement the data structure using a C++ class hierarchy and use inheritance and virtual functions. However, neither of these approaches could provide the efficiency required for a component in a standard library that would be put to general use.
The Standard Template Library (STL) provides C++ programmers with a library of common data structures -- linked lists, vectors, deques, sets, and maps -- and a set of fundamental algorithms that operate on them. C++ programmers no longer need to implement these basic data structures and can be assured that the data structures provided by the STL perform efficiently and correctly.
The STL would not have been possible without the use of C++ templates; class and function templates are used throughout the STL. Templates provide not only the efficiency needed for a generic component library, but also make the library extensible. Templates allow the STL to work with built-in types and user-defined types in a seamless way.
Templates are still a recent addition to C++ and many compiler vendors do not provide all of the features as suggested in the April 1995 ANSI draft. The STL depends heavily on many of these advanced features and, in some cases, relies on workarounds to accommodate the current generation of compilers.
There are six components in the STL organization. Three components, in particular, can be considered the core components of the library:
An STL data structure or container, unlike traditional ones, does not contain many member functions. STL containers contain a minimal set of operations for creating, copying, and destroying the container along with operations for adding and removing elements. You will not find container member functions for examining the elements in a container or sorting them. Instead, algorithms have been decoupled from the container and can only interact with a container via traversal by an iterator. This orthogonal component structure is illustrated in Figure 1.
Figure 1: Containers, algorithms, and iterators form an
orthogonal
component space in the STL.
This orthogonal structure is what brings the STL its power, flexibility, and extensibility. Developers that implement new algorithms utilizing one of the STL iterators are guaranteed that their algorithms will work with existing container types as well as those that have not yet been developed.
The remaining three components of the STL are also fundamental to the library and contribute to its flexibility and portability:
Containers are data structures that manage a collection of elements and are responsible for the allocation and deallocation of those elements. Containers typically have constructors and destructors along with operations for inserting and deleting elements.
Elements are stored in containers as whole objects; no pointers are used to access the elements in a container. This results in containers that are type safe and efficient. The STL provides two categories of containers:
Sequence containers store elements in sequential order. These containers group a finite set of elements in a linear arrangement. The STL includes class templates for vectors, lists, and deques.
Here is an example of a vector of ints:
vector<int> l;
for (int i=0; i < 100; i++)
l.push_back (i);
Associative containers store elements based on a key value. Implemented as red-black trees, they provide efficient retrieval of elements based on their key. The STL provides class templates for maps, sets, multimaps, and multisets. maps and multimaps allow arbitrary data to be associated with each key. Also, maps and sets only allow elements with unique keys, whereas multimaps and multisets may contain elements with duplicate keys. Associative arrays are easily created using maps:
map<string,string,less<string> > cap; cap["Arkansas"]="Little Rock"; cap["New York"]="Albany";
Containers, by themselves, do not provide access to their elements. Instead, iterators are used to traverse the elements within a container. Iterators are very similar to smart pointers and have increment and dereferencing operations. By generalizing access to containers through iterators, the STL makes it possible to interact with containers in a uniform manner. In addition, as we saw in Figure 1, iterators are the glue that connects algorithms to containers.
Iterators are the cornerstone of the STL design and give the STL its flexibility. Instead of developing algorithms for a specific container, they are developed for a specific iterator category. This strategy makes it possible to use the same algorithm with a variety of different containers.
Each category forms a set of requirements that must be met by concrete iterator types within that category. Requirements for a given iterator category are specified by a set of of valid expressions for iterators in that category as well as precise semantics describing their usage. In addition, iterators in the STL must satisfy complexity requirements. These requirements ensure that algorithms written in terms of iterators will work correctly and efficiently.
The STL provides a hierarchy of iterator categories as shown in Figure 2. Iterators at the top of the hierarchy are the most general; those at the bottom are the most restricted and have fewer requirements. An iterator satisfies all of the requirements of the iterator below it.
Each container specifies which iterator category it belongs to. By using a novel language technique, the STL selects the right algorithm at compile time depending on the iterator category.
Figure 2: Iterators in the STL form a hierarchy.
Iterators are used in a similar manner as pointers. Just like pointers, for any iterator type, there is guaranteed to be an iterator value that points past the last element of a corresponding container. Each STL container provides member functions, begin() and end(), that return iterator values for the first and end (one past the last) elements.
To iterate through the list of ints we created above, we write:
list::iterator iter;
for (iter = l.begin();
iter != l.end();
iter++) {
cout << *l << endl;
}
Note that each time through the loop we dereference the iterator to
obtain the value the iterator is pointing at. The increment operator
is used to advance the iterator through the list.
The STL also provides const iterators so that iterators may be used with const containers:
template <class T>
void PrintList (const list<T>& l) {
list::const_iterator iter;
for (iter = l.begin();
iter != l.end();
iter++) {
cout << *l << endl;
}
}
The C++ Standard Library provides iostreams to facilitate the reading and writing of data to and from input/output streams. The STL provides two iterator templates so that algorithms may work directly with I/O streams:
For example, we could read data into our list from the standard input as follows:
istream_iterator<int, ptrdiff_t> in(cin); istream_iterator<int, ptrdiff_t> eos; copy (in, eos, back_inserter(l));and later write the list to the standard output:
ostream_iterator out(cout, ", "); copy (l.begin(), l.end(), out):
STL algorithms are decoupled from the particular containers they operate on and are instead parameterized by iterator types. This means that all containers within the same iterator category (see Figure 2) can utilize the same algorithms.
Because algorithms are written to work on iterators rather than components, the software development effort is drastically reduced. Instead of writing a search routine for each kind of container, one need only write one for each iterator of interest. Since different components can be accessed by the same iterators, just a few versions of the search routine must be implemented.
For example, here is the HP implementation [3 ] of the STL count algorithm, which counts the number of elements in a container with a particular value
template <class InputIterator,
class T,
class Size>
void count(InputIterator first,
InputIterator last,
const T& value,
Size& n) {
while (first != last)
if (*first++ == value) ++n;
}
An algorithm which uses InputIterators can be used with any container that works with InputIterators or any of the iterator categories above it in the hierarchy (Figure 2).
To count the number of elements equal to 10 in our list, we can write:
int countTen = 0; count(l.begin(), l.end(), 10, countTen);
The semantics of the InputIterator first and InputIterator last in the STL count algorithm look remarkably like regular C pointers. In fact all STL algorithms will also work with regular C/C++ pointers. For example, we can use the same count algorithm to to count values in a regular int array:
int a[100]; // put some values into array a int countTen = 0; count(&a[0], &a[100], 10, countTen);Most C/C++ programmers are so familiar with the pointer programming paradigm that they quickly become familiar with the STL algorithms.
The pointer-like semantics of STL algorithms guarantee that there is an efficient implementation for them, often resulting in code that is nearly as efficient as hand-written assembly code.
The STL provides many fundamental algorithms in seven categories:
In C, you can make a routine more generic by passing a pointer to a helper function that can be used by the routine as part of its algorithm. This is how the C library quisksort algorithm, qsort, is implemented. To sort an array of integers, we define a comparison function
static int intcmp(int* i,int *j){
return(*i - *j);
}
and pass a pointer to this function when calling qsort:
qsort(a,10,sizeof(int),intcmp);The problem with passing pointers to functions is that they are less efficient than template functions that can be expanded inline.
Function objects are class objects which have a function call operator ( operator()) defined. They contain no data members or constructors/destructors (except the default ones provided by the compiler). Function objects can be passed to template functions in much the same way as pointers to functions are passed to C functions. However, because there is no pointer indirection and because they can often be expanded inline, they are much more efficient.
Suppose we wish to remove from our list, all of the ints that are a multiple of 3. We can use the STL remove_if function and supply our own predicate, called three_mult, as a function object.
The actual checking of the multiple goes in the body of operator(), which returns a bool:
struct three_mult {
bool operator() (int& v) {
return (v % 3 == 0);
}
};
A new list, m, is created as the predicate is applied to each
element of the list by remove_copy_if:
remove_copy_if (l.begin(),
l.end(),
back_inserter(m),
three_mult());
The STL provides many function objects that are used by STL
algorithms, but may also be used by users in their code. The STL
provides function objects for arithmetic operators (e.g.,
times, divides, and modulus), comparison operators
(e.g.,
greater, less, and less_equal), and logical
operators (e.g., logical_and, logical_or, and
logical_not).
Adaptors are template classes that provide an existing class with a new interface. Adaptors can be used to create new interfaces for containers or iterators.
Often it is desirable to create a specialized container from an existing, more general container. The operations of the new container are implemented using the underlying operations of the existing containers. Container adaptors are used to create a new container by mapping the interface of an existing container to that of the new container. This allows new containers to be created without much additional effort, since most of the functionality is already provided by the existing container.
The STL provides three container adaptors: stack<Container>, queue<Container>, and deque<Container>. The following program demonstrates the use of a stack that has been implemented as a vector:
#include <vector.h>
#include <stack.h>
void
main() {
stack <vector<int> > st;
for (int i=0; i < 10; i++)
st.push (i);
while ( !st.empty() ) {
cout << st.top() << " ";
st.pop();
}
cout << endl;
}
Adaptors can also be used to extend the functionality of an existing iterator. The STL provides three iterator adaptors:
The STL provides three different insert iterators that instead of overwriting the value at that location, actually insert a value there. Each type of adaptor performs the insertion into the container in a different place.
Any package provided by the Standard C++ Library must be portable to many different machine architectures. Portability is one of C++'s strengths and the standards process helps to ensure that all compiler vendors have a common base to address this need.
One of the main problems to address in portability is the memory model of the machine. The memory model contains information about pointer types, the type of the difference between two pointers, the size of objects and also which primitives are used to allocate and deallocate raw memory. The STL encapsulates this information in a special class called an allocator. Allocators separate the STL from the dependencies of the underlying memory model of the machine architecture.
Each container is given an allocator when it is constructed. Whenever a container inserts or removes an element, it uses its allocator to allocate and deallocate the memory for the object. The container does not know anything about the memory model of the machine, it relies on the allocator for all of its memory needs.
C++ programmers who develop applications for Microsoft Windows are all too familiar with the multitude of memory models in the DOS and 16-bit Windows environments. However, allocators allow Windows programmers to easily mix models when using STL containers. It is (almost!) easy to have a list in far memory and a vector in near memory, simply by including the correct allocator. To create a list in far memory, we can write:
#include <faralloc.h> #include <list.h> list <int, far_allocator> fl;I say `almost' because the current generation of compilers does not yet support default template arguments that are in fact templates themselves. The STL uses default template arguments to hide the allocator semantics from users. When you specify or declare a container without an allocator, you get the default allocator. As a workaround to this problem, the HP implementation relies on the C++ preprocessor to include the correct allocator for a container. To use a far list, we write:
#include <faralloc.h> #define Allocator far_allocator #include <list.h> list<int> farList;One problem with this workaround is that now it is impossible to use more than one allocator for a given container type in the same source file, since you are limited to reading in a header file just once. However, you may still use mixed-model containers across different source files. This problem will go away as compiler vendors update their compilers to include the STL.
I hope this article has given you a look under the hood of the STL. In fact, if you have not yet experimented with the STL I urge you to try it! You can obtain a public domain version of the STL from HP Labs via ftp from butler.hpl.hp.com [3]. I have been using this implementation with Borland's C++ compiler (Version 4.5). See the stl.faq [3] file for information about other platforms. If you are using the STL, consider sharing your experiences with others in this column! Write me for details at wiseb@cs.rpi.edu.
Copyright 1996 by G. Bowden Wise
Want to learn more about C++? You can go to an index or the next installment or the previous installment of this series.
Last Modified:
Location: www.acm.org/crossroads/xrds2-3/ovp.html