|
|
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:
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.