iter_swap() versus swap() — what's the differe

问题:

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?

回答1:

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.

回答2:

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.

回答3:

Yes, they both do the same thing, when used properly. No, std::iter_swap is not deprecated (by being placed in the Standard's §D Compatibility features section). MSDN's quote is misleadingly dismissive. The issue is that it's inconvenient to use std::swap properly.

You should use iter_swap for the simple reason that it's a higher abstraction.

swap is commonly overloaded for user-defined types. The proper way to call it is

using std::swap;
swap( blah, bleh );

not simply

std::swap( blah, bleh );

This is ensconced in §17.6.3.2, in particular ¶3:

The context in which swap(t, u) and swap(u, t) are evaluated shall ensure that a binary non-member function named “swap” is selected via overload resolution (13.3) on a candidate set that includes:

— the two swap function templates defined in <utility> (20.2) and

— the lookup set produced by argument-dependent lookup (3.4.2).

iter_swap is not such a special overloaded name, and customizing its functionality requires adding a template specialization to namespace std {}.

---

Therefore, iter_swap usefully encapsulates the part of the Swappable interface which you would otherwise implement every time.

It is actually a more friendly interface, regardless of whether there's ever a semantic difference for your implementation and its particular arguments. (Not that potential optimizations of it should be overlooked. MSDN may give their opinion, but they can't anticipate what library authors might provide using "backwards compatibility interfaces.")

---

As for a specialization of iter_swap with an observably different result from swap( *a, *b ), that would seem to be nonconformant with the requirement §25.3.3/5,

Effects: swap(*a, *b).

The example you cite does sound like an observable difference, since pointers to *a and *b are both valid before and after the operation. That's unfortunately a bug in the library implementation.

回答4:

You have hit on the key distinction.

swap(*a, *b) is a global function that resets all pointers pointing to *a to point to what was the contents of *b and vice versa. It's the old tmp = a, a = b, b = tmp swap.

iter_swap is for the more limited case of modifying the underlying objects being iterated over to affect the structures of which they were a part. If *a and *b were part of the same linked list, it was sufficient for iter_swap to simply swap their positions in the list. This is an advantage for when you want to simply sort a list without invalidating/changing external pointers to objects in the list. If I have a pointer to a user object I don't care if you sort the list of user objects, I don't want my idea of who is the "current" user to change, so list sort better not use swap.

回答5:

Which one should you use? Depends on what you are using it for. Because the swap only works for objects, swapping two independent integers or strings or doubles. But the iter_swap works well for arrays and lists, in which you can swap numbers in two different lists as demonstrated on cplusplus.com

回答6:

Reading the laws carefully:

---

20.2.2 swap [utility.swap]

• template void swap(T& a, T& b) noexcept(is_nothrow_move_constructible::value && is_nothrow_move_assignable::value);

  2 Requires: Type T shall be MoveConstructible and MoveAssignable. (Table 20) and (Table 22)

  3 Effects: Exchanges values stored in two locations.

• template void swap(T (&a)[N], T (&b)[N]) noexcept(noexcept(swap(*a, *b)));

  4 Requires: a[i] shall be swappable with b[i] for all i in the range [0,N). (17.6.3.2)

  5 Effects: swap_ranges(a, a + N, b)

25.3.3 swap [alg.swap]

• template void iter_swap(ForwardIterator1 a, ForwardIterator2 b);

  5 Effects: swap(*a, *b).

  6 Requires: a and b shall be dereferenceable. *a shall be swappable with *b. (17.6.3.2)

---

Thus iter_swap is required to exchange the values stored in two dereferenced locations or ranges of dereferenced locations, and any attempt to exchange the references or locations themselves is fighting against conformance. That clearly disables speculating about optimizations being the reason lying behind std::iter_swap. Instead, as Potatoswatter was properly pointing out, encapsulation and abstraction are the main reasons of its existence. std::iter_swap and std::swap each belong to diferent abstraction layers, the same way std::swap itself and any binary non-member function named "swap" selected via overload resolution differ.

Swap developer and designer roles to understand achieving the same result does not mean being the same, as in "even declaring a typedef from a fundamental type is just noise for a compiler, it is not noise for the reader". Take it as a joke, but we could argue whole C++ is just a deprecatable artifact wraping C, since both do the same thing while in the lowest level, and so on with any code block representing abstraction from another by means of a wrapper. Specially when the line is so thin as in the case of std::iter_swap, "swap" and std::swap. Maybe "using std::swap" has only a few caracters and it disappears once compiled, but means injecting an identifier and building a whole overload resolution mechanism. Injected over and over, built over and over, replaced over and over, discarded over and over. Far from an abstract, encapsulated and recycled approach.

