Standard Template Library Programmer's Guide

This does not preclude the use of STL algorithms in conjunction with containers or iterators that do not meet the standard complexity specifications. This is occasionally quite useful, especially if the code is either not performance critical, or other requirements on the container make the performance specifications unrealizable. But this has two potential problems. First, the algorithm may no longer be the right one, or even a reasonable one, for the problem. A different algorithm may be better tailored to actual relative costs of the container operations. Second, the algorithm is, of course, unlikely to satisfy its specified complexity constraint.

The complexity specifications in STL are, of necessity, an oversimplification. A full specification would describe exactly how the running time of an operation varies with that of the operations it invokes. The result would be rather unmanageable for the user, who would have to be keep track of large amounts of irrelevent detail. It would be overly constraining on the implementor, since overall improvements on the existing algorithms may not satisfy such detailed constraints.

Concept specifications ( e.g. Forward Iteratoror Container) specify complexity requirements that should be met by all instances of the concept. This is the minimum behavior required by operations ( e.g. sort ) parameterized with respect to the concept. Any specific instance ( e.g. vector ) is likely to perform better in at least some cases.

It is difficult to specify precisely when an algorithm satisfies a performance constraint. Does copying a vector on a 16-bit embedded processor take constant time? After all, the size of the vector is limited to some value less than 65,536. Thus the number of memory operations involved in the copy operation is certainly bounded by a constant. It is even conceivable that the worst case vector copy time on this processor may be less than the worst-case time for a single memory access on a machine with paged virtual memory. Nonetheless, it would be intuitively wrong to describe a vector copy or a list traversal as being a constant time operation. Even on this machine, a vector implemented as a list is unlikely to yield satisfactory performance. (Of course, so would an implementation that looped for a second for every vector access, although that would clearly run in constant time. The point here is to communicate the proper intent between implementor and user, not to guard against malicious or silly implementations.)

Fundamentally, it is difficult to define the notion of asymptotic algorithm complexity precisely for real computer hardware instead of an abstract machine model. Thus we settle for the following guidelines:

1. For an algorithm A to have running time O( f(n) ), there must be a corresponding algorithm A' that is correct on machines with arbitrarily long pointer and size_t types, such that A and A' perform essentially the same sequence of operations on the actual hardware. (In simple cases A and A' will be the same. In other cases A may have been simplified with the knowledge that adresses are bounded.) For inputs of sufficiently large size n , A' must take at most time Cf(n) , where C is a constant, independent of both n and the address size. (Pointer, size_t , and ptrdiff_t operations are presumed to take constant time independent of their size.)

2. All container or iterator complexity specifications refer to amortized complexity. An individual operation may take longer than specified. But any sufficiently long sequence of operations on the same container or iterator will take at most as long as the corresponding sum of the specified operation costs.

3. Algorithms specify either worst-case or average case performance, and identify which. Unless otherwise stated, averages assume that container elements are chosen from a finite type with more possible values than the size of the container, and that container elements are independently uniformly distributed.

4. A complexity specification for an operation f assumes that operations invoked by f require at most the specified runtime. But algorithms generally remain appropriate if the invoked operations are no more than a logarithmic factor slower than specified in the expected case.

5. If operations are more expensive than assumed by a function F in the current STL, then F will slow down at most in proportion to the added cost. Any future operations that fail to satisfy this property will make that explicit.

To make this precise, assume F is specified to use time f(m) for input of size m . F uses operations G k , with specified running times g k (n) on input size n . If F is used in a context in which each G k is slower than expected by at most a factor h(n) , then F slows down by at most a factor h(m) . This holds because none of the current algorithms ever apply the operations G k to inputs significantly larger than m .

This is an attempt to answer some of the questions related to the use of strings with SGI STL.

There are several problems, but the most serious ones relate to the specification for lifetimes of references to characters in a string. The second committee draft disallows the expression s[1] == s[2] where s is a nonconstant string. This is not simply an oversight; current reference counted implementations may fail for more complicated examples. They may fail even for s[1] == s[2] if the string s is simultaneously examined (merely examined, not necessarily modified) by another thread. It is hard to define precisely what constitutes a correct use of one of the current reference counted implementation.

This problem was partially addressed at the July 1997 meeting of the C++ standardization committee; the solution was to adopt more complicated rules about reference lifetimes. Unfortunately, these new rules still do not address the multi-threading issues.

A related problem was pointed out in the French national body comments on the second committee draft. The following program produces the wrong answer for most reference counted basic_string implementations that we have tested; the problem is that, if two strings share a common representation, they are vulnerable to modification through a pre-existing reference or iterator. # include &ltstring> # include &ltstdio.h>

main() {

string s("abc");

string t;

char& c(s[1]);

t = s; // Data typically shared between s and t.

c = 'z'; // How many strings does this modify?

if (t[1] == 'z') {

printf("wrong\n");

} else {

printf("right\n");

}

}

The draft standard (as well as common sense) says that updating a reference to one of s 's elements should only modify s , not t as well; the fact that s and t might share a representation is an implementation detail that should have no effect on program behavior. Given the design of basic_string , though, it is very difficult for a reference-counted implementation to satisfy that requirement.