deque fails to meet 23.2.1.3.4-5 causing invalid iterators and extra assignments

[Steve LoBasso]

Hi Paolo,

> first, thanks for your message. Can you help me further understanding
> the issue? I suggest discussing the current (for 4.2.0 and later
> releases) code, more efficient and also more clear, IMHO:

Speaking relative to 4.2.0 is fine, as far as I can tell, this bug exists
in all versions of gnu deque as far back as I can see. In fact I see the
same problem in the SGI implementation. It seems to be an old bug and must
have been copied MANY times into MANY implementations.

> 
>     ...
>       const difference_type __n = __last - __first;
>       const difference_type __elems_before = __first - begin();
>       if (static_cast<size_type>(__elems_before) < (size() - __n) / 2)
>         {
>           if (__first != begin())
>         std::copy_backward(begin(), __first, __last);
>           _M_erase_at_begin(begin() + __n);
>         }
>       else
>         {
>           if (__last != end())
>         std::copy(__last, end(), __first);
>           _M_erase_at_end(end() - __n);
>         }
>     ...
> 
> In your specific example above, we have __elems_before == 0, and the
> condition can become false only when __n == size() -1 (not for any
> smaller __n), because then integer division by two leads to zero.
> Indeed, if the condition is false, we end up copying the last element
> from the tail to the head and then erasing the last __n - 1 elements,
> the last one included, thus invalidating incorrectly any iterator to the
> last element itself. Is this the issue we are actually discussing, or
> can you conceive of other more general situations?

These seem to be the main issues:
 the one extra copy and at the same time copying in the wrong direction,
 thus invalidating the iterators. I can't see any other problems.

Although it is a problem more often than when n = size() - 1
ie. size() = 8 erase(begin() + 3, begin() + 4)

> Coming then to your proposed solution, I don't like that it effectively
> removes the nice idea of always copying the  optimal (minimum) number of
> elements: AFAICS, only comparing to (size() - __n) / 2 exactly achieves
> that. Then, I think we could instead do this:
> 
> Index: deque.tcc
> ===================================================================
> --- deque.tcc   (revision 121055)
> +++ deque.tcc   (working copy)
> @@ -143,7 +143,7 @@
>         {
>           const difference_type __n = __last - __first;
>           const difference_type __elems_before = __first - begin();
> -         if (static_cast<size_type>(__elems_before) < (size() - __n) / 2)
> +         if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
>             {
>               if (__first != begin())
>                 std::copy_backward(begin(), __first, __last);
> 
> What do you think? In case, you should tell me whether this helps for
> the other issue too (I didn't really look into it yet, sorry, but I'm
> pretty sure it does ;) and help me a bit with understanding the dumps of
> your testcase: when, exactly, in a nutshell, the dumps are fine?
> 
> Thanks,
> Paolo.

I believe your fix is just as valid as mine. Either one seems to fix the problem.

Thanks

   -Steve



 
____________________________________________________________________________________
Cheap talk?
Check out Yahoo! Messenger's low PC-to-Phone call rates.
http://voice.yahoo.com