TITLE: exception safety in standard containers

C++ Newsletter #030 - December 1997

Issue #030
December, 1997


Contents:

Introduction to C++ Libraries Part 3 - numeric_limits
Notes From ANSI/ISO - Exception Safety in Containers, Part 2
Introduction to Object-oriented Design Part 9 - Templates vs. Classes


INTRODUCTION TO C++ LIBRARIES PART 3 - NUMERIC_LIMITS

[snip]

NOTES FROM ANSI/ISO - EXCEPTION SAFETY IN CONTAINERS,
PART 2

Jonathan Schilling, jls@sco.com

In the previous issue we mentioned that one of the best improvements made to
the standard over the last two meetings has been the requirement that
standard library containers exhibit certain levels of exception safety. 

Here's an example of what that means, using lists and vectors (C++
Newsletter #015):

        #include <iostream>
        #include <list>

        using namespace std;

        class A {
        public:
                A(int i) { n = i; }
        #if CCTOR
                A(const A& a) { 
                        if (a.n < 6) 
                                n = a.n; 
                        else 
                                throw "too large";
                }
        #endif
                int get() const { return n; }
        private:
                int n;
        };

        int main() {
                list<A> la;
                la.push_back(A(0));  la.push_back(A(1));
                
                typedef list<A>::iterator LI;

                try {
                        for (int i = 2; i < 10; i++) {
                                LI li = la.begin();  li++;
                                la.insert(li, A(i));
                        }
                } catch (const char* s) { }
                        
                // what does la contain now?
                for (LI i = la.begin(); i != la.end(); i++)
                        cout << i->get();
                cout << endl;
        }

The list initially has two elements, and then we insert a series of elements
before the second element position. When compiled without any user-supplied
copy constructor, the output is: 

        0987654321

What happens when we compile with CCTOR defined? We have supplied a copy
constructor which throws an exception for element 6. This copy constructor
is called by the library container implementation when elements are copied
into the container. What is the state of the container when the copy
construction for element 6 throws an exception? 

Prior to the recent changes to the standard, the results of this were
completely undefined. After the exception was caught the list might be intact
or not; the iterator operations on it might work or not; there might be fewer
or no elements still in the list; or the destruction of the list object at
the end of main() might cause a core dump. 

However, now the standard states that the insert() operation that causes the
throw will have no effect, and guarantees that the output will be: 

        054321

which is what it was before the insert() that threw began. In other words,
list insert is done with "commit or rollback" semantics. 

Now, let's take the above example and use a vector rather than a list. (This
can be done by simply editing the three text occurrences of "list" to
"vector"). 

Without the copy constructor, we get the same output as for list: 

        0987654321

But with the copy constructor included via defining CCTOR, we get: 

        0543211

which looks like a "wrong" value (there's an extra 1). What happened? 

Remember in the previous issue we talked about two levels of guarantees in
terms of exception safety in containers. The stronger level is the
commit-or-rollback level, and is required for most operations on lists,
maps, and sets. The weaker level doesn't guarantee the contents of the
container, but does guarantee that the container will be well-formed (for
example, you can iterate through it and destruct it). This weaker level is
all that is required of most operations on vectors and deques. 

The basic rationale for the difference is to permit efficient implementation.
The first group of containers are typically "node- based", meaning elements
of a container are allocated in separate nodes that are linked together,
while the second group of containers are "array-based", meaning elements of
a container are allocated in contiguous storage. It's a lot easier to provide
commit-or-rollback semantics on node-based containers than array-based ones;
hence the two levels of guarantees. 

So, while the above example for vectors is guaranteed to execute to completion,there's no way of knowing what the output will be. (The "0543211" output comes
from the Silicon Graphics free STL, and looks to be the result of a partial
resizing or copying operation; another STL implementation might produce an
entirely different result). 

There are some special cases to the general description of the two levels of
guarantees above. For instance: multiple element insertion operations on maps
and sets do not have the first level guarantee. Insertions of PODs - plain
old C-level structs - for vectors and deques do have it. Stacks and queues
have it as well. Thus for complete details you'll have to check the standard
or a reference book. 

In conclusion, the basic benefit of all this is that if you have classes that
use exception handling, you can put them into standard library containers and
get reasonable and useful behavior in the event an exception is thrown. 

INTRODUCTION TO OBJECT-ORIENTED DESIGN PART 9 -
TEMPLATES VS. CLASSES

[snip]

ACKNOWLEDGEMENTS

Thanks to Nathan Myers, Eric Nagler, David Nelson, and Jonathan Schilling
for help with proofreading. 

SUBSCRIPTION INFORMATION / BACK ISSUES

To subscribe to the newsletter, send mail to majordomo@world.std.com with
this line as its message body: 

subscribe c_plus_plus 

Back issues are available via FTP from: 

        ftp.glenmccl.com  /morespace1/glenmccl/newslett

or on the Web at: 

        http://www.glenmccl.com/~glenm

There is also a Java newsletter. To subscribe to it, say: 

subscribe java_letter 

using the same majordomo@world.std.com address. 

-------------------------

Copyright (c) 1997 Glen McCluskey. All Rights Reserved. 

This newsletter may be further distributed provided that it is copied in its
entirety, including the newsletter number at the top and the copyright and
contact information at the bottom. 

Glen McCluskey & Associates LLC
Professional C++ Consulting
Internet: glenm@glenmccl.com
Phone: (800) 722-1613 or (970) 490-2462
Fax: (970) 490-2463
FTP: ftp.glenmccl.com /morespace1/glenmccl/newslett (for back issues)
Web: http://www.glenmccl.com/~glenm