Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

iter_swap() versus swap() -- what's the difference?

Tags:

c++

swap

MSDN says:

swap should be used in preference to iter_swap, which was included in the C++ Standard for backward compatibility.

But comp.std.c++ says:

Most STL algorithms operate on iterator ranges. It therefore makes sense to use iter_swap when swapping elements within those ranges, since that is its intended purpose --- swapping the elements pointed to by two iterators. This allows optimizations for node-based sequences such as std::list, whereby the nodes are just relinked, rather than the data actually being swapped.

So which one is correct? Should I use iter_swap, or should I use swap? (Is iter_swap only for backwards compatibility?) Why?

like image 953
user541686 Avatar asked Dec 24 '12 17:12

user541686


People also ask

What does iter_ swap do c++?

std::iter_swap in C++ It simply exchanges the values of the elements pointed to by the iterators.

How to swap two elements in a Vector c++?

The std::swap() is a built-in function in C++ STL which swaps the value of any two variables passed to it as parameters. The std::vector::swap() function is used to swap the entire contents of one vector with another vector of same type.


2 Answers

The standard itself has very few mentions of iter_swap:

  • It should have the effect of swap(*a, *b), although there is no stipulation that it must be implemented that way.
  • The dereferenced values *a and *b must be "swappable", which implies that swap(*a, *b) must be valid, and thus the dereferenced types must be identical, although the iterator types do not have to be.
  • iter_swap is required to be used in the implementation of std::reverse. No such requirement is placed on any other algorithm, so this seems to be an oddity.

To borrow what sehe had found from the SGI docs:

Strictly speaking, iter_swap is redundant. It exists only for technical reasons: in some circumstances, some compilers have difficulty performing the type deduction required to interpret swap(*a, *b).

All of these seem to suggest that it is an artifact of the past.

like image 63
Rufflewind Avatar answered Sep 19 '22 16:09

Rufflewind


This seems to be one of those scenarios in which the internet produces a host of conflicting information.

  • cplusplus.com says that iter_swap is identical to swap and, by that logic, MSDN would be correct in saying that one ought to simply stick to swap.

  • cppreference.com tells us that calling swap is merely a possible implementation for iter_swap, opening the door for possible optimisations in iter_swap for certain specialisations, as long as the function's constant complexity guarantee is upheld.

The standard, under [C++11: 25.3.3/5], says only that iter_swap(a,b) has the result swap(*a,*b) (and requires that "a and b shall be dereferenceable", and that "*a shall be swappable with *b") which would at first glance correlate with MSDN's interpretation.

However, I believe Microsoft have neglected to consider the as-if rule, which should allow an implementation to make iter_swap faster than swap in certain cases (e.g. elements of a linked list).

I would therefore trust that the comp.std.c++ quote is the more technically accurate of the two.

That being said, there is a fairly strict limit on the optimisation that may be performed. Consider, for example, an implementation of iter_swap over linked list elements that simply re-links nodes rather than physically swapping the element values — this is not a valid implementation, because the requirement that iter_swap's observable behaviour match swap's is violated.

I would therefore suggest that in practice there can be little if any benefit to preferring iter_swap over swap, and I'd recommend sticking to the latter for simplicity and consistency. C++11 move semantics ought to make swap a cinch in many cases anyway.

like image 30
Lightness Races in Orbit Avatar answered Sep 17 '22 16:09

Lightness Races in Orbit