Re: STDCXX-635 and iterator validitty after deque::swap()

[Mark Brown]

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 [EMAIL PROTECTED] 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.