Exception Safety Concerning Range Members
jehuga...@gmail.com
I have recently been reading books by both Scott Meyers and Herb
Sutter.
Dr. Meyers points out the considerable efficiency gains by using range
members, such as assign and insert.
Dr. Sutter writes that range members are an exception to the exception
guarantees of the STL. He mentioned something about handling such
cases would pose an efficiency cost on the implementations.
Is this true for std::list? Could you create a temporary list and then
splice it into *this?
template <typename FITER>
list(FITER first, FITER past)
{
while (first != past)
{
insert(end(), *(first++)); // could be optimized
}
}
template <typename FITER>
void insert(iterator pos, FITER first, FITER past)
{
(*this).splice(pos, std::list<T, allocator_type>(first, past)); //
allocators are stateless
//
splice is constant time
//
and has a strong exception guarantee
}
Is this exception-safe? Does it require considerable, additional
processing? Why don't any implementations seem to use it?
Thanks!
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
jehuga...@gmail.com
> splice it into *this?
>
> template <typename FITER>
> list(FITER first, FITER past)
> {
> while (first != past)
> {
> insert(end(), *(first++)); // could be optimized
> }
>
> }
>
> template <typename FITER>
> void insert(iterator pos, FITER first, FITER past)
> {
> (*this).splice(pos, std::list<T, allocator_type>(first, past)); //
> allocators are stateless
> //
> splice is constant time
> //
> and has a strong exception guarantee
>
> }
I just wanted to point out that I realize that this won't compile. In
a spurt, I forgot the recieved lists was by reference, not const
reference. See how trying to eliminate temps all the time get you in
trouble?!
>
> Is this exception-safe? Does it require considerable, additional
> processing? Why don't any implementations seem to use it?
I also wanted to point out that I am aware that some implementations
may choose to do a count of the spliced objects. However, for my
example, I am assuming that the operation is constant time, or that
the 2-argument splice would be optimized to takes the incoming list's
size and add it to its own. Hence there would be no "extra" cost of
using splice this way (at most one linear count). I am also assuming
that splice on a doubly linked list would be nothing more than 4
pointer changes.
I realized some of this last night right after I posted.
David Abrahams
on Sun May 20 2007, "jehugaleahsa-AT-gmail.com" <jehugaleahsa-AT-gmail.com> wrote:
> Hello:
>
> I have recently been reading books by both Scott Meyers and Herb
> Sutter.
>
> Dr. Meyers points out the considerable efficiency gains by using range
> members, such as assign and insert.
>
> Dr. Sutter writes that range members are an exception to the exception
> guarantees of the STL.
That's at best a misconception.
The STL gives the basic exception guarantee everywhere, the strong
guarantee where it can without loss of efficiency, and the nothrow
guarantee where it is important to do so (e.g. for recovery or so that
stack unwinding can proceed). The exception guarantees for the range
members are specified entirely consistently in that context. See
http://www.boost.org/more/generic_exception_safety.html
Sutter's characterization of the STL in my copy of "Exceptional C++"
that "all standard containers must also implement the strong guarantee
for all operations (with two exceptions)" puts the emphasis in the
wrong place, and the two exceptions are ultimately incorrectly stated,
as shown below.
> He mentioned something about handling such cases would pose an
> efficiency cost on the implementations.
In the case where the copy ctor and/or assignment operator of T can
throw an exception, **giving the strong guarantee** for
vector<T>::insert(pos,it0,it1) and deque<T>::insert(pos,it0,it1) would
impose an efficiency cost (you'd essentially have to allocate and copy
an entirely new container).
That doesn't mean the case isn't "handled." It also doesn't apply to
the range constructors of std::vector<>.
> Is this true for std::list?
No. In fact, 23.2.3.3 list modifiers says specifically,
template <class InputIterator>
void insert(iterator position , InputIterator first ,
InputIterator last );
...
1 Remarks: Does not affect the validity of iterators and
references. If an exception is thrown there are no effects.
Which means it unconditionally gives the strong guarantee. I suggest
you go to the standard for the official guarantees. The secondary
sources are often wrong or misleading.
> Could you create a temporary list and then
> splice it into *this?
Yes, you can.
> template <typename FITER>
> list(FITER first, FITER past)
> {
> while (first != past)
> {
> insert(end(), *(first++)); // could be optimized
> }
> }
>
> template <typename FITER>
> void insert(iterator pos, FITER first, FITER past)
> {
> (*this).splice(pos, std::list<T, allocator_type>(first, past)); // allocators are stateless
> // splice is constant time
> // and has a strong exception guarantee
> }
>
> Is this exception-safe?
Depends what you mean by that ;-). When I say "exception-safe," I
mean "gives the basic guarantee."
> Does it require considerable, additional processing? Why don't any
> implementations seem to use it?
Did you look at the actual code? If it's not ultimately doing
something equivalent to the above, in the case where the allocators
are equal, it's nonconforming. If you have found such a nonconforming
implementation, could you please let us know which one it is?
Thanks,
--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com
jehuga...@gmail.com
> throw an exception, **giving the strong guarantee** for
> vector<T>::insert(pos,it0,it1) and deque<T>::insert(pos,it0,it1) would
> impose an efficiency cost (you'd essentially have to allocate and copy
> an entirely new container).
Yes, I first tried to implement the range insert for vector and
realized multiple reasons why it cannot provide the strong guarantee
without performance cost. The first being that you have to know
whether or not you need to reallocate. The std::distance of the range
*could* be constant time, but is not guaranteed.
> Which means it unconditionally gives the strong guarantee. I suggest
> you go to the standard for the official guarantees. The secondary
> sources are often wrong or misleading.
Even though I am a little die-hard about C++, I find it difficult to
read the standard. I am not a compiler implementer, I am a programmer.
I will read the standard when 0x comes out, since I will need to do
some major catch up. :- )
> > Could you create a temporary list and then
> > splice it into *this?
>
> Yes, you can.
Well, that is good. I am glad my noodle is working.
> > Does it require considerable, additional processing? Why don't any
> > implementations seem to use it?
>
> Did you look at the actual code? If it's not ultimately doing
> something equivalent to the above, in the case where the allocators
> are equal, it's nonconforming. If you have found such a nonconforming
> implementation, could you please let us know which one it is?
At the two implementations I looked at, specifically MSVC8, the code
looked something like this:
template<class _Iter>
void _Insert(iterator _Where,
_Iter _First, _Iter _Last, input_iterator_tag)
{
size_type _Num = 0;
try {
for (; _First != _Last; ++_First, ++_Num)
_Insert(_Where, *_First);
} catch (...) {
for (; 0 < _Num; --_Num)
{ // undo inserts
iterator _Before = _Where;
erase(--_Before);
}
}
}
This looks like it is adding the elements one at a time, and then
backing up if something goes wrong. This is what I see in GCC 3.4.4:
// Called by the range insert to implement [23.1.1]/9
template<typename _InputIterator>
void
_M_insert_dispatch(iterator __pos,
_InputIterator __first, _InputIterator __last,
__false_type)
{
for ( ; __first != __last; ++__first)
_M_insert(__pos, *__first);
}
followed by this:
// Called by insert(p,n,x), and the range insert when it turns out
// to be the same thing.
void
_M_fill_insert(iterator __pos, size_type __n, const value_type&
__x)
{
for ( ; __n > 0; --__n)
_M_insert(__pos, __x);
}
I had to track this one down. But in both cases, you see the elements
getting put in in a linear fashion. That is what surprised me. It is
hard to get an allocator from a generic range. The GCC version doesn't
even look like it tries to be exception-safe. Of course, perhaps it is
dealt with in the _M_ methods.
In either case, I don't see splice being used, even though it would
seem to be more exception safe.
That is why I was curious in the first place. Perhaps I missed
something.
Thanks!
--
David Abrahams
on Mon May 21 2007, "jehugaleahsa-AT-gmail.com"
<jehugaleahsa-AT-gmail.com> wrote:
>> > Does it require considerable, additional processing? Why don't any
>> > implementations seem to use it?
>>
>> Did you look at the actual code? If it's not ultimately doing
>> something equivalent to the above, in the case where the allocators
>> are equal, it's nonconforming. If you have found such a nonconforming
>> implementation, could you please let us know which one it is?
>
> At the two implementations I looked at, specifically MSVC8, the code
> looked something like this:
>
> template<class _Iter>
> void _Insert(iterator _Where,
> _Iter _First, _Iter _Last, input_iterator_tag)
> {
> size_type _Num = 0;
>
> try {
> for (; _First != _Last; ++_First, ++_Num)
> _Insert(_Where, *_First);
> } catch (...) {
> for (; 0 < _Num; --_Num)
> { // undo inserts
> iterator _Before = _Where;
> erase(--_Before);
> }
> }
> }
>
> This looks like it is adding the elements one at a time, and then
> backing up if something goes wrong.
Which is exactly equivalent to the splice technique. It gives the
strong guarantee.
> This is what I see in GCC 3.4.4:
>
> // Called by the range insert to implement [23.1.1]/9
> template<typename _InputIterator>
> void
> _M_insert_dispatch(iterator __pos,
> _InputIterator __first, _InputIterator __last,
> __false_type)
> {
> for ( ; __first != __last; ++__first)
> _M_insert(__pos, *__first);
> }
>
> followed by this:
>
> // Called by insert(p,n,x), and the range insert when it turns out
> // to be the same thing.
> void
> _M_fill_insert(iterator __pos, size_type __n, const value_type&
> __x)
> {
> for ( ; __n > 0; --__n)
> _M_insert(__pos, __x);
> }
I don't think that code is relevant to what we're looking at.
> I had to track this one down. But in both cases, you see the elements
> getting put in in a linear fashion. That is what surprised me. It is
> hard to get an allocator from a generic range.
I don't understand the relevance of that statement.
> The GCC version doesn't even look like it tries to be
> exception-safe. Of course, perhaps it is dealt with in the _M_
> methods.
No, there's no way it can be. The GCC code is clearly buggy.
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32017
> In either case, I don't see splice being used, even though it would
> seem to be more exception safe.
It's not more exception safe than the Dinkum approach, though it is
simpler. The Dinkum approach has the advantage of working with
unequal allocators (for some definition of "working" that I'm sure
Dinkumware supplies somewhere).
> That is why I was curious in the first place. Perhaps I missed
> something.
Perhaps; perhaps not ;-).
--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Michael Marcin
>
> No, there's no way it can be. The GCC code is clearly buggy.
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32017
>
Interestingly enough there seems to have been progress on this front today.
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21772
Perhaps as a nod to this conversation?
- Michael Marcin
--