Title
iter_swap underspecified
Status
cd1
Section
[alg.swap]
Submitter
Andrew Koenig

Created on 1999-08-14.00:00:00 last changed 164 months ago

Messages

Date: 2010-10-21.18:28:33

Rationale:

It's useful to say just what iter_swap does. There may be some iterators for which we want to specialize iter_swap, but the fully general version should have a general specification.

Note that in the specific case of list<T>::iterator, iter_swap should not be specialized as suggested above. That would do much more than exchanging the two iterators' values: it would change predecessor/successor relationships, possibly moving the iterator from one list to another. That would surely be inappropriate.

Date: 2010-10-21.18:28:33

Proposed resolution:

Change the effect clause of iter_swap in 25.2.2 paragraph 7 from:

Exchanges the values pointed to by the two iterators a and b.

to

swap(*a, *b).

Date: 2010-10-21.18:28:33

[ Kona: The LWG notes the original need for iter_swap was proxy iterators which are no longer permitted. ]

Date: 1999-08-14.00:00:00

The description of iter_swap in 25.2.2 paragraph 7,says that it ``exchanges the values'' of the objects to which two iterators refer.

What it doesn't say is whether it does so using swap or using the assignment operator and copy constructor.

This question is an important one to answer, because swap is specialized to work efficiently for standard containers.
For example:

vector<int> v1, v2;
iter_swap(&v1, &v2);

Is this call to iter_swap equivalent to calling swap(v1, v2)?  Or is it equivalent to

{
vector<int> temp = v1;
v1 = v2;
v2 = temp;
}

The first alternative is O(1); the second is O(n).

A LWG member, Dave Abrahams, comments:

Not an objection necessarily, but I want to point out the cost of that requirement:

iter_swap(list<T>::iterator, list<T>::iterator)

can currently be specialized to be more efficient than iter_swap(T*,T*) for many T (by using splicing). Your proposal would make that optimization illegal. 

History
Date User Action Args
2010-10-21 18:28:33adminsetmessages: + msg1801
2010-10-21 18:28:33adminsetmessages: + msg1800
2010-10-21 18:28:33adminsetmessages: + msg1799
1999-08-14 00:00:00admincreate