Prev Up Next
Go backward to Generic Algorithms
Go up to Top
Go forward to Literate Generic Programming


STL provides a set of easily composable software components of six major kinds: generic algorithms, containers, iterators, function objects, adaptors, and allocators. In each of these component categories, STL provides a relatively small set of fundamental components; it is through uniformity of interfaces and orthogonality of component structure that STL provides functionality far beyond the actual number of components included. But STL is not intended as a closed system; its structure is designed with extension in mind. Because of limitations imposed by the C++ standardization process, many capabilities that might have been included have been left for future extension efforts. Additional generic algorithms and containers are obvious directions for extension, but it is in the area of adaptors that some of the most immediately useful and nontrivial extension possibilities exist. An adaptor is a component that takes another component and outfits it with a new interface, or provides the same interface but with different or additional "behind-the-scenes" functionality. For example STL provides stack, queue, and priority-queue adaptors that provide a new and more restricted interface to the capabilities of other sequence containers. Reverse iterators are an example of providing the same interface with different functionality. There are no examples in STL of providing additional functionality, but there appear to be many potentially useful possibilities for such adaptors.

Performance Measurement Adaptors

A major kind of behind-the-scenes functionality that can be provided by adaptors is keeping counts or logs of activity, for use in performance testing and tuning. For this purpose, adaptors are being developed for adding such history-keeping to containers, iterators, and function objects. Library components for post-processing of the statistics or logs are also being developed. Such information can provide different and often better insight into performance characteristics of algorithms or application code than standard profiling or timing techniques.

These components have been used extensively in the development of the new generic algorithms described in the previous section.

Complete Traversal Adaptors and Algorithms

A complete traversal of a container C (such as a set) is informally described by the iteration scheme

for  x  in C, F(x,C)
where F is a function that might possibly modify C by inserting new elements into it. We assume that the order in which the elements are treated is not relevant, as long as the iteration continues until F has been applied to all elements currently in C, including those F has inserted. Standard iteration mechanisms, such as the iterators provided in the C++ Standard Template Library (STL), do not directly support complete traversals.


Prev Up Next