Recently I bought a book called "The C++ Standard Template Library" by P.J.
Plauger. The book contains the source code for the STL part of Dinkumware's
Standard C++ library along with comments on the code presented and
explanations on how it relates to the ISO C++ Standard. The book claims "You
will find here a complete presentation of STL as it is specified by the C++
Standard." My purpose behind buying the book was to study the code of the
standard containers to see how the various exception guarantees explained in
the Standard are met in a library sold on a commercial basis.

So, I started from Chapter 9 "Containers", which contains general
information on STL containers and explains their exception safety
guarantees. I was soon struck by the absolutely erroneous statements on the
containers exception safety. And I find it of paramount importance to
explain the mistaken statements so that they get a lesser chance of
spreading around. In particular the book claims that:

1. "For all the container classes defined by STL, if an exception is thrown
during calls to the following member functions: insert (single element
insert), push_back, push_front the container is left unaltered and the
exception is rethrown". Whereas the C++ Standard gives such strong guarantee
for the overloaded member functions insert of classes vector and deque only
on condition that the copy constructor and the copy assignment operator of
the type T used to instantiate the container do not throw while inserting,
see 23.2.1.3/2 and 23.2.4.3/1 of the Standard.

2. "For all the container classes defined by STL, no exception is thrown
during calls to the following member functions: erase (single element
erase), pop_back, pop_front". Again the book fails to acknowledge that the
C++ Standard gives the no-throw guarantee for the overloaded member
functions erase of classes vector and deque only on condition that the copy
constructor and the copy assignment operator of the type T used to
instantiate the container do not throw while erasing, see 23.2.1.3/6 and
23.2.4.3/5 of the Standard.

The above over-confident statements could partially be justifiable, had the
STL part of Dinkumware's Standard C++ library presented in the book
delivered what the book claims. But, having studied the code of vector and
deque, I can say that it's not the case.

3. "The member function swap makes additional promises for all container
classes defined by STL: the member function throws an exception only if the
container stores an allocator object al, and al throws an exception when
copied". That's something wrong again, for the Standard promises something
completely different: "no swap function throws an exception unless that
exception is thrown by the copy constructor or assignment operator of the
container's Compare object" (23.1/10).

For those who bough the book I'd suggest reading what the Standard has to
say on the containers exception safety instead. Also, Bjarne Stroustrup has
placed on a free basis an appendix to his book called "E: Standard-Library
Exception Safety", which explains the exception safety guarantees of the
standard containers in detail and in accordance with the C++ and which can
be found at:
http://www.research.att.com/~bs/3rd_safe0.html

Having studied what the book had to say on the stanard containers in general
I went on to Chapter 10
"<vector>", where the source code for the standard vector and its
specialization for bool were presented. And on the very first page of the
code I found an embarassing memory leak in almost all the constructors:

...

template<class T, class A>
    class Vector_val {
protected:
    class Vector_val(A Al = A())
        : Alval(Al)  {}
    typedef typename A::typename A::template
        rebind<T>::other Alty;
    Alty Alval;
    };

template<class T, class Ax = allocator<T> >
    class vector : public Vector_val<T, Ax> {
public:
    ...
    typedef Vector_val<T, Ax> Mybase;
    typedef typename Mybase::Alty A;
    ...
    ...
    ...
    vector(size_type N)
        : Mybase()
        {if (Buy(N))
            Last = Ufill(First, N, T()); }
    vector(size_type N, const T& V, const A& Al)
        : Mybase(Al)
        {if (Buy(N))
            Last = Ufill(First, N, V); }
    ...
protected:
    bool Buy(size_type N)
        {First = 0, Last = 0, End = 0;
        if (N == 0)
            return (false);
        else
            {First = Mybase::Alval.allocate(N,
                (void *)0);
            Last = First;
            End = First + N;
            return (true); }}
    ...
    void Destroy(pointer F, pointer L)
        {for (; F != L; ++F)
            Mybase::Alval.destroy(F); }
    ...
    template<class It>
        pointer Ufill(pointer Q, size_type N, const T &X)
        {pointer Qs = Q;
        try {
        for (; 0 < N; --N, ++Q)
            Mybase::Alval.construct(Q, X);
        } catch (...) {
        Destroy(Qs, Q);
        throw;
        }
        return (Q); }
    pointer First, Last, End;
    };

Clearly, if Ufill throws an exception due to the converting constructor for
a user-supplied type T throwing, the memory allocated by 'Buy' is NOT
RELEASED, which drasticly violates the guarantees of the Standard.

Further examination of the library revealed bugs in almost every container
presented...


Sincerely,
Andrei Iltchenko.


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]