You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@stdcxx.apache.org by Farid Zaripov <Fa...@epam.com> on 2007/07/06 19:01:29 UTC
23.deque.special
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 think that this part should be replaced to just checking
deque.begin() == deque.end() after (and perhaps, before) the swap
operation.
--------------
typedef std::deque<T, std::allocator<T> > MyDeque;
typedef typename MyDeque::iterator Iterator;
// create two empty deque objects
MyDeque empty [2];
// save their begin and end iterators before calling swap
const Iterator before [2][2] = {
{ empty [0].begin (), empty [0].end () },
{ empty [1].begin (), empty [1].end () }
};
// swap the two containers
empty [0].swap (empty [1]);
// get the new begin and end iterators
const Iterator after [2][2] = {
{ empty [0].begin (), empty [0].end () },
{ empty [1].begin (), empty [1].end () }
};
// verify that the iterators have not been invalidated
rw_assert ( before [0][0] == after [1][0]
&& before [1][0] == after [0][0], 0, __LINE__,
"deque<%s>().begin() not swapped", tname);
rw_assert ( before [0][1] == after [1][1]
&& before [1][1] == after [0][1], 0, __LINE__,
"deque<%s>().end() not swapped", tname);
--------------
Farid.
Re: STDCXX-635 and iterator validitty after deque::swap()
Posted by Mark Brown <ma...@gmail.com>.
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.
>
>
STDCXX-635 and iterator validitty after deque::swap() (was: Re: 23.deque.special)
Posted by Martin Sebor <se...@roguewave.com>.
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?
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.
RE: 23.deque.special
Posted by Farid Zaripov <Fa...@epam.com>.
> -----Original Message-----
> From: Martin Sebor [mailto:sebor@roguewave.com]
> Sent: Monday, July 09, 2007 10:05 PM
> To: stdcxx-dev@incubator.apache.org
> Subject: Re: 23.deque.special
>
> > But in current implementation iterator not invalidated. Yes, it's
> > mebmers has changed, but it's still valid "end iterator".
>
> But it doesn't point to the right container. Unless I'm still
> missing something this needs to pass:
No. It point to the right container.
std::deque<int> x, y;
x._C_end._C_node always == &x._C_end._C_cur for empty container x
This condition is required by current design (include/deque, line 663)
void _C_init () {
// clear both `beg.cur' and `end.cur' and set both `beg.node'
// and `end.node' to point to `end.cur' (instead of 0) to avoid
// having to check before dereferencing the pointers
_C_beg =
_C_end = _C_deque_iter (pointer (), &_C_end._C_cur);
_C_nodes = _C_node_pointer ();
_C_node_size = 0;
}
After x.swap (y) operation x._C_end._C_node still should point to
&x._C_end._C_cur,
but not to &y._C_end._C_cur to be a valid "end iterator" of the
container x.
> > If we decide to set deque<>._C_end._C_node = 0 for end
> iterator of
> > empty deque It would be a big change (we should change the
> all places
> > where _C_end._C_node member dereferenced).
>
> Couldn't we just repoint _C_end._C_node in swap()?
http://svn.apache.org/viewvc?view=rev&revision=507940
Here I repoint _C_end._C_node to the value required by current design
after binary _STD::swap (_C_end, __rhs._C_end);
Farid.
Re: 23.deque.special
Posted by Martin Sebor <se...@roguewave.com>.
Farid Zaripov wrote:
[...]
>>>> 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.
>> But that would only hide the bug. swapping empty deques needs
>> to work (and not invalidate iterators) just as well as
>> swapping ones with elements.
>
> But in current implementation iterator not invalidated. Yes, it's
> mebmers
> has changed, but it's still valid "end iterator".
But it doesn't point to the right container. Unless I'm still
missing something this needs to pass:
#include <assert.h>
#include <deque>
int main ()
{
std::deque<int> x, y;
std::deque<int>::iterator i = x.begin (), j = x.end ();
std::deque<int>::iterator k = y.begin (), l = y.end ();
std::swap (x, y);
assert (i == y.begin () && j == y.end ());
assert (k == y.begin () && l == y.end ());
}
>
> If we decide to set deque<>._C_end._C_node = 0 for end iterator of
> empty
> deque It would be a big change (we should change the all places where
> _C_end._C_node member dereferenced).
Couldn't we just repoint _C_end._C_node in swap()? I thought
that's what we were doing anyway so I guess I still don't fully
understand the problem.
Martin
RE: 23.deque.special
Posted by Farid Zaripov <Fa...@epam.com>.
> -----Original Message-----
> From: Martin Sebor [mailto:sebor@roguewave.com]
> Sent: Monday, July 09, 2007 8:05 PM
> To: stdcxx-dev@incubator.apache.org
> Subject: Re: 23.deque.special
>
> Right, I think that will be necessary. I was under the
> impression that you already did that in the change below but
> now that I've re-read it I think that issue might be about
> something else.
>
> http://svn.apache.org/viewvc?view=rev&revision=507940
In this change I just corrected _C_begin and _C_end members
of empty deque after swap operaton.
> >
> >> 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.
>
> But that would only hide the bug. swapping empty deques needs
> to work (and not invalidate iterators) just as well as
> swapping ones with elements.
But in current implementation iterator not invalidated. Yes, it's
mebmers
has changed, but it's still valid "end iterator".
If we decide to set deque<>._C_end._C_node = 0 for end iterator of
empty
deque It would be a big change (we should change the all places where
_C_end._C_node member dereferenced).
Farid.
Re: 23.deque.special
Posted by Martin Sebor <se...@roguewave.com>.
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.
Right, I think that will be necessary. I was under the impression
that you already did that in the change below but now that I've
re-read it I think that issue might be about something else.
http://svn.apache.org/viewvc?view=rev&revision=507940
>
>> 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.
But that would only hide the bug. swapping empty deques needs to
work (and not invalidate iterators) just as well as swapping ones
with elements.
Martin
RE: 23.deque.special
Posted by Farid Zaripov <Fa...@epam.com>.
> -----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.
Re: 23.deque.special
Posted by Martin Sebor <se...@roguewave.com>.
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. Swapping two deques is required not to
invalidate any iterators, isn't that right? Are you suggesting to
loosen the test so as not to exercise this requirement?
Martin
>
> I think that this part should be replaced to just checking
> deque.begin() == deque.end() after (and perhaps, before) the swap
> operation.
>
> --------------
> typedef std::deque<T, std::allocator<T> > MyDeque;
> typedef typename MyDeque::iterator Iterator;
>
> // create two empty deque objects
> MyDeque empty [2];
>
> // save their begin and end iterators before calling swap
> const Iterator before [2][2] = {
> { empty [0].begin (), empty [0].end () },
> { empty [1].begin (), empty [1].end () }
> };
>
> // swap the two containers
> empty [0].swap (empty [1]);
>
> // get the new begin and end iterators
> const Iterator after [2][2] = {
> { empty [0].begin (), empty [0].end () },
> { empty [1].begin (), empty [1].end () }
> };
>
> // verify that the iterators have not been invalidated
> rw_assert ( before [0][0] == after [1][0]
> && before [1][0] == after [0][0], 0, __LINE__,
> "deque<%s>().begin() not swapped", tname);
>
> rw_assert ( before [0][1] == after [1][1]
> && before [1][1] == after [0][1], 0, __LINE__,
> "deque<%s>().end() not swapped", tname);
> --------------
>
> Farid.
>