Does std::vector::swap invalidate iterators?

Question

If I swap two vectors, will their iterators remain valid, now just pointing to the "other" container, or will the iterator be invalidated?

That is, given:

using namespace std;
vector<int> x(42, 42);
vector<int> y;
vector<int>::iterator a = x.begin(); 
vector<int>::iterator b = x.end();

x.swap(y);

// a and b still valid? Pointing to x or y?

It seems the std mentions nothing about this:

[n3092 - 23.3.6.2]

void swap(vector<T,Allocator>& x);

Effects: Exchanges the contents and capacity() of *this with that of x.

Note that since I'm on VS 2005 I'm also interested in the effects of iterator debug checks etc. (_SECURE_SCL)

Answer 1

The behavior of swap has been clarified considerably in C++11, in large part to permit the Standard Library algorithms to use argument dependent lookup (ADL) to find swap functions for user-defined types. C++11 adds a swappable concept (C++11 §17.6.3.2[swappable.requirements]) to make this legal (and required).

The text in the C++11 language standard that addresses your question is the following text from the container requirements (§23.2.1[container.requirements.general]/8), which defines the behavior of the swap member function of a container:

Every iterator referring to an element in one container before the swap shall refer to the same element in the other container after the swap.

It is unspecified whether an iterator with value a.end() before the swap will have value b.end() after the swap.

In your example, a is guaranteed to be valid after the swap, but b is not because it is an end iterator. The reason end iterators are not guaranteed to be valid is explained in a note at §23.2.1/10:

[Note: the end() iterator does not refer to any element, so it may be invalidated. --end note]

This is the same behavior that is defined in C++03, just substantially clarified. The original language from C++03 is at C++03 §23.1/10:

no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped.

It's not immediately obvious in the original text, but the phrase "to the elements of the containers" is extremely important, because end() iterators do not point to elements.

Answer 2

Swapping two vectors does not invalidate the iterators, pointers, and references to its elements (C++03, 23.1.11).

Typically the iterator would contain knowledge of its container, and the swap operation maintains this for a given iterator.

In VC++ 10 the vector container is managed using this structure in <xutility>, for example:

struct _Container_proxy
{   // store head of iterator chain and back pointer
    _Container_proxy()
    : _Mycont(0), _Myfirstiter(0)
    {   // construct from pointers
    }

    const _Container_base12 *_Mycont;
    _Iterator_base12 *_Myfirstiter;
};

Answer 3

All iterators that refer to the elements of the containers remain valid

Answer 4

As for Visual Studio 2005, I have just tested it. I think it should always work, as the vector::swap function even contains an explicit step to swap everything:

 // vector-header
    void swap(_Myt& _Right)
        {   // exchange contents with _Right
        if (this->_Alval == _Right._Alval)
            {   // same allocator, swap control information

 #if _HAS_ITERATOR_DEBUGGING
            this->_Swap_all(_Right);
 #endif /* _HAS_ITERATOR_DEBUGGING */
 ...

The iterators point to their original elements in the now-swapped vector object. (I.e. w/rg to the OP, they first pointed to elements in x, after the swap they point to elements in y.)

Note that in the n3092 draft the requirement is laid out in §23.2.1/9 :

Every iterator referring to an element in one container before the swap shall refer to the same element in the other container after the swap.