This is the original GotW problem and solution substantially as posted to Usenet. See the book Exceptional C++ (Addison-Wesley, 2000) for the most current solutions to GotW issues #1-30. The solutions in the book have been revised and expanded since their initial appearance in GotW. The book versions also incorporate corrections, new material, and conformance to the final ANSI/ISO C++ standard. |
CHALLENGE EDITION: Exception Safety
Difficulty: 9 / 10Exceptions can be an elegant solution to some problems, but they introduce many hidden control flows and can be difficult to use correctly. Try your hand at implementing a very simple container (a stack that users can push and pop) and see the issues involved with making it exception-safe and exception-neutral. 
Problem1. Implement the following container to be exception-neutral. Stack objects should always be in a consistent state and destructible even if some internal operations throw, and should allow any T exceptions to propagate through to the caller. template <class T>
// T must have default ctor and copy assignment
class Stack
{
public:
Stack();
~Stack();
Stack(const Stack&);
Stack& operator=(const Stack&);
unsigned Count(); // returns # of T's in the stack
void Push(const T&);
T Pop(); // if empty, returns default-
// constructed T
private:
T* v_; // pointer to a memory area big
// enough for 'vsize_' T objects
unsigned vsize_; // the size of the 'v_' area
unsigned vused_; // the number of T's actually
// used in the 'v_' area
};BONUS QUESTIONS2. Are the standard library containers exception-safe or exception-neutral, according to the current draft? 3. Should containers be exception-neutral? Why or why not? What are the tradeoffs? 4. Should containers use exception specifications? For example, should we declare "Stack::Stack() throw( bad_alloc );"? CHALLENGEWith many current compilers, using "try" and "catch" often adds unnecessary overhead to your programs, which would be nice to avoid in this kind of low-level reusable container. Can you implement all Stack member functions as required without ever using "try" or "catch"? * * * * * * * * * * Here are two example functions (but which do not necessarily meet the requirements) to get you started: template<class T>
Stack<T>::Stack()
: v_(0),
vsize_(10),
vused_(0)
{
v_ = new T[vsize_]; // initial allocation
}
template<class T>
T Stack<T>::Pop()
{
T result; // if empty, return default-constructed T
if( vused_ > 0)
{
result = v_[--vused_];
}
return result;
}
Solution[The solution did turn out to be entirely correct. For an updated and greatly enhanced version of this material, see my September and November/December 1997 C++ Report articles, and further final updates in the book Exceptional C++.] IMPORTANT NOTE: I do not claim that this solution actually meets my original requirements. In fact, I don't have a compiler than can compile it! While I've addressed as many of the interactions as I can think of, a major point of this exercise was to demonstrate that writing exception-safe code requires care. See also Tom Cargill's excellent article,
"Exception Handling: A False Sense of Security" (C++ Report, vol. 9 no. 6, Nov-Dec 1994). He shows that EH is tricky, but please note that his article was probably not meant to dismiss EH in general and people shouldn't get too superstitious about using exceptions. Just be aware, and drive with care. Last note: To keep this solution simpler, I've decided not to demonstrate the base class technique for exception-safe resource ownership. I invite Dave Abrahams (or others) to follow up to this solution and demonstrate this very effective technique. To recap, here's the required interface: template <class T>
// T must have default ctor and copy assignment
class Stack
{
public:
Stack();
~Stack();
Stack(const Stack&);
Stack& operator=(const Stack&);
unsigned Count(); // returns # of T's in the stack
void Push(const T&);
T Pop(); // if empty, returns default-
// constructed T
private:
T* v_; // pointer to a memory area big
// enough for 'vsize_' T objects
unsigned vsize_; // the size of the 'v_' area
unsigned vused_; // the number of T's actually
// used in the 'v_' area
};Now for the implementations. One requirement we will place on T is T dtors must not throw. If dtors may throw, many operations are difficult or impossible to implement safely. //----- DEFAULT CTOR ----------------------------------------------
template<class T>
Stack<T>::Stack()
: v_(new T[10]), // default allocation
vsize_(10),
vused_(0) // nothing used yet
{
// if we got here, the construction was okay
}
//----- COPY CTOR -------------------------------------------------
template<class T>
Stack<T>::Stack( const Stack<T>& other )
: v_(0), // nothing allocated or used yet
vsize_(other.vsize_),
vused_(other.vused_)
{
v_ = NewCopy( other.v_, other.vsize_, other.vsize_ );
// if we got here, the copy construction was okay
}
//----- COPY ASSIGNMENT -------------------------------------------
template<class T>
Stack<T>& Stack<T>::operator=( const Stack<T>& other )
{
if( this != &other )
{
T* v_new = NewCopy( other.v_, other.vsize_, other.vsize_ );
// if we got here, the allocation and copy were okay
delete[] v_;
// note that this cannot throw, since T dtors cannot
// throw and ::operator delete[] is declared as throw()
v_ = v_new;
vsize_ = other.vsize_;
vused_ = other.vused_;
}
return *this; // safe, no copy involved
}
//----- DTOR ------------------------------------------------------
template<class T>
Stack<T>::~Stack()
{
delete[] v_; // again, this can't throw
}
//----- COUNT -----------------------------------------------------
template<class T>
unsigned Stack<T>::Count()
{
return vused_; // it's just a builtin, nothing can go wrong
}
//----- PUSH ------------------------------------------------------
template<class T>
void Stack<T>::Push( const T& t )
{
if( vused_ == vsize_ ) // grow if necessary
{
unsigned vsize_new = (vsize_+1)*2; // grow factor
T* v_new = NewCopy( v_, vsize_, vsize_new );
// if we got here, the allocation and copy were okay
delete[] v_; // again, this can't throw
v_ = v_new;
vsize_ = vsize_new;
}
v_[vused_] = t; // if this copy throws, the increment
++vused_; // isn't done and the state is unchanged
}
//----- POP -------------------------------------------------------
template<class T>
T Stack<T>::Pop()
{
T result;
if( vused_ > 0)
{
result = v_[vused_-1]; // if this copy throws, the
--vused_; // decrement isn't done and
} // the state is unchanged
return result;
}
//
// NOTE: As alert reader Wil Evers was the first to point out,
// "As defined in the challenge, Pop() forces its users to write
// exception-unsafe code, which first causes a side effect
// (popping an element off the stack) and then lets an exception
// escape (copying the return value into [the caller's
// destination object])."
//
// This points out that one reason writing exception-safe
// code is so hard is that it affects not only your
// implementations, but also your interfaces! Some
// interfaces, like this one, can't be implemented in a
// fully exception-safe manner.
//
// One way to correct this one is to respecify the function as
// "void Stack<T>::Pop( T& result)". This way we can know
// the copy to the result has actually succeeded before we
// change the state of the stack. For example, here's an
// alternative version of Pop() that's more exception-safe:
//
template<class T>
void Stack<T>::Pop( T& result )
{
if( vused_ > 0)
{
result = v_[vused_-1]; // if this copy throws, the
--vused_; // decrement isn't done and
} // the state is unchanged
}
//
// Alternatively, we may let Pop() return void and provide a
// Front() member function to access the topmost object.
//
//----- HELPER FUNCTION -------------------------------------------
// When we want to make a (possibly larger) copy of a T buffer,
// this function will allocate the new buffer and copy over the
// original elements. If any exceptions are encountered, the
// function releases all temporary resources and propagates
// the exception so that nothing is leaked.
//
template<class T>
T* NewCopy( const T* src, unsigned srcsize, unsigned destsize )
{
destsize = max( srcsize, destsize ); // basic parm check
T* dest = new T[destsize];
// if we got here, the allocation/ctors were okay
try
{
copy( src, src+srcsize, dest );
}
catch(...)
{
delete[] dest;
throw; // rethrow the original exception
}
// if we got here, the copy was okay
return dest;
}BONUS QUESTIONS2. Are the standard library containers exception-safe or exception-neutral, according to the current draft? This is currently unspecified. Lately there has been some discussion within the committee about whether to provide either weak ("container is always destructible") or strong ("all container operations have commit-or-rollback semantics") exception safety guarantees. As Dave Abrahams has pointed out in that discussion, and since then in email, often the strong guarantee "comes along for free" if you implement the weak guarantee. This is the case with several operations above. 3. Should containers be exception-neutral? Why or why not? What are the tradeoffs? Some containers have operations with unavoidable space tradeoffs if they are to be made exception-neutral. Exception-neutrality is a Good Thing in itself, but may not be practical when implementing the strong guarantee requires much more space or time than does implementing the weak guarantee. Often a good compromise is to document which T operations are expected not to throw and then guarantee exception-neutrality based on conformance to those assumptions. 4. Should containers use exception specifications? For example, should we declare "Stack::Stack() throw( bad_alloc );"? No, since it is unknown in advance which T operations might throw or what they might throw. Notice that some container operations (e.g., Count()) simply return a scalar and are known not to throw. While it's possible to declare these with "throw()", there are two possible reasons why you wouldn't: first, it limits you in the future in case you want to change the underlying implementation to a form which could throw; and second, exception specifications incur a performance overhead whether an exception is thrown or not. For widely-used operations, it may be better not to use exception specifications to avoid this overhead. CHALLENGEWith many current compilers, using "try" and "catch" often adds unnecessary overhead to your programs, which would be nice to avoid in this kind of low-level reusable container. Can you implement all Stack member functions as required without ever using "try" or "catch"? Yes, because we only care about catching "...". In general, code of the form try { TryCode(); } catch(...) { CatchCode(parms); throw; }can be rewritten as struct Janitor {
Janitor(Parms p) : pa(p) {}
~Janitor() { if uncaught_exception() CatchCode(pa); }
Parms pa;
};
{
Janitor j(parms); // j is destroyed both if TryCode()
// succeeds and if it throws
TryCode();
}Our solution uses try/catch only in the NewCopy function, so let's illustrate this technique by rewriting NewCopy: template<class T>
T* NewCopy( const T* src, unsigned srcsize, unsigned destsize )
{
destsize = max( srcsize, destsize ); // basic parm check
struct Janitor {
Janitor( T* p ) : pa(p) {}
~Janitor() { if( uncaught_exception() ) delete[] pa; }
T* pa;
};
T* dest = new T[destsize];
// if we got here, the allocation/ctors were okay
Janitor j(dest);
copy( src, src+srcsize, dest );
// if we got here, the copy was okay... otherwise, j
// was destroyed during stack unwinding and will handle
// the cleanup of dest to avoid leaking memory
return dest;
}Having said that, I've now talked to several people who've done empirical speed tests. In the case when no exception occurs, try/catch is usually much faster, and can be expected to continue to be faster. However, it is still important to know about this kind of technique because it often yields more elegant and maintainable code, and because some current compilers still produce extremely inefficient code for try/catch in both the exceptional and exception-free code paths. | 
