Standard Template Library Programmer's Guide

• The containers can be instantiated with a single allocator, which can be redirected to different files by calling additional member functions. The allocator must be suitably redirected before container calls that may allocate.

(Shared with standard allocators.) Some C++ programming texts have suggested that individual classes keep a free lists of frequently allocated kinds of objects, so that most allocation requests can be satisfied from the per-class free list. When an allocation request encounters an empty free list, a potentially slower allocator (e.g. new or malloc) is called to allocate several of the required objects at once, which are then used to replenish the free list.

The HP STL was designed along these lines. Allocators were intended to be used as the slower backup allocator. Containers like list were presumed to maintain their own free list.

Based on some small experiments, this has no performance advantage over directly calling the allocate function for individual objects. In fact, the generated code is essentially the same. The default allocator we provide is easily inlined. Hence any calling overhead is eliminated. If the object size is statically known (the case in which per-class free lists may be presumed to help), the address of the free list header can also be determined by the compiler.

Per-class free lists do however have many disadvantages:

• They introduce fragmentation. Memory in the free list for class A cannot be reused by another class B , even if only class B objects are allocated for the remainder of program execution. This is particularly unfortunate if instead of a single class A there are many instances of a template class each of which has its own free list.

• They make it much more difficult to construct thread-safe containers. A class that maintains its own free list must ensure that allocations from different threads on behalf of different containers cannot interfere with each other. This typically means that every class must be aware of the underlying synchronization primitives. If allocators allocate individual objects, then only allocators themselves need to address this issue, and most container implementations can be independent of the threading mechanism.

• Garbage collecting allocators are difficult to accommodate. The garbage collector will see per-class free lists as accessible memory. If pointers in these free objects are not explicitly cleared, anything they reference will also be retained by the collector, reducing the effectiveness of the collector, sometimes seriously so.

We chose to require an explicit size argument, both for deallocate, and to describe the original size of the object in the reallocate call. This means that no hidden per-object space overhead is required; small objects use only the space explicitly requested by the client. Thus, even in the absence of fragmentation, space usage is the same as for per-class allocators.

This choice also removes some time overhead in the important special case of fixed-size allocation. In this case, the size of the object, and thus the address of the free-list header becomes a clearly recognizable compile-time constant. Thus the generated code should be identical to that needed by a per-class free-list allocator, even if the class requires objects of only a single size.

This is probably the most questionable design decision. It would have probably been a bit more useful to provide a version of reallocate that either changed the size of the existing object without copying or returned NULL. This would have made it directly useful for objects with copy constructors. It would also have avoided unnecessary copying in cases in which the original object had not been completely filled in.

Unfortunately, this would have prohibited use of realloc from the C library. This in turn would have added complexity to many allocator implementations, and would have made interaction with memory-debugging tools more difficult. Thus we decided against this alternative.

The actual version of reallocate is still quite useful for container specializations to specific element types. The STL implementation is starting to take advantage of that.

• New feature: concept checks. The library now does better compile-time error checking to make sure that the types used to instantiate library templates conform to the templates' requirements.

• Removed two non-standard-conforming extensions: the second, defaulted template parameter in bitset, and the third, default template parameter in deque.

• Many bug fixes, performance enhancements, and compatibility improvements.

• New feature: header, as defined in section 26.3 of the C++ standard.

• header is now supported on compilers that lack support for constant initialization of static const data members, such as Microsoft v6.0.

• Performance improvements in copy for compilers that lack support for partial specialization of templates.

• Improved support for insert_iterator when used with hash tables and slist.

• Documentation bug fix: documentation now makes it clear which library features are standard and which are SGI extensions.

• Bug fixes.

• Added a Frequently Asked Questions list.

• Bug fixes, particularly in multithreading support for non-SGI compilers.

• The at member function is now supported for the vector and deque classes. (It was previously supported only for string.)

• Minor bug fixes.

• The and headers are now supported on compilers that lack full support for member templates and partial specialization, such as Microsoft v6.0.

• Code to support multithreading has been consolidated in a single file, so that system dependences are better isolated.

• Minor bug fixes.

• Faster operator[] in map.

• Algorithmic improvements in find, find_if, and partition.

• The standard exception hierarchy is now usable on compilers that do not provide an header.

This release provides several new features.

• Standard-conforming string and bitset classes, and the standard exception hierarchy.

• Standard-conforming allocators, including the default allocator class allocator. All containers now use standard allocators, and all containers now support allocators whose instances are distinct. Old-style allocators, like alloc, are still supported for backward compatibility.

• Algorithmic improvements in search.

• All sequences now support the resize and assign member functions. All sequences now properly support overloaded insert member functions and constructors in the presence of member templates.

• Bug fixes in rope, and minor bug fixes elsewhere. Minor changes for standard conformance.

• Standard-conforming auto_ptr class.

• Internal names, such as names of function and template parameters, have been changed so that they cannot conflict with user names (including user macros).