Topic: exception behaviour in containers


Author: David Abrahams <dave@boost-consulting.com>
Date: Mon, 15 Oct 2007 13:16:23 CST
Raw View
on Mon Oct 01 2007, Daniel Kr  gler <daniel.kruegler-AT-googlemail.com> wrote:

> On 1 Okt., 19:42, d...@clovermail.net (Daniel) wrote:
>> [note to moderators: I tried sending this to the newsgroup about 48 hours ago
>> but I can't see it so I am trying again to the email address]
>>
>> I can't see any descriptions/guarantees of what should happen if there is an
>> exception in certain container member functions.  I am specifically interested
>> in copy constructor, assignment operator, and insertion.  It seems there are a
>> few possibilities that could happen:
>>
>> * unwind any changes and leave the container in the state previous to the
>> function call
>> * leave the operation partially complete, some elements copied
>> * abort leaving the container internal data structure corrupted

They are there.

> As recently explained by David Abrahams in the thread " Standard
> library exception specifications might be lacking" found at
>
> http://tinyurl.com/2vqroj
>
> the current standard finished this part a little bit hasty due to
> time- limits and one of the out-comes of the thread was that at
> least some points are still open (begin(), iterator::operator+,
> etc).

I don't think that's an accurate characterization.  We did provide
completely documented guarantees for all the operations in question.
Time limits prevented us from providing stronger guarantees than we did.

> Regrettably it is no-where explicitly written, but the intend
> of the STL seems to be to provide at least the basic safety
> guarantee.

It doesn't need to be explicitly written.  Nowhere does the standard
permit the standard library components to violate invariants.

> I base this assertion on more recent attempts to clarify
> the exception behaviour of the standard library in upcoming
> multi-threading C++ as described in
>
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2410.html

That paper has almost no relevance to the question, AFAICT.

> I don't think that the above mentioned copy-c'tor is relevant for the
> discussion, because a failing c'tor will prevent the existence of a
> to-be-constructed object and thus there is not much to corrupt (or
> do you possibly mean the source??).

The copy ctors with const& rhs are not allowed to modify the source.
That leaves one standard template, auto_ptr, where such considerations
are relevant.

> In [container.requirements]/10+11 of the recent draft there are
> given general statements on insert for the single-insertion step (so
> this is not limited to unordered associative containers).

That's not a new addition.

> I think it was considered as too expensive to provide the strong
> guarantee for multi-inserts and if needed is easy to write.
> Further-on several containers to give more precise guarantees, e.g.
> in [deque.modifiers] or [vector.modifiers]

Correct.

--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com

---
[ 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.comeaucomputing.com/csc/faq.html                      ]





Author: dave@boost-consulting.com (David Abrahams)
Date: Mon, 15 Oct 2007 18:16:33 GMT
Raw View
on Mon Oct 01 2007, dfc-AT-clovermail.net (Daniel) wrote:

> [note to moderators: I tried sending this to the newsgroup about 48
> hours ago but I can't see it so I am trying again to the email
> address]
>
>
> I can't see any descriptions/guarantees of what should happen if there
> is an exception in certain container member functions.  I am
> specifically interested in copy constructor, assignment operator, and
> insertion.  It seems there are a few possibilities that could happen:
>
> * unwind any changes and leave the container in the state previous to
> the function call
> * leave the operation partially complete, some elements copied
> * abort leaving the container internal data structure corrupted
>
> My questions:
> Is there anything said about this in the standard that I have
> missed?

Yes; the specific guarantees are given in:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/1997/N1086.pdf
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/1997/N1114.pdf

When reading the second paper you should ignore the overly-restrictive
and simplified use of the term "safe" in the expository introduction,
which mashes together the strong and nothrow guarantees.  All the
library's operations are safe to use.

> (I see a section in the draft 23.1.3.1 that describes some guarantees
> for the new unordered associative containers - interestingly it
> mentions insert but only with a single element)
> Is there any implied reasons why any of the possibilities above (or
> any other) should or shouldn't happen?

If you're interested in rationale, you might learn something from
www.boost.org/more/generic_exception_safety.html

> Is it deliberate that there is nothing written about this in the
> standard, i.e. is it intended that the specific behaviour is vendor
> defined?

There is plenty written in the standard; both what we wrote and what
we chose not to write were deliberate.  It would probably be a good
idea to give even stronger guarantees for the next standard, though.

--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com

---
[ 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.comeaucomputing.com/csc/faq.html                      ]





Author: dfc@clovermail.net (DFC)
Date: Sun, 7 Oct 2007 17:59:11 GMT
Raw View
Daniel Kr=FCgler wrote:
> On 3 Okt., 23:29, DFC <d...@clovermail.net> wrote:
>=20
>>Daniel Kr=FCgler wrote:
>>
>>>In [container.requirements]/10+11
>>>of the recent draft there are given general statements on insert for
>>>the
>>>single-insertion step (so this is not limited to unordered associative
>>>containers).
>>
>>Thanks, I missed that one this time around but it does look familiar, I=
 see it
>>is in 23.1/10 of my copy of 14882-2003 as well.
>=20
>=20
> Yes, that is correct, but at least for the following discussion the
> draft
> contains at least some more precise wordings, v.i. In the following I
> will - if not said otherwise - refer to the recent draft.
>=20
>=20
>=20
>>>I think it was considered as too expensive to provide the
>>>strong guarantee for multi-inserts and if needed is easy to write.
>>
>>This is what I was wondering but wanted to check really.  operator=3D i=
s the worst
>>one because if you want to gaurantee complete success/fail of operation=
 you have
>>to allocate copies of all the source nodes before deleting the current =
ones. The
>>insert could know what it has inserted and then back track, which could=
 be quite
>>simple.
>=20
>=20
> Especially the copy-assignment operator of containers has a very
> sparse
> specification (actually only a post-condition and a complexity is
> given),
> [container.requirements]/3 says something about the requirements on
> the
> value_type, if it is used. In the moment of writing this I have the
> impression,
> that the container library is under-specified in this regard, because
> in
> [container.requirements]/11 it is said:
>=20
> "Unless otherwise specified (either explicitly or by defining a
> function in terms
> of other functions), invoking a container member function or passing a
> container
> as an argument to a library function shall not invalidate iterators
> to, or change
> the values of, objects within that container."
>=20
> Since operator=3D is *not* defined in terms of other functions
> (specifically: Not
> via insert) one could interpret this sentence that op=3D of a container
> must not
> invalidate iterators to the *destination* container (we are obviously
> using a
> member function of the destination) - which makes no sense at all. Can
> anyone
> show me some wording in the standard, which clarifies this point?

