C++ Swap

Swapping is widely used in C++ for its potential efficiency benefit, well, in the cases where value swapping is required. A lot of C++ algorithms (such as std::sort) uses swapping. The other big advantage is that non-throwing swap is often used in the copy-and-swap idiom for strong exception guarantee (and less code duplication).

Support Swap For Your Type

As said above, if you are writing a new class (or class template) T, it makes sense to provide swapping support for T. Effective C++ by Scott Meyers (Item 25) discusses this in-depth. There has also been lengthy discussions at StackOverflow (here, here, and here for example) about best practices in enabling swap.  So this is a summary:

  • Provide a swap member function void T::swap(T& other).
    • We need this function because it has access to T’s internal guts including base class objects, and has the full competence to carry out swapping.
      • An alternative is to make a non-member swap function friend, see below.
    • Consider to provide noexcept guarantee for the function, if possible.
  • Provide a non-member free function void swap(T& a, T& b) in the same namespace of T. This function simply calls void T::swap(T& other).
    • We need this free function, because this is how libraries, such as standard C++ library algorithms (like std::sort) use it.
      • The libraries use the free swap function, because the same code has to work on types like int, and float, where member swap function is impossible.
    • The free function must be in the same namespace as T, such that at the calling site the compiler can resolve to this function through ADL (Argument-Dependent Lookup, i.e., Koenig Lookup).
    • Consider to provide noexcept guarantee for the function, if possible.
    • I often put the free function in the class T definition as an inline friend. It’s both clear interface (like part of the class) and has good source code locality.

That’s it. Your class or class template is now swapping enabled properly. For example:

class T
{
public:
    void swap(T& other) { … }  // real work
    friend inline void swap(T& a, T& b) { a.swap(b); } // (harmless friend) free function in the namespace of T
    …
};

std::swap

Remember there is a standard function template std::swap: template<class T> void swap(T& a, T& b). This is the default swap function for all types, e.g., when your class T does not have its own swapping support. The calling site will resolve to std::swap if you do not provide your own swap support above. std::swap is in C++03 25.2.2 <algorithm>, but moved to C++11 20.2.2 <utility>, because the basic form is not coherent with other functions in <algorithm>.

std::swap differs in C++03 and C++11:

  • C++03 requires T to be CopyConstructible and Assignable; C++11 requires T to be MoveConstructible and MoveAssignable. This basically means:
    • C++03 std::swap uses one copy construction to create a temporary T object, then two assignments to swap the values;
    • C++11 std::swap uses one move construction to create a temp T object, then two move assignments to swap the guts.
    • C++11 version is more efficient in a lot of cases.
  • C++03 says nothing about exception; C++11 has noexcept(noexcept(std::is_nothrow_move_constructible<T>::value && std::is_nothrow_move_assignable<T>::value)).
    • C++03’s swap may throw if T’s copy constructor or assignment operator can throw. This could happen if T’s copy constructor and assignment operator involve memory allocation. So C++03 does not impose anything here.
    • C++11’s swap does not throw if T’s move constructor and move assignment operator do not throw. A lot of T types shall try to achieve noexcept move constructor/assignment operator, as moving is supposed to be efficient and has less complications.

As you can see, if your class T provides decently implemented move constructor and move assignment operator, you may skip implementing swap for your type, because std::swap may work well enough for your type in C++11. This is implementing swap using move.

Do not attempt to call swap (in turn std::swap) on your class T to implement move assignment operator or move constructor, however. Since std::swap calls them, this creates a circular call loop and results in run-time stack overflow. After all, somebody has to do the real work. You cannot get both swapping and moving for free for T.

When implementing T’s move constructor or move assignment operator (or T’s swap directly), you may use swap on T’s base class and member objects; in fact this is recommended and you should do this whenever possible. See below for proper using of swap.

How To Support Swap Wrong

Here is a list of wrong practices regarding provide swapping for your class or class template T:

  • Overload std::swap, i.e., inject this function into namespace std: void std::swap(T& a, T& b). The namespace std is controlled by the C++ standard, and no new foreign introduction is allowed. Adding a new function there is simply wrong.
  • Specialize std::swap for T, i.e.: namespace std { template<> void swap<T>(T& a, T& b) {…} }. Specialize the standard function template is legal. This method works for a class T. However, it does not if T is a class template. In C++ a function template (such as std::swap) cannot be partially specialized (only function overloading is possible). This does not compile: namespace std { template<U> void swap<T<U>>(T<U>& a, T<U>& b) {…} }
    • Scott Meyers recommends to specialize std::swap for classes (in addition to the correct swap implementation above), and then forward to the member swap function. He believes there are people who use swap incorrectly by calling std::swap. Providing the specialized std::swap route the calls to the right swap. This is however disagreed by a lot of C++ programmers, because it is believed that those who incorrectly call std::swap should fix their problems.
  • Provide static swap member function of T, i.e.: struct T { static void swap(T& a, T& b) {} }; It’s mentioned by a StackOverflow user, but immediately dismissed. It is not useful because every call has to be scoped like T::swap(), therefore hard to write generic code.
  • Provide a free swap function in global namespace for T. This does work. But why polluting the global namespace?

Using Swap Properly

Using swap correctly needs two points:

  • The call to swap on T should resolve to T’s specific swap support, if available;
  • If there is not T’s specific swap support, the call should resolve to std::swap.

It is in fact very simple to write the correct code when using swap:

#include <utility>  // access std::swap in C++11.  In C++03, use <algorithm>

void foo(T& a, T& b)
{
    using std::swap;  // (1)
    swap(a,b);        // (2)
}

Line (1) makes std::swap visible to the call site, so in case T-specific swap is not there, the std::swap will be used. Line (2) uses a non-qualified swap() call. This is important, because this allows the ADL to find the swap function for T in the namespace where T’s defined.

Swap Multiple Items Or Indirectly

There are cases that you need to swap the items between two containers. If it is equivalent to swapping two container objects, it is often much cheaper than element-wise swapping. But there are cases that element-wise swapping is necessary, for example, swapping sub-sequences of two containers. Swapping two built-in arrays (T[]) also has to be done element-wise, because there is no indirection.

In C++03 and C++11, you can find std::swap_ranges in <algorithm>:

template<class ForwardIterator1, class ForwardIterator2>
    ForwardIterator2 swap_ranges(ForwardIterator1first1, ForwardIterator1last1, ForwardIterator2first2); // C++03 and C++11

C++11 also provides an overloaded std::swap for built-in arrays in <utility> (along with non-array swap 20.2.2):

template<class T2, size_t N>
    void swap( T2 (&a)[N], T2 (&b)[N]); // C++11

All above require individual elements to be swappable, and essentially call swap through ADL on all elements in a for loop.

Finally, if you have iterators and want to swap the objects pointed to by the iterators, you can call std::iter_swap in <algorithm>:

template<class ForwardIterator1, class ForwardIterator2>
    void iter_swap(ForwardIterator1 a, ForwardIterator2 b); // C++03, C++11

It just does swap(*a, *b) for you properly.

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 42 other followers

%d bloggers like this: