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

[Paolo Carlini <pcarlini at suse dot de>]

Hi Steve,

> I recently found that deque iterators were being invalidated under some
> circumstances when they shouldn't be.
>
> Specifically when elements are removed from the front of the deque using
> my_deque.erase(my_deque.begin(), my_deque.begin() + n)
>
> iterators at position (begin() + n) and beyond created before the erase
> should still be valid after the erase as stated in the standard
> at 23.2.1.3.4
>  
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:

   ...
     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?

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.