Hmm, it would seem operator=3D should be noted that it invalidates all it=
erators=20
and references?

>=20
> Concerning your reference to "nodes": Are you speaking here for
> std::list
> now, otherwise the remainder of the above mentioned insert conclusion
> cannot be guaranteed.
>=20

Not quite sure I follow you here but yes I was thinking about list when I=
 wrote=20
that but really I am concerned with any container and its nodes or elemen=
ts.

>=20
>>When you say it is 'easy to write' you mean easy for the user to add ex=
tra code
>>to guarantee this if needed? i.e they would make a copy of the contain =
before
>>performing the operator=3D or insert(many) and if it failed they would =
revert to
>>the copy.
>=20
>=20
> Yes, I mean a user-written helper function, typically taking advantage
> of
> swap:
>=20
> template<class Container>
> Container& safe_copy_assign(Container& dst, const Container& rhs) {
>   dst.swap(Container(rhs));
>   return dst;
> }
>=20
> Insert is a more tricky case, because of the first hint-iterator
> argument,
> but it is also solvable.
>=20
>=20
>>So in summary, what you are saying is an implementation can't be expect=
ed to
>>provide this guarantee for any operation that involves some sort of mul=
ti-insert
>>but the question is, is an implementation is still allowed to provide t=
hat if it
>>wants?
>=20
>=20
> That depends. Just in the moment I see no way how e.g. std::vector
> could realize that. The point is that this seems to violate the
> reallocation/
> reference/iterator guarantees of this container: If I make a copy of
> the original
> container to undo the changes of a possibly failing insert, I would
> not be allowed to replace the original container. But except for some
> specific cases an implementation can give such guarantees if not
> violating other constraints.
>=20

The vector allocates a new larger chunk of memory capable of holding the=20
enlarged vector, copies the old elements and new to be inserted ones, and=
 then=20
deletes the original.  If anything goes wrong it deletes the new one and =
the old=20
one still exists.  If the vector is already large enough it copies everyt=
hing it=20
needs to the right and inserts new elements.  If something goes wrong it =
copies=20
them all back. (If there is an exception copying elements back it is bad =
news,=20
perhaps this is the relevance of the "other than the assignment operator =
of T"=20
clause, the way I am reading it... see below )


