TechWire

The perfect swap in C++

So you are coding this cool app and you need to swap two variables. How does a good programmer do that in C++? The STL (Standard Templates Library) provides the std::swap function which does exactly what we want.

[code language=”cpp”]int a = 10;
int b = 12;
std::swap(a, b);[/code]

That’s easy. But hey, why don’t we go ahead and see actually what std::swap does behind the scenes? A grep in the Apache STL implementation gives us:

[code language=”cpp”]template <class _TypeT>
inline void swap (_TypeT& __a, _TypeT& __b)
{
   _TypeT __tmp = __a;
   __a = __b;
  __b = __tmp;
}[/code]

Woah, all the underscores! But don’t panic just yet. All it does is the grade-school swapping:

[code language=”cpp”]T tmp = a;
a = b;
b = tmp;[/code]

Hmm. That is perhaps the most straight-forward swap implementation. But how does it perform? Look again.

[code language=”cpp”]T tmp = a; // a copy of ‘a’ is created
a = b;  // a copy of ‘b’ is created
b = tmp;  // a copy of ‘tmp’ is created[/code]

That’s a lot of copies for a simple function! What if we could just ‘swap’ the two values without copying?

We google around a bit and find out that the above std::swap implementation is actually the old way of doing things. The new C++11 implementations does this differently. So we check the C++11 include files.

[code language=”cpp”]template<typename _Tp>
  inline void
swap(_Tp& __a, _Tp& __b)
   {
   _Tp __tmp = _GLIBCXX_MOVE(__a);
  __a = _GLIBCXX_MOVE(__b);
   __b = _GLIBCXX_MOVE(__tmp);
  }[/code]

That’s more confusing than the previous one. Again, don’t panic. We can simplify the things. _GLIBCXX_MOVE is defined to be std::move. Let’s just call it ‘move’. So the above function is roughly similar to:

[code language=”cpp”]T tmp = move(a);
a = move(b);
b = move(tmp);[/code]

Now we are scratching our chins. At first glance, the implementation looks much similar to the grade-school swap. And then, there’s this move-thingy. Okay, looking back, we remember that the elements were ‘copied’ in the grade-school algorithm. Instead, it looks like the variables are ‘moved’ here.

And we are right! In the first line, tmp is set to the value of a, while the variable a is (temporarily) invalidated. No copying is done. The previous memory location of a is now the territory of tmp. In the next line, a is set to the value of b, while b is invalidated. Finally, b is set to the value of tmp, and tmp itself is invalidated, which we don’t need again anyway. And the result? The two values are swapped without any copy operations!

How does this moving really work? C++11 introduces the so called “rvalue references”. The ‘move’ function returns the rvalue of the input parameter without triggering a copy construction.

[code language=”cpp”]T &a = x; // normal (lvalue) reference
T &&b = y; // rvalue reference [/code]

A full description will not fit in this post, but you can go through this nice little introduction on rvalue references. You might also want to refresh your memory about lvalues and rvalues.

And let’s call it a day and meet again with another little C++ adventure.

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2027.html

      

About author View all posts Author website

Thameera Senanayaka

Engineer. Loves tic-tac.

2 CommentsLeave a comment

Leave a Reply

Your email address will not be published. Required fields are marked *