samien
/
boost
의 미러 https://github.com/boostorg/boost


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684
							<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0052)http://people.ne.mediaone.net/abrahams/abrahams.html -->

    <meta name="generator" content="Microsoft FrontPage 5.0">
    <title>Exception-Safety in Generic Components</title>
    <meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
    <meta content="MSHTML 5.50.4522.1800" name="GENERATOR">

    <h1 align="center">Exception-Safety in Generic Components</h1>

    <p align="center"><i><b>Lessons Learned from Specifying Exception-Safety
    for the C++ Standard Library</b></i>

    <h3 align="center">David Abrahams</h3>

    <h3 align="center"><a href="mailto:david.abrahams@rcn.com">
    david.abrahams@rcn.com</a></h3>

    <p><b>Abstract.</b> This paper represents the knowledge accumulated in
    response to a real-world need: that the C++ Standard Template Library
    exhibit useful and well-defined interactions with exceptions, the
    error-handling mechanism built-in to the core C++ language. It explores the
    meaning of exception-safety, reveals surprising myths about exceptions and
    genericity, describes valuable tools for reasoning about program
    correctness, and outlines an automated testing procedure for verifying
    exception-safety.

    <p><b>Keywords:</b> exception-safety, exceptions, STL, C++

    <h2>1 What is exception-safety?</h2>

    <p>Informally, exception-safety in a component means that it exhibits
    reasonable behavior when an exception is thrown during its execution. For
    most people, the term ``reasonable'' includes all the usual
    expectations for error-handling: that resources should not be leaked, and
    that the program should remain in a well-defined state so that execution
    can continue. For most components, it also includes the expectation that
    when an error is encountered, it is reported to the caller.

    <p>More formally, we can describe a component as minimally exception-safe
    if, when exceptions are thrown from within that component, its invariants
    are intact. Later on we'll see that at least three different levels of
    exception-safety can be usefully distinguished. These distinctions can help
    us to describe and reason about the behavior of large systems.

    <p>In a generic component, we usually have an additional expectation of
    <i>exception-neutrality</i>, which means that exceptions thrown by a
    component's type parameters should be propagated, unchanged, to the
    component's caller.

    <h2>2 Myths and Superstitions</h2>

    <p>Exception-safety seems straightforward so far: it doesn't constitute
    anything more than we'd expect from code using more traditional
    error-handling techniques. It might be worthwhile, however, to examine the
    term from a psychological viewpoint. Nobody ever spoke of
    ``error-safety'' before C++ had exceptions.

    <p>It's almost as though exceptions are viewed as a <i>mysterious
    attack</i> on otherwise correct code, from which we must protect ourselves.
    Needless to say, this doesn't lead to a healthy relationship with error
    handling! During standardization, a democratic process which requires broad
    support for changes, I encountered many widely-held superstitions. In order
    to even begin the discussion of exception-safety in generic components, it
    may be worthwhile confronting a few of them.

    <p><i>``Interactions between templates and exceptions are not
    well-understood.''</i> This myth, often heard from those who consider
    these both new language features, is easily disposed of: there simply are
    no interactions. A template, once instantiated, works in all respects like
    an ordinary class or function. A simple way to reason about the behavior of
    a template with exceptions is to think of how a specific instantiation of
    that template works. Finally, the genericity of templates should not cause
    special concern. Although the component's client supplies part of the
    operation (which may, unless otherwise specified, throw arbitrary
    exceptions), the same is true of operations using familiar virtual
    functions or simple function pointers.

    <p><i>``It is well known to be impossible to write an exception-safe
    generic container.''</i> This claim is often heard with reference to
    an article by Tom Cargill <a title=
    "Tom Cargill, ``Exception Handling: A False Sense of Security'', C++ Report, Nov-Dec 1994"
     href=
    "#reference4"><sup>[4]</sup></a>
    in which he explores the problem of exception-safety for a generic stack
    template. In his article, Cargill raises many useful questions, but
    unfortunately fails to present a solution to his problem.<a title=
    "Probably the greatest impediment to a solution in Cargill's case was an unfortunate combination of choices on his part: the interface he chose for his container was incompatible with his particular demands for safety. By changing either one he might have solved the problem."
     href=
    "#footnote1"><sup>1</sup></a>
    He concludes by suggesting that a solution may not be possible.
    Unfortunately, his article was read by many as ``proof'' of that
    speculation. Since it was published there have been many examples of
    exception-safe generic components, among them the C++ standard library
    containers.

    <p><i>``Dealing with exceptions will slow code down, and templates are
    used specifically to get the best possible performance.''</i> A good
    implementation of C++ will not devote a single instruction cycle to dealing
    with exceptions until one is thrown, and then it can be handled at a speed
    comparable with that of calling a function <a title=
    "D. R. Musser, ``Introspective Sorting and Selection Algorithms'', Software-Practice and Experience 27(8):983-993, 1997."
     href=
    "#reference7"><sup>[7]</sup></a>.
    That alone gives programs using exceptions performance equivalent to that
    of a program which ignores the possibility of errors. Using exceptions can
    actually result in faster programs than ``traditional'' error
    handling methods for other reasons. First, a catch block clearly indicates
    to the compiler which code is devoted to error-handling; it can then be
    separated from the usual execution path, improving locality of reference.
    Second, code using ``traditional'' error handling must typically
    test a return value for errors after every single function call; using
    exceptions completely eliminates that overhead.

    <p><i>``Exceptions make it more difficult to reason about a program's
    behavior.''</i> Usually cited in support of this myth is the way
    ``hidden'' execution paths are followed during stack-unwinding.
    Hidden execution paths are nothing new to any C++ programmer who expects
    local variables to be destroyed upon returning from a function:

    <blockquote>