>=20
>>>Further-on several containers to give more precise guarantees, e.g.
>>>in [deque.modifiers] or [vector.modifiers]
>>
>>and so does list.modifiers (again I had overlooked these). So it seems =
all the
>>sequences do require insert(many) to back track if there is an exceptio=
n.
>=20
>=20
> How do you come to that conclusion? Please note, that they mostly
> give some constraints, e.g. std::vector says in [vector.modifiers]/3:
>=20
> "[..] If an exception is thrown other than by the copy constructor or
> assignment operator of T or by any InputIterator operation there are
> no effects.[..]
>=20

The way I read this (but perhaps I misunderstand it) is that, for example=
,=20
23.2.5.4/3 is referring to all the various insert methods outlined in /1.=
  /3 to=20
me reads "if an exception is thrown...there are no effects" in other word=
s "if=20
an exception is thrown when calling an insert method...the container must=
 be in=20
the same state as before the insert method was called" (+ some cases when=
 this=20
may not happen depending on the exception source).  If this is right it a=
nswers=20
some of my original question... for insert(many) in sequence containers i=
t is=20
explicitly stated what needs to happen.


> First, note that compared to [lib.vector.modifiers]/1 of the
> corresponding
> 14882-2003 document the part "or by any InputIterator operation" has
> been added. IMO this has been done, because other iterator categories
> can precalculate the new size and ensure that there is enough memory
> to fulfil the request - this is generally not possible for
> InputIterators.
> Second, if you have the money (I mean the allocated memory ;-)),
> other
> potential exception sources are those which occur by moving some
> vector
> elements and by copying the new ones - and if these fail, there can
> be
> effects.
>=20

Ok, agreed. If the exception source is, for example, due to copying the n=
ew one=20
we may still be able to undo, but if it is due to copying the old ones ba=
ck in=20
an attempt to undo then we are stuffed, so I now understand the reason fo=
r the=20
"other than copy ctor or assignment op of T..." clause.

>=20
>>Do
>>you think this requirement on the associative containers is an oversigh=
t,
>>because like you mentioned it was rushed?  I also can't see the signifi=
cance of
>>"other than by the copy constructor or assignment operator of T" except=
ion to
>>the rule there are no effects, any thoughts?
>=20
>=20
> Hmmh, now you are discussing again about the *associative* containers?
> What do you mean with "this requirements" in this regard?
>=20

What I am trying to say is I can't see any mention of what should happen =
if=20
there is an exception in a map::insert for example, 23.3.1.3 doesn't seem=
 to=20
mention exceptions at all. I want to know if there should be a paragraph =
like=20
23.2.5.4/3 in the appropriate places in the associative containers, or if=
 there=20
is a good reason nothing is mentioned about exceptions, or if I have over=
looked=20
something (again).


So in summary:
* I think we have answered my questions about sequence containers and ins=
ert methods
* operator=3D probably isn't very well specified
* I'm not sure about insert methods in the associative containers and nee=
d some=20
more advice about what should happen with these

Daniel

---
[ 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.comeaucomputing.com/csc/faq.html                      ]





