C/C++ Contributing Editors

Standard C/C++: Exception Safety in STL

P. J. Plauger

STL was originally written with no concern about exceptions, but the C++ Standard reconciled the two technologies just before it froze.

Introduction

It's been some time since I reviewed the Standard Template Library as it appears in the Standard C++ library (See all installments of my column, "Standard C/C++," CUJ from December 1995 to June 1997 inclusive.) Shortly after the last part of that presentation, the C++ Standards committee began revamping the specification for STL. That task continued through the November 1997 meeting in Morristown, New Jersey, where the draft was finally frozen.

A number of small changes were made to the STL headers, which I won't attempt to detail here. What I will do, however, is describe a general cleanup the committee made to STL. The most important part of that cleanup was a careful rethinking of how STL containers and algorithms should interact with exceptions. The resulting changes to the C++ Standard require all implementations of STL to become rather more cautious. We implementors are forced to work harder so that programmers can have better guarantees when using the Standard C++ library.

Here is the essence of the problem. Exceptions are a powerful mechanism for handling error conditions that are, well, exceptional. You don't want to handle them as part of the normal flow of control — they're too much of a distraction from the problem at hand. Instead, you throw an exception at the point you detect the error. Somewhere higher in the nest of control blocks and calling functions, you can catch the thrown exception at a more convenient place for processing it. C++ unwinds the stack and destroys any automatic objects that go out of scope along the way.

On the other hand, STL containers are a powerful mechanism for organizing homogeneous sequences of objects on your behalf. You want them to make whatever changes you request to the controlled sequences, and leave them in a coherent state each time they return control to you. The last thing you want to do is distract a container partway through some change. Neither you nor the container code is likely to know how to clean up the damage.

So what happens if an STL container decides to throw an exception, or performs an operation that might do so on its behalf? An obvious example is storage allocation. A container allocates and frees storage as needed to store the elements of the sequence it controls. Any allocation can fail, through no fault of the code requesting the storage, simply because some other agency has used up the last of available storage. Once upon a time, you got a null pointer to signal a failed allocation. Nowadays, the allocator (such as operator new) typically throws an object of class bad_alloc.

It's hardly asking too much of an implementor to ensure that a container is left in a consistent state if an allocation fails. Perhaps the implementor can't predict when such a failure will occur, but it is pretty obvious where in the code it can happen. You just have to make sure you have a bird in the hand — the allocated storage — before you start altering the stored control information to reflect the change to the container. At the very least, you want the destructor for the container to tidy up sensibly. At the most, you want the container to be ready if some agency catches the exception and tries to perform another operation on the container. It should look like a coherent container.

STL containers themselves throw exceptions on one or two other occasions. An obvious example is the member function at. When present, it serves as a checked form of indexed access. If vec[i] accesses element i, then vec.at(i) does the same with checking. Should i be an invalid index, the member function throws an object of class out_of_range. Once again, it's not too much to ask of an implementor to ensure that the container be left in a consistent state when it throws the exception.

But STL containers are templates. You specialize a template by specifying one or more type parameters. You can specify a class that you define yourself. The template expansion then includes code that you yourself have written — constructors, destructors, assignment operators, even types and member functions with prespecified names. Put simply, a template specialization is a cooperative endeavor between you and the library implementor.

So how do you cooperate when it comes to exceptions? You may want to throw an exception from a constructor you provide when it can't construct an object properly, or destroy it, or assign it, or whatever. A member function defined by the container may be partway through an operation when it defers to your code. If your code throws an exception, the member function had better be prepared to ensure that the container stays in a consistent state. One way is to call programmer-supplied code only in places where it is acceptable to lose control due to a thrown exception. Another way is to call programmer-supplied code from within a try block, so the member function can tidy up as needed before rethrowing the exception.

Considerations such as these greatly complicate the business of implementing the STL containers. They are hard enough to write to begin with, I can attest — one of the big reasons why STL is such a valuable addition to the Standard C++ Library. In fact, the situation is worse than "greatly complicated." Some talented people have studied the matter in detail. (Two principal contributors are Dave Abrahams, from Mark of the Unicorn, and Greg Colvin, now at Oracle.) They concluded that it is essentially impossible to write containers that are safe against exceptions being thrown from arbitrary places within programmer-supplied code.