<pre>ErrorCode f( int&amp; result )         // 1 
{                                  // 2 
    X x;                           // 3 
    ErrorCode err = x.g( result ); // 4 
    if ( err != kNoError )         // 5 
        return err;                // 6 
    // ...More code here... 
    return kNoError;               // 7 
}
</pre>
    </blockquote>

    <p>In the example above, there is a ``hidden'' call to
    <code>X::~X()</code> in lines 6 and 7. Granted, using exceptions, there is
    no code devoted to error handling visible:

    <blockquote>
<pre>int f()                 // 1 
{                       // 2 
    X x;                // 3 
    int result = x.g(); // 4 
    // ...More code here... 
    return result;      // 5 
} 
</pre>
    </blockquote>

    <p>For many programmers more familiar with exceptions, the second example
    is actually more readable and understandable than the first. The
    ``hidden'' code paths include the same calls to destructors of
    local variables. In addition, they follow a simple pattern which acts
    <i>exactly</i> as though there were a potential return statement after each
    function call in case of an exception. Readability is enhanced because the
    normal path of execution is unobscured by error-handling, and return values
    are freed up to be used in a natural way.

    <p>There is an even more important way in which exceptions can enhance
    correctness: by allowing simple class invariants. In the first example, if
    <code>x</code>'s constructor should need to allocate resources, it has no
    way to report a failure: in C++, constructors have no return values. The
    usual result when exceptions are avoided is that classes requiring
    resources must include a separate initializer function which finishes the
    job of construction. The programmer can therefore never be sure, when an
    object of class <code>X</code> is used, whether he is handling a
    full-fledged <code>X</code> or some abortive attempt to construct one (or
    worse: someone simply forgot to call the initializer!)

    <h2>3 A contractual basis for exception-safety</h2>

    <p>A non-generic component can be described as exception-safe in isolation,
    but because of its configurability by client code, exception-safety in a
    generic component usually depends on a contract between the component and
    its clients. For example, the designer of a generic component might require
    that an operation which is used in the component's destructor not throw any
    exceptions.<a title=
    " It is usually inadvisable to throw an exception from a destructor in C++, since the destructor may itself be called during the stack-unwinding caused by another exception. If the second exception is allowed to propagate beyond the destructor, the program is immediately terminated."
     href=
    "#footnote2"><sup>2</sup></a>
    The generic component might, in return, provide one of the following
    guarantees:

    <ul>
      <li>The <i>basic</i> guarantee: that the invariants of the component are
      preserved, and no resources are leaked.

      <li>The <i>strong</i> guarantee: that the operation has either completed
      successfully or thrown an exception, leaving the program state exactly as
      it was before the operation started.

      <li>The <i>no-throw</i> guarantee: that the operation will not throw an
      exception.
    </ul>

    <p>The basic guarantee is a simple minimum standard for exception-safety to
    which we can hold all components. It says simply that after an exception,
    the component can still be used as before. Importantly, the preservation of
    invariants allows the component to be destroyed, potentially as part of
    stack-unwinding. This guarantee is actually less useful than it might at
    first appear. If a component has many valid states, after an exception we
    have no idea what state the component is in|only that the state is valid.
    The options for recovery in this case are limited: either destruction or
    resetting the component to some known state before further use. Consider
    the following example:

    <blockquote>
<pre>template &lt;class X&gt; 
void print_random_sequence() 
{ 
    std::vector&lt;X&gt; v(10); // A vector of 10 items 
    try { 
        // Provides only the <i>basic</i> guarantee 
        v.insert( v.begin(), X() ); 
    } 
    catch(...) {} // ignore any exceptions above 
    // print the vector's contents 
    std::cout "(" &lt;&lt; v.size() &lt;&lt; ") "; 
    std::copy( v.begin(), v.end(), 
    std::ostream_iterator&lt;X&gt;( std::cout, " " ) ); 
} 
</pre>
    </blockquote>

    <p>Since all we know about v after an exception is that it is valid, the
    function is allowed to print any random sequence of <code>X</code>s.<a
    title=
    "In practice of course, this function would make an extremely poor random sequence generator!"
     href=
    "#footnote3"><sup>3</sup></a>
    It is ``safe'' in the sense that it is not allowed to crash, but
    its output may be unpredictable.

    <p>The <i>strong</i> guarantee provides full
    ``commit-or-rollback'' semantics. In the case of C++ standard
    containers, this means, for example, that if an exception is thrown all
    iterators remain valid. We also know that the container has exactly the
    same elements as before the exception was thrown. A transaction that has no
    effects if it fails has obvious benefits: the program state is simple and
    predictable in case of an exception. In the C++ standard library, nearly
    all of the operations on the node-based containers list, set, multiset,
    map, and multimap provide the <i>strong</i> guarantee.<a title=
    "It is worth noting that mutating algorithms usually cannot provide the strong guarantee: to roll back a modified element of a range, it must be set back to its previous value using operator=, which itself might throw. In the C++ standard library, there are a few exceptions to this rule, whose rollback behavior consists only of destruction: uninitialized_copy, uninitialized_fill, and uninitialized_fill_n."
     href=
    "#footnote4"><sup>4</sup></a>).

    <p>The <i>no-throw</i> guarantee is the strongest of all, and it says that
    an operation is guaranteed not to throw an exception: it always completes
    successfully. This guarantee is necessary for most destructors, and indeed
    the destructors of C++ standard library components are all guaranteed not
    to throw exceptions. The <i>no-throw</i> guarantee turns out to be
    important for other reasons, as we shall see.<a title=
    "All type parameters supplied by clients of the C++ standard library are required not to throw from their destructors. In return, all components of the C++ standard library provide at least the basic guarantee."
     href=
    "#footnote5"><sup>5</sup></a>

    <h2>4 Legal Wrangling</h2>

    <p>Inevitably, the contract can get more complicated: a quid pro quo
    arrangement is possible. Some components in the C++ Standard Library give
    one guarantee for arbitrary type parameters, but give a stronger guarantee
    in exchange for additional promises from the client type that no exceptions
    will be thrown. For example, the standard container operation
    <code>vector&lt;T&gt;::erase</code> gives the <i>basic</i> guarantee for
    any <code>T</code>, but for types whose copy constructor and copy
    assignment operator do not throw, it gives the <i>no-throw</i> guarantee.<a
    title=
    "Similar arrangements might have been made in the C++ standard for many of the mutating algorithms, but were never considered due to time constraints on the standardization process."
     href=
    "#footnote6"><sup>6</sup></a>

    <h2>5 What level of exception-safety should a component specify?</h2>

    <p>From a client's point-of-view, the strongest possible level of safety
    would be ideal. Of course, the <i>no-throw</i> guarantee is simply
    impossible for many operations, but what about the <i>strong</i> guarantee?
    For example, suppose we wanted atomic behavior for
    <code>vector&lt;T&gt;::insert</code>. Insertion into the middle of a vector
    requires copying elements after the insertion point into later positions,
    to make room for the new element. If copying an element can fail, rolling
    back the operation would require ``undoing'' the previous
    copies...which depends on copying again. If copying back should fail (as it
    likely would), we have failed to meet our guarantee.

    <p>One possible alternative would be to redefine <code>insert</code> to
    build the new array contents in a fresh piece of memory each time, and only
    destroy the old contents when that has succeeded. Unfortunately, there is a
    non-trivial cost if this approach is followed: insertions near the end of a
    vector which might have previously caused only a few copies would now cause
    every element to be copied. The <i>basic</i> guarantee is a
    ``natural'' level of safety for this operation, which it can
    provide without violating its performance guarantees. In fact all of the
    operations in the library appear to have such a ``natural'' level
    of safety.

    <p>Because performance requirements were already a well-established part of
    the draft standard and because performance is a primary goal of the STL,
    there was no attempt to specify more safety than could be provided within
    those requirements. Although not all of the library gives the <i>strong</i>
    guarantee, almost any operation on a standard container which gives the
    <i>basic</i> guarantee can be made <i>strong</i> using the ``make a
    new copy'' strategy described above:

    <blockquote>
