Standard Template Library Programmer's Guide

The balance operation proceeds as described in the paper cited above. The operation is non-destructive; rebalanced pieces formerly shared with other ropes are no longer shared after the operation. As a rope is being balanced, the balanced bit is set in each concatenation node that has sufficiently small depth for its length. Tree nodes with the balanced bit set are not examined by further balancing operations. Thus the balance operation tends to not rebalance the same substring.

The worst-case cost of rebalancing is nonetheless linear in the string. However, the observed behavior is that rebalancing typically consumes a small fraction of the running time. Indeed, all natural ways of building a rope of length N by repeated concatenation require total time linear in N . It is possible, but nontrivial, to design concatenation sequences that violate this.

The substring operation is performed differently depending on the tree node representing the root of the rope. The operation is recursive:

1. For a leaf node, we either return a leaf node with the substring, or if that would be too long, we return a subscript node.

2. For a concatenation node, we return the concatenation of the appropriate substrings of the left and right subtrees. We stop if we find that we need a zero length substring. Similarly, we simply return a pointer to the entire rope when that's appropriate.

3. For a substring node, we either return a short leaf node, or a new substring node. referring to the rope from which the original substring was obtained. Thus we do not build up nested substring nodes.

4. Any other function node is treated roughly as a leaf.

Note that this process requires time proportional to the rope depth, and doesn't directly depend on the length. The algorithm only copies pieces of leaf nodes at the beginning and end of the substring, and it builds new concatenation nodes along the paths from the root to either end of the substring. The interior of the substring can remain shared with the original rope.

Iterators generated by the normal begin() and end() operations generate const_iterators, i.e. iterators that do not permit updates to the underlying rope. Such iterators basically contain three kinds of information:

1. A pointer to the root node of the rope with which the iterator is associated. This pointer is not included in the reference count, Const_iterators become invalid if the underlying rope is modified or destroyed. (In the garbage collected case they remain valid and continue to refer to the original pre-modification rope.)

2. The position inside the rope.

3. Cached information used to speed up access to sections of the rope close to the current position.

We maintain two kinds of cache information in the iterator:

1. The limits of a contiguous block of storage holding the characters surrounding the current character position, and the current offset within that block. Most iterator references can be resolved with access to only this part of the cache. The referenced block of storage can either be part of a leaf in the rope representation, or it can be a small block of characters reserved inside the iterator itself. The latter is used when the iterator refers to a rope section represented by a function node.

2. The bottom few rope nodes on the path from the root node to the leaf or function node currently referenced by the iterator. This is used to quickly increment or decrement the iterator across node boundaries. We do not cache the entire path, since that would make rope iterators unpleasantly large.

This implementation differs significantly from that used in the C "cord" package. We do not reserve space inside iterators for a complete path from the root to the current node. This change was made to accommodate STL code that assumes small iterators that can be cheaply passed by value. We try to aid such code further by providing an iterator assignment operation which does not copy the cache part of the iterator unless it has been initialized.

The character buffer in the iterator is needed since there is not another place to cache characters returned for the evaluation of a function node. (This is less of an issue with a garbage collector, since it turns out to be reasonably efficient to maintain such caches in the function object itself. Without a garbage collector, this requires locking around cache accesses, which is usually unacceptable.)

Mutable iterators differ primarily in that they also contain a pointer to the rope itself (i.e. a pointer to the tree node pointer), so that they can be used to perform updates, and in that the rope root pointer is included in the reference count. In this case the rope root pointer is redundant, except that it us used to detect changes in the rope, so that the cached information in the iterator can be invalidated. The rope has changed iff the rope itself no longer points to the same node as the rope root pointer in the iterator. The fact that the iterator is included in the reference count ensures that the root node cannot be dropped and reused. It also prevents the rope from being destructively updated while the iterator must remain valid.

This document consists of 2 sections. The first discusses some of the decisions made in the implementation of default allocators in the SGI STL. These decisions influence both the performance of the default allocator, as well as its behavior with leak detectors.

The second section describes the original design of SGI STL allocators. The current SGI STL also supports the allocator interface in the C++ standard. The interface described here is specific to the SGI STL and cannot be used in code that must be portable to other STL implementations. Thus its use is now discouraged. The discussion is nonetheless preserved both for historical reasons, and because it exposes some of the issues surrounding the standard interface.

The default allocator alloc maintains its own free lists for small objects. It uses an underlying system-provided allocator both to satisfy larger requests, and to obtain larger chunks of memory which can be subdivided into small objects. Two of the detailed design decisions have proven to be controversial, and are explained here.

Malloc is used as the underlying system-provided allocator. This is a minor design decision. ::operator new could also have been used. Malloc has the advantage that it allows for predictable and simple failure detection. ::operator new would have made this more complicated given the portability and thread-safety constraints, and the possibility of user provided new handlers.

Memory allocated for blocks of small objects is not returned to malloc. It can only be reused by subsequent alloc::allocate requests of (approximately) the same size. Thus programs that use alloc may appear to leak memory when monitored by some simple leak detectors. This is intentional . Such "leaks" do not accumulate over time. Such "leaks" are not reported by garbage-collector-like leak detectors.

The primary design criterion for alloc was to make it no slower than the HP STL per-class allocators, but potentially thread-safe, and significantly less prone to fragmentation. Like the HP allocators, it does not maintain the necessary data structures to free entire chunks of small objects when none of the contained small objects are in use. This is an intentional choice of execution time over space use. It may not be appropriate for all programs. On many systems malloc_alloc may be more space efficient, and can be used when that is crucial.