Exposing the inner work trought the upper layer gives and aditional potential chance of failure on maintenance. In the swap domain, missing (or messing) a "using std::swap" on a deep metaprogramming containment design will silently wait inside your template function, waiting for a trivially swappable, fundamental or c-array type to break the build, if lucky, or even StackOverflow(TM) by means of infinite recursion. Obviously implementation of an extensible mechanism has to be published, but also has to be respected. About trivially swappable, mind anything moveconstructible and moveassignable is swappable against its own type even if it lacks of an overloaded swap resolution hook, and indeed there are obscure techniques to disable unwanted swappable behaviors.

With that on mind, maybe it all can be resumed in an unproper interpretation of the std::iter_swap identifier itself: it does not stand for "iterator swapping", but "iterable swapping". Don't be fooled by the standard requirements on arguments being forward iterators: in essence, a pointer is a random access iterator, thus satisfying the requirements. Phisically u pass by pointer, logically u pass by iterator. The commission usually tries to specify the minimal requirements for a facility to work with defined and expected behavior, nothing more. The "iterable swapping" name rightly exposes the goal and powers of the mechanism. the "std::iter_swap" identifier seems not due to confusion generated, but it is too late to change it and undo all the codebase relying on.

Feel free to swap as u wish as long as it works, but please not on my watch. Mixing abstraction layers won't make the compiler cry, but interfaces are just too cool to avoid. Instead, here is a snippet to help guidance in the future:

//#include <utility> // std::swap is not required here
#include <algorithm> // std::iter_swap is

namespace linker {

    class base {
    };

    class member {
    };

    template<class M = member, class B = base> // requires swappable base and member
    class link : B {
    public:
        void swap(link &other) { // using iterable swapping
            std::iter_swap(static_cast<B*>(this), static_cast<B*>(&other));
            std::iter_swap(&_member, &other._member);
        }
    private:
        M _member;
    };

    template<class base, class member>
    void swap(link<base,member>& left, link<base,member>& right) { // extending iterable swapping
        left.swap(right);
    }

}

namespace processor {

    template<class A, class B>
    void process(A &a, B &b) { // using iterable swapping
        std::iter_swap(&a, &b);
    }

}

int main() {
#if !defined(PLEASE_NO_WEIRDNESS)
    typedef
        linker::link<
            linker::link<
                linker::link< int[1] >,
                linker::link< void*, linker::link<> >
            >[2],
            linker::link<
                linker::member[3]
            >
        >
    swappable[4]; // just an array of n-ary hierarchies
#else
    typedef linker::link<> swappable;
#endif
    swappable a, b;
    processor::process(a, b);
}

Some points of interest as aditional guidance:

• Swapping means thrown exceptions. Statement seems stupid, but it isn't once u know swap idiom is not focused on performance but on extreme safety and robustness.

• std::iter_swap showcase one of the many lovely but overlooked features of metaprogramming: a template not only does overload resolution but also namespace resolution, allowing its use as the first in a chain of unknown and unrelated namespaces. Thanks, one thing less to worry about.

• Swappable requirements allows u to use std::swap directly if (and ONLY IF) u can afford making the assumption of both targets being of fundamental or c-array to fundamental types, thus allowing the compiler to bypass any overload resolution. Sadly that rules out the parameters of almost every template. Using std::swap directly implies both targets are of the same type (or forced to be of the same type).

• Don't waste efforts on declaring swapable capabilities on a type wich already is trivially swappable with itself, just like our link template class (try removing linker::swap, behavior won't change at all).
  “swap” was designed to be extensible to swap from diferent types,
  automatic for same types. Mind a type is not "swappable" or
  "non-swappable" by itself, but "swappable-with" or
  "non-swappable-with" another type.

Finally, I wonder how many readers will notice

• 20.2.2 swap [utility.swap]

• 25.3.3 swap [alg.swap]

and recognize an utility is not an algorithm. In the Microsoft-Dinkumware implementation, among others, std::iter_swap just lives in the wrong header for convenience, wich isn't wrong. Maybe just it's identifier is.

---

Edit: After being faced with some more related mistakes, tought i could sumarize them like this: an algorithm is a concept so generic and specific, every time someone is about to specialize one of them, a designer cries somewhere else. In the case of std::iter_swap, since commitee clearly gives no freedom, any attempt to tweak the algorithm as in the relinking speculations would deserve a different meaning and identifier. Also maybe someone missed containers do have a swap member function, where optimizations do apply.

Better refactor so your final layer objects are nondata, fundamental, or represent hidden heavier objects (streamed if heavy enough). Embrace that resource adquisition should be initialization (RAII) and both new-delete overloads and container allocators have a use, to unleash true swap benefits with zero aditional effort. Optimize resources so u move data only on readquisition, then let C++ design your types easy, safe and fast by default.

Motto: Back in the old days, people struggled with data that was too fat on memory, too slow on disk. Nowadays, iterator vectors are filtered from storage pools, and streamed to be processed in parallel pipes. Tomorrow cars will drive alone. Deserves a PostIt.