<pre>template &lt;class Container, class BasicOp&gt; 
void MakeOperationStrong( Container&amp; c, const BasicOp&amp; op ) 
{ 
    Container tmp(c); // Copy c 
    op(tmp); // Work on the copy 
    c.swap(tmp); // Cannot fail<a title=
"Associative containers whose Compare object might throw an exception when copied cannot use this technique, since the swap function might fail."
 href=
"#footnote7"><sup>7</sup></a>
}
</pre>
    </blockquote>

    <p>This technique can be folded into a wrapper class to make a similar
    container which provides stronger guarantees (and different performance
    characteristics).<a title=
    "This suggests another potential use for the oft-wished-for but as yet unseen container traits&lt;&gt; template: automated container selection to meet exceptionsafety constraints."
     href=
    "#footnote8"><sup>8</sup></a>

    <h2>6 Should we take everything we can get?</h2>

    <p>By considering a particular implementation, we can hope to discern a
    natural level of safety. The danger in using this to establish requirements
    for a component is that the implementation might be restricted. If someone
    should come up with a more-efficient implementation which we'd like to use,
    we may find that it's incompatible with our exception-safety requirements.
    One might expect this to be of no concern in the well-explored domains of
    data structures and algorithms covered by the STL, but even there, advances
    are being made. A good example is the recent <i>introsort</i> algorithm <a
    title=
    "D. R. Musser, ``Introspective Sorting and Selection Algorithms'', Software-Practice and Experience 27(8):983-993, 1997."
     href=
    "#reference6"><sup>[6]</sup></a>,
    which represents a substantial improvement in worst-case complexity over
    the well-established <i>quicksort</i>.

    <p>To determine exactly how much to demand of the standard components, I
    looked at a typical real-world scenario. The chosen test case was a
    ``composite container.'' Such a container, built of two or more
    standard container components, is not only commonly needed, but serves as a
    simple representative case for maintaining invariants in larger systems:

    <blockquote>
