Standard C/C++
P. J. Plauger
The Header <memory>
STL tries to simplify life for users by providing storage management for its own containers. That makes STL anything but simple for implementors. A peek at the underlying machinery is instructive for everyone.
Introduction
Of the thirteen headers that constitute the Standard Template Library, the header <memory> is by far the hardest to understand. Last month, I described its principal inhabitant, template class allocator. (See ``Standard C/C++: Allocators,'' CUJ, June 1996.) It serves as a prototypical allocator, or storage manager, for all the container classes in STL. This month, I complete my overview of the header <memory> by discussing everything else that it defines.
The common theme for all entities defined in this header is storage management. An STL container allocates and frees storage for the elements of the sequence it controls. Some STL algorithms can benefit from the use of a temporary storage area, if it can be made available. So an obvious need exists for mechanisms that allocate storage, free it, and ensure that chunks of it don't get mislaid. C programmers will recognize these services as just a somewhat more structured version of the old standbys malloc and free.
But C++ has an additional need. A typical object must be constructed, once allocated, then destroyed, before it is freed. By contrast, the basic object types inherited from C can be adequately initialized just by assignment, and they need no special preparation before they are freed. So an important concomitant to any machinery for storage allocation and freeing in C++ is comparable machinery for constructing and destroying the objects in question.
As with earlier STL headers, I present header <memory> in logical chunks, from beginning to end. The first chunk was the topic of last month's column. For continuity, and to minimize confusion among regular readers of this column, I extend the chunk numbering scheme this month. So don't be too surprised when the first listing you see is labeled ``Part 2.''
Uninitialized Copy and Fill
Template container vector represents its sequence of elements as a contiguous array. You can initialize its elements from another sequence, or by replicating a value throughout the sequence. To alter the length of the sequence, the container must typically allocate ``raw'' (unconstructed) storage as an array of the desired size, then copy over the existing storage. All these operations can be expressed in terms of a handful of simple algorithms:
template<class InIt, class FwdIt> inline
FwdIt uninitialized_copy(InIt first, InIt last, FwdIt x);
template<class FwdIt, class T> inline
void uninitialized_fill(FwdIt
first, FwdIt last,
const T& x);
template<class FwdIt, class Size,
class T> inline
void uninitialized_fill_n(
FwdIt first, Size n,
const T& x);
The first algorithm copies the sequence designated by the range of iterators [first, last) to the sequence designated by the iterator x. (Remember that InIt can be any kind of input iterator, and FwdIt can be any kind of forward iterator.) It does so by constructing each element of the destination sequence using its copy constructor.
The second algorithm operates in reverse. It constructs each element of the sequence designated by [first, last) by copying the value x. The third does much the same, except that the destination sequence consists of n elements beginning at first.
Listing 1 shows the chunk of header <memory> that implements these three algorithms. All make use of the template function _Construct that I showed last month. You should not be surprised to learn that the header <algorithm> contains similar algorithms with the names copy, fill, and fill_n. These perform much the same operations, except that they copy by assignment instead of by construction.
Temporary Buffers
I mentioned earlier that some algorithms can make use of temporary storage. Sorting, merging, and partitioning can often be performed faster by copying elements to and from a scratch area, instead of working in place with just one or two temporary objects. The header <memory> meets this need by defining a pair of template functions for allocating and freeing a temporary buffer:
template<class T> inline
pair<T *, ptrdiff_t>
get_temporary_buffer(ptrdiff_t n);
template<class T> inline
void return_temporary_buffer(T *p);
The first template function lets you allocate storage for an array of up to n objects of type T by calling get_temporary_buffer<T>(n). If the first member of the returned pair is not a null pointer, then it has the value p, a pointer to the beginning of the allocated storage. Its actual size is given by the second member, which may be less than n. You are obliged to return any storage successfully allocated this way by calling return_temporary_buffer(p).
The algorithms in STL never request more than one such buffer at a time. They are also pretty tolerant of being short changed. If no buffer can be allocated, or if it is smaller than requested, the algorithm still works correctly, It merely slows down.
Unfortunately, get_temporary_buffer cannot generally be implemented in the form shown above. The explicit parameter list (<T> in this case) is required for template classes but not permitted for template functions in a typical C++ compiler currently available. So the implementation shown here retains the older ruse of requiring a second, pointer argument to convey the element type. The actual call looks like get_temporary_buffer(n, (T *)0).
Listing 2 shows the chunk of header <memory> that allocates and frees temporary buffers. I showed the macros _PDFT, _FARQ, and _SIZT last month. They let you alter the header to support storage allocation on a far heap. Note also the use of triple-slash comments to turn off code that can't yet be compiled, and to flag substitute code that must eventually be removed.
Algorithms that make use of temporary buffers face an administrative problem. The first time you store a value in an element of such a buffer you have to construct the element. The fill and copy algorithms shown above can sometimes do the job, but not always. In many cases, the algorithm is generating elements on the fly. It really wants to pretend that it's working with just another iterator.
That's where template class raw_storage_iterator comes in. It is an output iterator, accepting a sequence of generated values in strictly increasing order with no backing up or multiple stores to the same object. Its peculiar claim to fame is that it stores a generated sequence in raw storage. Thus, it constructs elements as it goes.
Listing 3 shows the chunk of header <memory> that implements template class raw_storage_iterator. You specialize it for given iterator and element types. The parameter name OutIt suggests that any old output iterator will do for the first parameter, but this is misleading. For an iterator p of this type, you must be able to obtain a pointer to the raw storage that it designates by writing &*p. It would be more honest to say that this parameter must be a forward iterator, but that's the way the draft C++ Standard reads.
Regular readers of this column might notice a change in notation from past installments. Earlier columns designated an output iterator by deriving publicly from the base class output_iterator. Well, that went away at the March 1996 meeting, in favor of a more general template base class called iterator. I'll skip the gory details for now. Just know that iterator<output_iterator_tag, void, void> is the latest name for the base of all output iterators.
Otherwise, template class raw_storage_iterator closely follows the pattern for writing all output iterators.
Algorithms that use temporary buffers face additional administrative problems. Once an element of the temporary buffer is constructed, subsequent stores must not involve construction, lest they commit the sin of double construction. So an algorithm that makes multiple passes over a temporary buffer must keep careful track. Elements not yet constructed get constructed, while recycled elements get assigned. And before the temporary buffer can be freed, any constructed elements must be meticulously destroyed.
The original STL code from Hewlett-Packard endeavors to do all these things with inline logic. The result is added complexity, in algorithms that are complex to begin with. And the inevitable consequence is occasional bugs, when the bookkeeping goes awry. So I chose a more structured approach that encapsulates most of the messy logic involved in using temporary buffers.
Listing 4 shows the chunk of header <memory> that implements template class _Temp_iter. It is an output iterator that manages a temporary buffer, but it is rather more thorough than template class raw_storage_iterator. The constructor _Temp_iter<T>(n) requests a temporary buffer that can hold up to n elements of type T. Its destructor automatically frees any temporary buffer so obtained. The iterator keeps track of the usage high-water mark within the buffer. It constructs stored elements or assigns them as needed. And, of course, it destroys elements as needed before freeing the buffer.
That's not the end of it. A copy of _Temp_iter<T> uses the same storage as the original, so the bookkeeping is correct even when such iterators are returned by value from functions. The template class also defines a handful of special member functions for controlling rescans of the buffer:
- Init() resumes storing at the beginning of the buffer
- First() returns a pointer to the beginning of the buffer
- Last() returns a pointer to the next place to store (just past the last element stored) in the buffer
- Maxlen() returns the length of the buffer
I won't describe their usage in any more detail here. They make more sense in conjunction with the algorithms that use them.
Suffice it to say that my implementation of STL makes no direct use of get_temporary_buffer or return_temporary_buffer. It makes no use at all of raw_storage_iterator. I've found that _Temp_iter provides a much more structured solution.
Template Class auto_ptr
Template class auto_ptr is not part of the original STL proposal. Rather, it is a later addition that was parked in the header <memory> as the most suitable resting place. It is designed to deal with the problem of storage leaks that can occur in the presence of exceptions.
Put simply, an auto_ptr<T> encapsulates a pointer to an allocated object of type T -- one obtained by calling operator new. Multiple auto_ptr<T> objects can store the same pointer value, but only one such object actually ``owns'' the pointer. Ownership can be transferred by assignment or by copy construction. It can be given away explicitly by calling the member function release. Otherwise, when the auto_ptr<T> object is destroyed, it deletes the object designated by a pointer that it still owns.
Why have all this machinery? A thrown exception is meticulous about destroying any dynamically allocated objects (storage class auto or register) that go out of scope as the exception is passed up the line. But it cannot know to destroy objects allocated by explicit calls to operator new, as in a new expression. They must be deallocated by explicit calls to operator delete, as in a delete expression. Template class auto_ptr provides a way to tie explicitly allocated storage to dynamically allocated storage. It ensures that the controlled object is deleted however the pointer that controls it goes out of scope.
Listing 5 shows the chunk of header <memory> that implements template class auto_ptr. The full definition provides for constructing and assigning from auto_ptr objects with a different parameter type, but that requires member templates. As usual, this implementation supplies a simpler interim version that only allows an initial value of the same type.
Operator new
The final item in header <memory> is an overload for operator new. Listing 6 shows the last remaining chunk of header <memory>. It defines the template operator:
template<class T>
void *operator new(size_t n, _STD allocator<T>& al);
Basically, this overload lets you write new T(al) to allocate and construct an object of class T, obtaining storage from the allocator<T> object al. To understand the mysteries of the code, see last month's installment.
Note that operator new is defined outside the scope of namespace std. Many issues with regard to namespaces remain unclear, but early implementors seem agreed on this point. It does not make sense to talk about an instance of operator new other than in the global namespace. In mysterious matters such as these, I just do as I'm told.
P.J. Plauger is senior editor of C/C++ Users Journal. He is convener of the ISO C standards committee, WG14, and active on the C++ committee, WG21. He developed Lib Suite ++, the Plum-Hall validation suite for the Standard C++ library. His latest books are The Draft Standard C++ Library, Programming on Purpose (three volumes), and Standard C (with Jim Brodie), all published by Prentice-Hall. You can reach him at [email protected].
