The Design of C++ Standard Components

Algorithms and data structures

The biggest determinants of a component's execution speed are its internal data structures and algorithms. Consider the ordered collection classes of the Set(3C++) component. If we use search trees to represent sets, then searching, insertion, and removal are fast, but iteration is slow. If we use a sorted array representation, then searching and iteration are fast, but insertion and removal are slow. In general, no single implementation is best for all applications. There are two ways out of this dilemma:

Provide multiple implementations of each component. For example, provide an array-based implementation of Set(3C++), a search tree-based implementation, a hashed version, one that uses skiplists, and so on. Customers can then choose the implementation that is best for a specific application. For example, a customer whose application spends most of its time inserting and removing might choose the skiplist-based implementation, while a customer whose application spent most of its time iterating would use the array-based implementation.
Provide just one implementation, but make sure that is fast enough for most applications.

The first strategy quickly encounters a law of diminishing returns: for each new implementation provided, how many customers will actually use it? In dollar terms, will enough customers buy the component to defray our development and maintenance costs? Furthermore, some users may not want to have to choose between different implementations of a component.

We adopted the second strategy for C++ Standard Components. For each component, we provide a single implementation based on data structures and algorithms that will be fast enough for most applications (see below). Notice that this does not preclude multiple implementations in the future.

To illustrate what we mean by ``fast enough'', consider the class Set_of_p (pointer sets) provided by the Set(3C++) component. The current implementation is based on a data structure called a digital trie. All operations involving a single set element (like membership testing, inserting, removing) are done in constant time (that is, time independent of the size of the set), operations involving all set elements (like iteration) are linear in the size of the set, and operations involving the elements of two sets (like algebraic and relational operations) are linear in the size of the larger set. In terms of order estimates (see below), these complexities are optimal. In terms of complexity theory, in the limit, our implementation will be as good as any other implementation, to within a constant multiplier.

We believe that information about the space and time complexity of a function belongs in the function's public interface. We have therefore tried to include (at least) order estimates for each function documented in the C++ Standard Components Programmer's Reference Manual. You will find this information either in the description section, associated with the function, or summarized in a separate complexity section. For some components (like Array_alg(3C++), we give operation counts in addition to order estimates, as illustrated by the following excerpt from the description of function part_ps() in part(3C++):

   If N is the size of the block, then complexity is
   O(NlgN).
   Exactly N tests of the criterion and at
   most 3NlgN assignments are done.