<pre>// SearchableStack - A stack which can be efficiently searched 
// for any value. 
template &lt;class T&gt; 
class SearchableStack 
{ 
 public: 
    void push(const T&amp; t); // O(log n) 
    void pop(); // O(log n) 
    bool contains(const T&amp; t) const; // O(log n) 
    const T&amp; top() const; // O(1) 
 private: 
    std::set&lt;T&gt; set_impl; 
    std::list&lt;std::set&lt;T&gt;::iterator&gt; list_impl; 
}; 
</pre>
    </blockquote>

    <p>The idea is that the list acts as a stack of set iterators: every
    element goes into the set first, and the resulting position is pushed onto
    the list. The invariant is straightforward: the set and the list should
    always have the same number of elements, and every element of the set
    should be referenced by an element of the list. The following
    implementation of the push function is designed to give the <i>strong</i>
    guarantee within the natural levels of safety provided by set and list:

    <blockquote>
<pre>template &lt;class T&gt;                                // 1 
void SearchableStack&lt;T&gt;::push(const T&amp; t)         // 2 
{                                                       // 3 
    set&lt;T&gt;::iterator i = set_impl.insert(t);      // 4 
    try                                                 // 5 
    {                                                   // 6 
        list_impl.push_back(i);                         // 7 
    }                                                   // 8 
    catch(...)                                          // 9 
    {                                                   // 10 
        set_impl.erase(i);                              // 11 
        throw;                                          // 12 
    }                                                   // 13 
}                                                       // 14 
</pre>
    </blockquote>

    <p>What does our code actually require of the library? We need to examine
    the lines where non-const operations occur:

    <ul>
      <li>Line 4: if the insertion fails but <code>set_impl</code> is modified
      in the process, our invariant is violated. We need to be able to rely on
      the <i>strong</i> guarantee from <code>set&lt;T&gt;::insert</code>.

      <li>Line 7: likewise, if <code>push_back</code> fails, but
      <code>list_impl</code> is modified in the process, our invariant is
      violated, so we need to be able to rely on the <i>strong</i> guarantee
      from list&lt;T&gt;::insert.

      <li>Line 11: here we are ``rolling back'' the insertion on line
      4. If this operation should fail, we will be unable to restore our
      invariant. We absolutely depend on the <i>no-throw</i> guarantee from
      <code>set&lt;T&gt;::erase</code>.<a title=
      "One might be tempted to surround the erase operation with a try/catch block to reduce the requirements on set&lt;T&gt; and the problems that arise in case of an exception, but in the end that just begs the question. First, erase just failed and in this case there are no viable alternative ways to produce the necessary result. Second and more generally, because of the variability of its type parameters a generic component can seldom be assured that any alternatives will succeed."
       href=
      "#footnote9"><sup>9</sup></a>

      <li>Line 11: for the same reasons, we also depend on being able to pass
      the <code>i</code> to the <code>erase</code> function: we need the
      <i>no-throw</i> guarantee from the copy constructor of
      <code>set&lt;T&gt;::iterator</code>.
    </ul>

    <p>I learned a great deal by approaching the question this way during
    standardization. First, the guarantee specified for the composite container
    actually depends on stronger guarantees from its components (the
    <i>no-throw</i> guarantees in line 11). Also, I took advantage of all of
    the natural level of safety to implement this simple example. Finally, the
    analysis revealed a requirement on iterators which I had previously
    overlooked when operations were considered on their own. The conclusion was
    that we should provide as much of the natural level of safety as possible.
    Faster but less-safe implementations could always be provided as extensions
    to the standard components. <sup><a title=
    "The prevalent philosophy in the design of STL was that functionality that wasn't essential to all uses should be left out in favor of efficiency, as long as that functionality could be obtained when needed by adapting the base components. This departs from that philosophy, but it would be difficult or impossible to obtain even the basic guarantee by adapting a base component that doesn't already have it."
     name="#footnote10">10</a></sup>

    <h2>7 Automated testing for exception-safety</h2>

    <p>As part of the standardization process, I produced an exception-safe
    reference implementation of the STL. Error-handling code is seldom
    rigorously tested in real life, in part because it is difficult to cause
    error conditions to occur. It is very common to see error-handling code
    which crashes the first time it is executed ...in a shipping product! To
    bolster confidence that the implementation actually worked as advertised, I
    designed an automated test suite, based on an exhaustive technique due to
    my colleague Matt Arnold.

    <p>The test program started with the basics: reinforcement and
    instrumentation, especially of the global operators <code>new</code> and
    <code>delete</code>.<sup><a title=
    "An excellent discussion on how to fortify memory subsystems can be found in: Steve Maguire, Writing Solid Code, Microsoft Press, Redmond, WA, 1993, ISBN 1-55615- 551-4."
     name="#footnote11">11</a></sup>Instances of the components (containers and
    algorithms) were created, with type parameters chosen to reveal as many
    potential problems as possible. For example, all type parameters were given
    a pointer to heap-allocated memory, so that leaking a contained object
    would be detected as a memory leak.

    <p>Finally, a scheme was designed that could cause an operation to throw an
    exception at each possible point of failure. At the beginning of every
    client-supplied operation which is allowed to throw an exception, a call to
    <code>ThisCanThrow</code> was added. A call to <code>ThisCanThrow</code>
    also had to be added everywhere that the generic operation being tested
    might throw an exception, for example in the global operator
    <code>new</code>, for which an instrumented replacement was supplied.

    <blockquote>
