stdcxx-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Mark Brown <mark.g.br...@gmail.com>
Subject Re: STDCXX-635 and iterator validitty after deque::swap()
Date Fri, 23 Nov 2007 18:59:46 GMT
Martin Sebor wrote:
> Following up on an old thread...
> 
> I suspect this problem that we've been discussing for some time now
> might stem from the fact that the standard doesn't actually define
> what it means to invalidate an iterator. Here's some background: 
> http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#278
> 
> IIUC, the resolution of the issue makes the test case for the issue 
> (STDCXX-635) invalid (and the behavior of deque::swap() valid WRT
> repointing the end iterators).
> 
> But, unless I'm missing something, it also means that an operation
> that is required not to invalidate existing iterators might actually
> cause some valid iterators to point to different elements than they
> did before. And that doesn't seem quite right to me.
> 
> Thoughts?

This is a tricky problem. I found an old thread on comp.std.c++
that discusses the same issue in the context of list splicing:
http://groups.google.com/group/comp.std.c++/browse_thread/thread/a9c7fe6b37f5926d/611b0e71f9e0ad6f
I haven't read the whole long thread very carefully but from what
have read it doesn't look like the group reached a firm conclusion
on the subject. I do agree that the standard absolutely must make
it clear that not just individual iterators but also ranges denoted
by pairs of iterators remain valid after non-invalidating operations
or not.

--Mark

> 
> Martin
> 
> 
> Farid Zaripov wrote:
>>> -----Original Message-----
>>> From: Martin Sebor [mailto:msebor@gmail.com] On Behalf Of Martin Sebor
>>> Sent: Monday, July 09, 2007 7:40 AM
>>> To: stdcxx-dev@incubator.apache.org
>>> Subject: Re: 23.deque.special
>>>
>>> Farid Zaripov wrote:
>>>>   Below is a part of the 23.deque.special test. These rw_assert's 
>>>> fails because of deque::end() internal representation is 
>>> dependent on
>>>> object and cannot be swapped.
>>> I'm not sure I understand.
>>
>>   The std::deque<>::iterator type has two members: pointer to the
>> current element and pointer
>> to the array containing the element (include/deque, line 188):
>>
>>     // `cur' points at the curent element or is null (for the end
>> iterator)
>>     // `node' points to the array containing the element or &cur (for
>> end)
>>     pointer         _C_cur;
>>     _C_node_pointer _C_node;
>> };
>>
>>   For the end iterator _C_node == &_C_cur.
>>
>>   In case swapping two empty deque, two end iterators being swapped.
>>
>>   Let's iter1 is the iterator of some deque1 and iter2 is the iterator
>> of another deque2 before swap.
>> And let's iter3 is the iterator of deque1 and iter4 is the iterator of
>> deque2 after swap.
>>
>> Before swap:
>>
>>   iter1._C_cur == 0;
>>   iter1._C_node == &deque1._C_end._C_cur;
>>
>>   iter2._C_cur == 0;
>>   iter2._C_node == &deque2._C_end._C_cur;
>>
>> After swap still:
>>
>>   iter3._C_cur == 0;
>>   iter3._C_node == &deque1._C_end._C_cur;
>>
>>   iter4._C_cur == 0;
>>   iter4._C_node == &deque2._C_end._C_cur;
>>
>> The iterators mebmer values aren't swapped, because if they would
>> swapped these iterators
>> wouldn't be "end iterators" in terms of our deque implementation.
>>
>>   iter3 != iter2 and iter4 != iter1
>>
>> So in our deque implementation we shouldn't compare end iterators after
>> swap operation.
>>
>>> Swapping two deques is required not to invalidate any iterators, isn't
>> that right?
>>
>>   If iter3 should == iter2 and iter4 should == iter1, then we need to
>> change the deque implementation.
>>
>>> Are you suggesting to loosen the test so as not to exercise this
>> requirement?
>>   I suggest only not to exercise iterators if one deque is empty.
>>
>> Farid.
> 
> 


Mime
View raw message