All is not lost, however. If you impose some pretty reasonable constraints on when exceptions can occur, it is possible to write STL containers that are reasonably exception safe. By "reasonably," I mean that if a permissible exception is thrown in programmer-supplied code, the container that calls this code makes one of two promises. In descending order of desirability, the promises are:

In either event, there should be no memory leaks, of course.

The final C++ Standard spells out the reasonable constraints on programmer-supplied code. It requires that all containers keep the second (weaker) promise above, in the presence of permissible exceptions. And it spells out the places where containers keep the first (stronger) promise above.

Constraints on Value Types

For a comprehensive example, consider the declaration:

typedef map<Mykey, Myval, Mycomp, Myalloc> Mymap;

This specializes the template container map, defined in the header <map>, for the four template parameters:

Each of these four template parameters can be a class you define, with numerous opportunities for throwing exceptions. I'll discuss them in turn, but first a blanket prohibition. No destructor may throw an exception. There are a host of reasons why:

When can you throw an exception? Consider first the types Key and Value. The container has to construct objects of these types, destroy them, and copy them by assignment. For objects of type Key, it must also compare them using operator() defined by class Mycomp. I've already ruled out throwing exceptions during destruction. But all the other operations can conceivably have occasion to throw an exception.

Here's the kind of thing you have to do to insert a new element in a map:

iterator
_Insert(_Nodeptr _X, _Nodeptr _Y, const _Ty& _V)
{if (max_size() - 1 <= _Size)
    throw length_error("map<T> too long");
_Nodeptr _Z = _Buynode(_Y, _Red);
_Left(_Z) = _Nil, _Right(_Z) = _Nil;
try
    {_Consval(&_Value(_Z), _V); }
catch (...)
    {_Freenode(_Z);
    throw; }
++_Size;
<do the actual insertion>

Type _Ty is a synonym for:

pair<const Key, Value>

the information stored in each element of the map, a.k.a. a map node. And _Nodeptr is a synonym for a pointer to one of these nodes.

Note the cautious preparations. First the container ensures that it can represent the new size of the container. If not, it throws an object of type length_error to report the failure. The map remains in a consistent state. The call to _Buynode attempts to allocate a new map node and fill in some of its fields. If the allocation fails, _Buynode can throw an exception. In this case, the member function simply allows the exception to propagate. It is still in a consistent state.

The template function _Consval attempts to construct the {key, value} pair in the _Value field of the node, using placement semantics. Thus, it calls on the constructor for pair<const Key, Value>, which in turn calls on the constructors for Key and Value. Either of these can throw an exception. If the pair is partially constructed before the throw, it is up to the compiler to ensure that the wreckage is properly destroyed — we don't have to worry at that level. But we do have to worry about what happens to the container when the exception is propagated.

In this case, the only cleanup required is to call _Freenode to free the allocated node. Note that this can involve destroying the links that were initialized in _Buynode. Generally speaking, these are simply object pointers, which have (implicit) destructors that do nothing. But my implementation of STL does its best to accommodate allocators that return "pointers" which are really classes. If they need destroying, it is up to _Freenode to ensure that the job gets done before the storage is freed.

Only after the code runs this gauntlet of potential throws does the member function _Insert really believe it can do the insertion. It increments _Size, the size of the container, and proceeds to stitch it into place in the tree structure that represents the ordered map.

In fact, the code takes one additional precaution not immediately apparent in the above snippet. The arguments to _Insert denote the place in the tree where the insertion should occur. The caller determines this place by climbing over the tree, making any number of key comparisons. Should any of these key comparisons throw an exception, the container doesn't even try to call _Insert. Talk about walking on eggs.

Other Programmer Constraints

Remember that key comparisons are performed by calling operator() defined in class Mycomp. Obviously, this function can throw an exception if the mood strikes it. The STL containers are flexible enough to tolerate a function pointer instead of a proper class for Mycomp. In that case, you needn't worry about the constructor for the pointer throwing an exception.

But you do have to worry if Mycomp represents a class with a nontrivial constructor. One advantage of using a function object (a.k.a. functoid) of this sort is that you can squirrel away additional data within the object. An accompanying disadvantage is that the constructors or assignment operators for the stored data can throw exceptions. This has implications for container assignment and content swapping. The function object has to be copied along with the controlled sequence, otherwise the ordering rule could change. So a container has to be prepared for an exception thrown by a seemingly innocuous operation such as copying the stored function object.

And that leaves class Myalloc. An allocator in STL encapsulates the work of allocating and freeing storage for a container. To implement allocators fully, you have to stress a C++ compiler pretty hard. Thus, many implementations of allocators do not conform fully to the final C++ Standard. They instead indulge in various kludges to approximate their required functionality.

But that's not a major issue with regard to exception safety. Allocators mostly traffic in raw storage. They are expected to throw an exception if they cannot satisfy an allocation request. They are expected not to throw for any (valid) deallocation request. An allocator is indeed an object. It gets squirreled away within a container when the container is constructed and can never be replaced thereafter. Its constructor and assignment operator can throw an exception and its destructor had better not. Beyond that, I won't go into the numerous subtleties surrounding whether allocators can store values.

A subtler issue is the types that an allocator can define for pointers and references. These include:

pointer
const_pointer
reference
const_reference

The final C++ Standard basically says that these types must correspond to the ordinary pointers and references of C++. It did not always say that. As I mentioned above, I have tried to allow at least for fancier pointers. If you indulge this latitude, however, you'd better be careful. Most of STL assumes that valid operations on iterators, and hence on the pointers they encapsulate, never throw exceptions.

Library Promises

Given the constraints on programmer-defined types outlined above, the Standard C++ library can make a few promises about exception safety. I'll cite chapter and verse from the C++ Standard.

For all containers, clause 23.1 promises the following:

In the last rule, the Compare object is the one whose type I've been calling Mycomp.

Not everybody was happy with this list. Some containers can promise more, without incurring serious overheads. There was strong sentiment for having each container promise as much as possible. Template class list, in particular, has the easiest job of all. It turns out not to be too hard to roll back practically any change to a list, if an exception occurs somewhere in the middle of changing several list elements.

In the end, the C++ Standards committee arrived at what I consider to be a happy compromise. They decided to require template class list to be as predictable as possible, but to impose only the minimum constraints on all other containers. Thus, if you really need a fail-safe container in the presence of exceptions, you'd better make do with a list. Otherwise, you have just the minimum promises outlined above to rely on.

One last item. Some containers, naturally enough, make use of the algorithms defined as part of STL. These are template functions, mostly inhabiting the header <algorithm>, that do all sorts of useful things on sequences of elements. To meet the exception-safety requirements outlined above, some containers have it much easier if three template functions are obliged to be themselves exception safe. These are the functions uninitialized_copy, uninitialized_fill, and uninitialized_fill_n, all defined in the header <utility>. Here's what clause 20.4.4 now says:

All the iterators that are used as formal template parameters in the following algorithms are required to have their operator* return an object for which operator& is defined and returns a pointer to T. In the algorithm uninitialized_copy, the formal template parameter InputIterator is required to satisfy the requirements of an input iterator. In all of the following algorithms, the formal template parameter ForwardIterator is required to satisfy the requirements of a forward iterator and also to satisfy the requirements of a mutable iterator and is required to have the property that no exceptions are thrown from increment, assignment, comparison, or dereference of valid iterators. In the following algorithms, if an exception is thrown there are no effects:

uninitialized_copy
uninitialized_fill
uninitialized_fill_n

To see the effect of this more stringent requirement, see Figures 1 and 2. Figure 1 shows the way these three template functions were once written. Figure 2 shows the new way. I've shown the macros _TRY_BEGIN, etc. in earlier code, so I'll leave it to your imagination to guess what they do here. The basic message is that the logic is messier, but not outrageously complex.

And that is the basic message of exception safety in the Standard C++ library. I believe the payoff in usefulness is well worth the added complexity.

P.J. Plauger is Senior Editor of C/C++ Users Journal and President of Dinkumware, Ltd. He is the author of the Standard C++ Library shipped with Microsoft's Visual C++, v5.0. For eight years, he served as convener of the ISO C standards committee, WG14. He remains active on the C++ committee, J16. 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 pjp@plauger.com.