<pre>// Use this as a type parameter, e.g. vector&lt;TestClass&gt; 
struct TestClass 
{ 
    TestClass( int v = 0 ) 
        : p( ThisCanThrow(), new int( v ) ) {} 
    TestClass( const TestClass&amp; rhs ) 
        : p( ThisCanThrow(), new int( *rhs.p ) ) {} 
    const TestClass&amp; operator=( const TestClass&amp; rhs ) 
        { ThisCanThrow(); *p = *rhs.p; } 
    bool operator==( const TestClass&amp; rhs ) 
        { ThisCanThrow(); return *p == *rhs.p; } 
    ...etc... 
    ~TestClass() { delete p; } 
};
</pre>
    </blockquote>

    <p><code>ThisCanThrow</code> simply decrements a ``throw
    counter'' and, if it has reached zero, throws an exception. Each test
    takes a form which begins the counter at successively higher values in an
    outer loop and repeatedly attempts to complete the operation being tested.
    The result is that the operation throws an exception at each successive
    step along its execution path that can possibly fail. For example, here is
    a simplified version of the function used to test the <i>strong</i>
    guarantee: <a title=
    "Note that this technique requires that the operation being tested be exception-neutral. If the operation ever tries to recover from an exception and proceed, the throw counter will be negative, and subsequent operations that might fail will not be tested for exception-safety."
     href=
    "#footnote12"><sup>12</sup></a>

    <blockquote>
<pre>extern int gThrowCounter; // The throw counter
void ThisCanThrow() 
{ 
    if (gThrowCounter-- == 0) 
        throw 0; 
} 
 