Author: dfc@clovermail.net (Daniel)
Date: Mon, 1 Oct 2007 17:42:22 GMT
Raw View
[note to moderators: I tried sending this to the newsgroup about 48 hours ago
but I can't see it so I am trying again to the email address]


I can't see any descriptions/guarantees of what should happen if there is an
exception in certain container member functions.  I am specifically interested
in copy constructor, assignment operator, and insertion.  It seems there are a
few possibilities that could happen:

* unwind any changes and leave the container in the state previous to the
function call
* leave the operation partially complete, some elements copied
* abort leaving the container internal data structure corrupted

My questions:
Is there anything said about this in the standard that I have missed? (I see a
section in the draft 23.1.3.1 that describes some guarantees for the new
unordered associative containers - interestingly it mentions insert but only
with a single element)
Is there any implied reasons why any of the possibilities above (or any other)
should or shouldn't happen?
Is it deliberate that there is nothing written about this in the standard, i.e.
is it intended that the specific behaviour is vendor defined?

Thanks,
Daniel


---
[ 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.comeaucomputing.com/csc/faq.html                      ]





Author: =?iso-8859-1?q?Daniel_Kr=FCgler?= <daniel.kruegler@googlemail.com>
Date: Tue, 2 Oct 2007 02:06:02 CST
Raw View
On 1 Okt., 19:42, d...@clovermail.net (Daniel) wrote:
> [note to moderators: I tried sending this to the newsgroup about 48 hours ago
> but I can't see it so I am trying again to the email address]
>
> I can't see any descriptions/guarantees of what should happen if there is an
> exception in certain container member functions.  I am specifically interested
> in copy constructor, assignment operator, and insertion.  It seems there are a
> few possibilities that could happen:
>
> * unwind any changes and leave the container in the state previous to the
> function call
> * leave the operation partially complete, some elements copied
> * abort leaving the container internal data structure corrupted

As recently explained by David Abrahams in the thread " Standard
library exception specifications might be lacking" found at

http://tinyurl.com/2vqroj

the current standard finished this part a little bit hasty due to time-
limits
and one of the out-comes of the thread was that at least some points
are still open (begin(), iterator::operator+, etc). Regrettably it is
no-where
explicitly written, but the intend of the STL seems to be to provide
at least
the basic safety guarantee. I base this assertion on more recent
attempts
to clarify the exception behaviour of the standard library in upcoming
multi-threading C++ as described in

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2410.html

I don't think that the above mentioned copy-c'tor is relevant for the
discussion, because a failing c'tor will prevent the existence of a
to-be-constructed object and thus there is not much to corrupt (or
do you possibly mean the source??). In [container.requirements]/10+11
of the recent draft there are given general statements on insert for
the
single-insertion step (so this is not limited to unordered associative
containers). I think it was considered as too expensive to provide
the
strong guarantee for multi-inserts and if needed is easy to write.
Further-on several containers to give more precise guarantees, e.g.
in [deque.modifiers] or [vector.modifiers]

Greetings from Bremen,

Daniel Kr   gler


---
[ 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.comeaucomputing.com/csc/faq.html                      ]





Author: DFC <dfc@clovermail.net>
Date: Wed, 3 Oct 2007 15:29:12 CST
Raw View
Daniel Kr   gler wrote:
> I don't think that the above mentioned copy-c'tor is relevant for the
> discussion, because a failing c'tor will prevent the existence of a
> to-be-constructed object and thus there is not much to corrupt (or
> do you possibly mean the source??).

You are right, if the constructor doesn't complete I just need to clean up
anything that has been done so as not to leak memory, and forward the exception,
I shouldn't of mentioned it because it isn't really what I wanted to discuss.

When I said leave the container corrupt I was referring to the destination but
this isn't really a viable option because it potentially means the container
can't even be destroyed.


> In [container.requirements]/10+11
> of the recent draft there are given general statements on insert for
> the
> single-insertion step (so this is not limited to unordered associative
> containers).

Thanks, I missed that one this time around but it does look familiar, I see it
is in 23.1/10 of my copy of 14882-2003 as well.

> I think it was considered as too expensive to provide the
> strong guarantee for multi-inserts and if needed is easy to write.

This is what I was wondering but wanted to check really.  operator= is the worst
one because if you want to gaurantee complete success/fail of operation you have
to allocate copies of all the source nodes before deleting the current ones. The
insert could know what it has inserted and then back track, which could be quite
simple.

When you say it is 'easy to write' you mean easy for the user to add extra code
to guarantee this if needed? i.e they would make a copy of the contain before
performing the operator= or insert(many) and if it failed they would revert to
the copy.

So in summary, what you are saying is an implementation can't be expected to
provide this guarantee for any operation that involves some sort of multi-insert
but the question is, is an implementation is still allowed to provide that if it
wants?

> Further-on several containers to give more precise guarantees, e.g.
> in [deque.modifiers] or [vector.modifiers]
>

and so does list.modifiers (again I had overlooked these). So it seems all the
sequences do require insert(many) to back track if there is an exception.  Do
you think this requirement on the associative containers is an oversight,
because like you mentioned it was rushed?  I also can't see the significance of
"other than by the copy constructor or assignment operator of T" exception to
the rule there are no effects, any thoughts?


Daniel

---
[ 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.comeaucomputing.com/csc/faq.html                      ]





Author: =?iso-8859-1?q?Daniel_Kr=FCgler?= <daniel.kruegler@googlemail.com>
Date: Wed, 3 Oct 2007 18:47:50 CST
Raw View
On 3 Okt., 23:29, DFC <d...@clovermail.net> wrote:
> Daniel Kr   gler wrote:
> > In [container.requirements]/10+11
> > of the recent draft there are given general statements on insert for
> > the
> > single-insertion step (so this is not limited to unordered associative
> > containers).
>
> Thanks, I missed that one this time around but it does look familiar, I see it
> is in 23.1/10 of my copy of 14882-2003 as well.

Yes, that is correct, but at least for the following discussion the
draft
contains at least some more precise wordings, v.i. In the following I
will - if not said otherwise - refer to the recent draft.


> > I think it was considered as too expensive to provide the
> > strong guarantee for multi-inserts and if needed is easy to write.
>
> This is what I was wondering but wanted to check really.  operator= is the worst
> one because if you want to gaurantee complete success/fail of operation you have
> to allocate copies of all the source nodes before deleting the current ones. The
> insert could know what it has inserted and then back track, which could be quite
> simple.

Especially the copy-assignment operator of containers has a very
sparse
specification (actually only a post-condition and a complexity is
given),
[container.requirements]/3 says something about the requirements on
the
value_type, if it is used. In the moment of writing this I have the
impression,
that the container library is under-specified in this regard, because
in
[container.requirements]/11 it is said:

"Unless otherwise specified (either explicitly or by defining a
function in terms
of other functions), invoking a container member function or passing a
container
as an argument to a library function shall not invalidate iterators
to, or change
the values of, objects within that container."

Since operator= is *not* defined in terms of other functions
(specifically: Not
via insert) one could interpret this sentence that op= of a container
must not
invalidate iterators to the *destination* container (we are obviously
using a
member function of the destination) - which makes no sense at all. Can
anyone
show me some wording in the standard, which clarifies this point?

Concerning your reference to "nodes": Are you speaking here for
std::list
now, otherwise the remainder of the above mentioned insert conclusion
cannot be guaranteed.

> When you say it is 'easy to write' you mean easy for the user to add extra code
> to guarantee this if needed? i.e they would make a copy of the contain before
> performing the operator= or insert(many) and if it failed they would revert to
> the copy.

Yes, I mean a user-written helper function, typically taking advantage
of
swap:

template<class Container>
Container& safe_copy_assign(Container& dst, const Container& rhs) {
  dst.swap(Container(rhs));
  return dst;
}

Insert is a more tricky case, because of the first hint-iterator
argument,
but it is also solvable.

> So in summary, what you are saying is an implementation can't be expected to
> provide this guarantee for any operation that involves some sort of multi-insert
> but the question is, is an implementation is still allowed to provide that if it
> wants?

That depends. Just in the moment I see no way how e.g. std::vector
could realize that. The point is that this seems to violate the
reallocation/
reference/iterator guarantees of this container: If I make a copy of
the original
container to undo the changes of a possibly failing insert, I would
not be allowed to replace the original container. But except for some
specific cases an implementation can give such guarantees if not
violating other constraints.

> > Further-on several containers to give more precise guarantees, e.g.
> > in [deque.modifiers] or [vector.modifiers]
>
> and so does list.modifiers (again I had overlooked these). So it seems all the
> sequences do require insert(many) to back track if there is an exception.

How do you come to that conclusion? Please note, that they mostly
give some constraints, e.g. std::vector says in [vector.modifiers]/3:

"[..] If an exception is thrown other than by the copy constructor or
assignment operator of T or by any InputIterator operation there are
no effects.[..]

First, note that compared to [lib.vector.modifiers]/1 of the
corresponding
14882-2003 document the part "or by any InputIterator operation" has
been added. IMO this has been done, because other iterator categories
can precalculate the new size and ensure that there is enough memory
to fulfil the request - this is generally not possible for
InputIterators.
Second, if you have the money (I mean the allocated memory ;-)),
other
potential exception sources are those which occur by moving some
vector
elements and by copying the new ones - and if these fail, there can
be
effects.

> Do
> you think this requirement on the associative containers is an oversight,
> because like you mentioned it was rushed?  I also can't see the significance of
> "other than by the copy constructor or assignment operator of T" exception to
> the rule there are no effects, any thoughts?

Hmmh, now you are discussing again about the *associative* containers?
What do you mean with "this requirements" in this regard?

Greetings from Bremen,

Daniel Kr   gler


---
[ 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.comeaucomputing.com/csc/faq.html                      ]