template &lt;class Value, class Operation&gt; 
void StrongCheck(const Value&amp; v, const Operation&amp; op) 
{ 
    bool succeeded = false; 
    for (long nextThrowCount = 0; !succeeded; ++nextThrowCount) 
    { 
        Value duplicate = v; 
        try 
        { 
            gThrowCounter = nextThrowCount; 
            op( duplicate ); // Try the operation 
            succeeded = true; 
        } 
        catch(...) // Catch all exceptions 
        { 
            bool unchanged = duplicate == v; // Test <i>strong</i> guarantee 
            assert( unchanged ); 
        } 
        // Specialize as desired for each container type, to check 
        // integrity. For example, size() == distance(begin(),end()) 
        CheckInvariant(v); // Check any invariant 
    } 
}
</pre>
    </blockquote>

    <p>Notably, this kind of testing is much easier and less intrusive with a
    generic component than with non-generics, because testing-specific type
    parameters can be used without modifying the source code of the component
    being tested. Also, generic functions like <code>StrongCheck</code> above
    were instrumental in performing the tests on a wide range of values and
    operations.

    <h2>8 Further Reading</h2>
    To my knowledge, there are currently only two descriptions of STL
    exception-safety available. The original specification <a title=
    "D. Abrahams, Exception Safety in STLport" href=
    "#reference2"><sup>[2]</sup></a>
    for the reference exception-safe implementation of the STL is an informal
    specification, simple and self-explanatory (also verbose), and uses the
    <i>basic-</i> and <i>strong-</i>guarantee distinctions outlined in this
    article. It explicitly forbids leaks, and differs substantively from the
    final C++ standard in the guarantees it makes, though they are largely
    identical. I hope to produce an updated version of this document soon. 

    <p>The description of exception-safety in the C++ Standard <a title=
    "International Standard ISO/IEC 14882, Information Technology-Programming Languages-C++, Document Number ISO/IEC 14882-1998"
     href=
    "#reference1"><sup>[1]</sup></a>
    is only slightly more formal, but relies on hard-to-read
    ``standardese'' and an occasionally subtle web of implication.<a
    title=
    "The changes to the draft standard which introduced exception-safety were made late in the process, when amendments were likely to be rejected solely on the basis of the number of altered words. Unfortunately, the result compromises clarity somewhat in favor of brevity. Greg Colvin was responsible for the clever language-lawyering needed to minimize the extent of these changes."
     href=
    "#footnote13"><sup>13</sup></a>
    In particular, leaks are not treated directly at all. It does have the
    advantage that it <i>is</i> the standard.

    <p>The original reference implementation <a title=
    "B. Fomitchev, Adapted SGI STL Version 1.0, with exception handling code by D. Abrahams"
     href=
    "#reference5"><sup>[5]</sup></a>
    of the exception-safe STL is an adaptation of an old version of the SGI
    STL, designed for C++ compilers with limited features. Although it is not a
    complete STL implementation, the code may be easier to read, and it
    illustrates a useful base-class technique for eliminating
    exception-handling code in constructors. The full test suite <a title=
    "D. Abrahams and B. Fomitchev, Exception Handling Test Suite" href=
    "#reference3"><sup>[3]</sup></a>
    used to validate the reference implementation has been used successfully to
    validate all recent versions of the SGI STL, and has been adapted to test
    one other vendor's implementation (which failed). As noted on the
    documentation page, it also seems to have the power to reveal hidden
    compiler bugs, particularly where optimizers interact with
    exception-handling code.

    <h2>References</h2>

    <ol>
      <li><a name="reference1">International</a> Standard ISO/IEC 14882,
      <i>Information Technology-Programming Languages-C++</i>, Document Number
      ISO/IEC 14882-1998, available from <a href=
      "http://webstore.ansi.org/ansidocstore/default.asp">http://webstore.ansi.org/ansidocstore/default.asp</a>.

      <li><a name="reference2">D.</a> Abrahams, <i>Exception Safety in
      STLport</i>, available at <a href=
      "http://www.stlport.org/doc/exception_safety.html">http://www.stlport.org/doc/exception_safety.html</a>.

      <li><a name="reference3">D.</a> Abrahams and B. Fomitchev, <i>Exception
      Handling Test Suite</i>, available at <a href=
      "http://www.stlport.org/doc/eh_testsuite.html">http://www.stlport.org/doc/eh_testsuite.html</a>.

      <li><a name="reference4">Tom</a> Cargill, ``Exception Handling:
      A False Sense of Security,'' C++ Report, Nov-Dec 1994, also
      available at <a href=
      "http://www.awprofessional.com/content/images/020163371x/supplements/Exception_Handling_Article.html">http://www.awprofessional.com/content/images/020163371x/supplements/Exception_Handling_Article.html</a>.

      <li><a name="reference5">B.</a> Fomitchev, <i>Adapted SGI STL Version
      1.0</i>, with exception handling code by D. Abrahams, available at <a
      href=
      "http://www.metabyte.com/~fbp/stl/old.html">http://www.metabyte.com/~fbp/stl/old.html</a>.

      <li><a name="reference6">D.</a> R. Musser, ``Introspective Sorting
      and Selection Algorithms,'' <i>Software-Practice and Experience</i>
      27(8):983-993, 1997.

      <li><a name="reference7">Bjarne</a> Stroustrup, <i>The Design And
      Evolution of C++</i>. Addison Wesley, Reading, MA, 1995, ISBN
      0-201-54330-3, Section 16.9.1.
    </ol>

    <h2>Footnotes</h2>

    <p><a name="footnote1">1</a> Probably the greatest impediment to a solution
    in Cargill's case was an unfortunate combination of choices on his part:
    the interface he chose for his container was incompatible with his
    particular demands for safety. By changing either one he might have solved
    the problem.

    <p><a name="footnote2">2</a> It is usually inadvisable to throw an
    exception from a destructor in C++, since the destructor may itself be
    called during the stack-unwinding caused by another exception. If the
    second exception is allowed to propagate beyond the destructor, the program
    is immediately terminated.

    <p><a name="footnote3">3</a> In practice of course, this function would
    make an extremely poor random sequence generator!

    <p><a name="footnote4">4</a> It is worth noting that mutating algorithms
    usually cannot provide the <i>strong</i> guarantee: to roll back a modified
    element of a range, it must be set back to its previous value using
    <code>operator=</code>, which itself might throw. In the C++ standard
    library, there are a few exceptions to this rule, whose rollback behavior
    consists only of destruction: <code>uninitialized_copy</code>,
    <code>uninitialized_fill</code>, and <code>uninitialized_fill_n</code>.

    <p><a name="footnote5">5</a> All type parameters supplied by clients of the
    C++ standard library are required not to throw from their destructors. In
    return, all components of the C++ standard library provide at least the
    <i>basic</i> guarantee.

    <p><a name="footnote6">6</a> Similar arrangements might have been made in
    the C++ standard for many of the mutating algorithms, but were never
    considered due to time constraints on the standardization process.

    <p><a name="footnote7">7</a> Associative containers whose
    <code>Compare</code> object might throw an exception when copied cannot use
    this technique, since the swap function might fail.

    <p><a name="footnote8">8</a> This suggests another potential use for the
    oft-wished-for but as yet unseen <code>container_traits&lt;&gt;</code>
    template: automated container selection to meet exception-safety
    constraints.

    <p><a name="footnote9">9</a> One might be tempted to surround the erase
    operation with a <code>try</code>/<code>catch</code> block to reduce the
    requirements on <code>set&lt;T&gt;</code> and the problems that arise in
    case of an exception, but in the end that just begs the question. First,
    erase just failed and in this case there are no viable alternative ways to
    produce the necessary result. Second and more generally, because of the
    variability of its type parameters a generic component can seldom be
    assured that any alternatives will succeed.

    <p><a name="footnote10">10</a> The prevalent philosophy in the design of
    STL was that functionality that wasn't essential to all uses should be left
    out in favor of efficiency, as long as that functionality could be obtained
    when needed by adapting the base components. This departs from that
    philosophy, but it would be difficult or impossible to obtain even the
    <i>basic</i> guarantee by adapting a base component that doesn't already
    have it.

    <p><a name="footnote11">11</a> An excellent discussion on how to fortify
    memory subsystems can be found in: Steve Maguire, Writing Solid Code,
    Microsoft Press, Redmond, WA, 1993, ISBN 1-55615- 551-4.

    <p><a name="footnote12">12</a> Note that this technique requires that the
    operation being tested be exception-neutral. If the operation ever tries to
    recover from an exception and proceed, the throw counter will be negative,
    and subsequent operations that might fail will not be tested for
    exception-safety.

    <p><a name="footnote13">13</a> The changes to the draft standard which
    introduced exception-safety were made late in the process, when amendments
    were likely to be rejected solely on the basis of the number of altered
    words. Unfortunately, the result compromises clarity somewhat in favor of
    brevity. Greg Colvin was responsible for the clever language-lawyering
    needed to minimize the extent of these changes.