Over the years many beginning programmers have shown me two different versions of C++ code for swapping the values of two variables. I am now starting to get tired of correcting the wrong version of the two, especially because of the disappointment that I get to see written on the face of those who thought theirs to be a very clever way of writing code. (Even if the version was correct, I don't know why they take such personal pride in the code. Obviously they have not invented the code; it has been circling the Internet or the general student community for many years, from where they have merely copied it.)
The first and the correct version for swapping values of two variables, in C++, is like this:
C++:
template<typename T>
void swap(T &a, T &b)
{
T t = a;
a = b;
b = t;
}
Simple, straightforward, and correct.
The second, wrong version goes like this:
C++:
template<typename T>
void swap(T &a, T &b)
{
a = a + b;
b = a - b;
a = a - b;
}
The openly asserted advantage of this version is that one variable is saved in this case. But the real, hidden attraction is that it appears to be smartly written code. If only the version was correct too. The problem with this version, of course, is that it is useless for any type that doesn't support arithmetic operations. It works fine for integer type for example, most of the times at least. It is not guaranteed to work even for floating point variables. But what if I want to swap the values of two Colour objects? Two Shape objects? The requirement that the type support addition and subtraction operations for its objects to be swappable is very absurd.
More problems with the second "smart" version:
The code fails utterly when you pass references to the same variable!
C++:
int a;
//read something into a
::swap(a, a); //BOOM! 'a' is now corrupted and beyond recovery.
The call to swap() in this case should have been a "no operation" like it will be with the first version.
The code fails even for the integers when the the sum of two passed variables exceeds the maximum integer limit on that machine. The code is also needlessly unnatural. Human beings don't swap things by indulging in addition and subtraction activities. Unless a person knows that the second version works for at least the integer type (some of the times), or verifies it manually by working through it logically or with a large number of example cases, it is difficult to just see and "get" that the code indeed does the swapping operation. The second version indeed uses one less variable than the first version but at the same time uses three additional arithmetic operations.
There are similar clever ways to swap two variables(using XOR operation, or macros for example), but all of them have one or more problems of similar kind. The best way to swap two variables is definitely the natural way to do it. By the way, parts of the above explanation apply to swapping variables in most other languages too(can't think one where it doesn't). Clever code is useless code if it isn't also correct at the same time.
Related Posts:
so why not do it *the right way* and just use bitwise xor?
a = a xor b
b = a xor b
a = a xor b
correct(the contract should specify that the references passed in may not be equal), works for all data types, and saves one precious variable.
Comment by Anonymous — June 22, 2008 @ 11:04 pm
>>so why not do it *the right way* and just use bitwise xor?
I certainly hope you aren't doing this with polymorphic objects. Please do not do bitwise operations on polymorphic objects. If you don't know why please do not ever write code again. Also whoever wrote that second version, stop coding as well. You are asinine and dangerous.
Comment by someone — June 23, 2008 @ 6:25 am
Instead of calling people asinine you might want to consider giving an argument for what you're claiming...just a suggestion though.
Comment by Anonymous — June 23, 2008 @ 8:09 am
You might also want to consider doing your homework by reading http://en.wikipedia.org/wiki/XOR_swap_algorithm
Comment by Anonymous — June 23, 2008 @ 8:14 am
All of your ways are wrong.
The only correct way of swapping is don't bother writing your own swap. Use std::swap directly if you can, call it if you cannot.
std::swap(a, b).
Done. Never reinvent your own wheel.
Your 1st way is wrong because it doesn't have a "nothrow" guarantee. It's especially important when memory is tight.
Comment by Michael — June 23, 2008 @ 10:51 am
@Anonymous,
@someone is correct, swapping done using xor operator is not a smart way either. It will take up a few lines to explain the reasons, but as @someone said you can lookup why you shouldn't pass arrays polymorphically to understand why xor version of swapping won't work for polymorphic objects.
@Michael,
If you are creating an application in C++ and you want to swap two variables, you most definitely would use std::swap function. If you read carefully, I was talking about people who are starting to learn programming, and hence need to write their own swap, search, sort etc. functions. The exercise clears up points like the ones discussed in this post.
I didn't even bother to make the swap function inline; my example focussed only on the right way to do the swapping. But I will post the std::swap functions as implemented by major STL implementors to show how simple they actually are.
Comment by tabrez — June 23, 2008 @ 3:34 pm
Hm...that's interesting. Teaching people who are starting to learn programming to use C++ templates doesn't sound like the right tool for the right job.
I suppose if someone is at the level of using templates, the concept of exception safety should be introduced somewhere close.
For someone who's new, I'd let them start with Ruby, Javascript, Logo, Object Pascal, or even Java. C++ sounds like a poor choice for an introductory language.
Comment by Michael — June 24, 2008 @ 3:58 am
Most people who learn C++ already know either Java, Python or C#. They still need to know how to swap two variables in C++. Templates are no more a beastly topic as it was once considered to be; most people teach basics of templates right from the very first classes, enough to get comfortable with the syntax of STL containers and algorithms. Writing the swap function in C++ without using templates is an utterly useless activity in my opinion.
Comment by tabrez — June 25, 2008 @ 5:28 pm
on June 22, 2008 at 11:04 pm said:
so why not do it *the right way* and just use bitwise xor?
a = a xor b
b = a xor b
a = a xor b
correct(the contract should specify that the references passed in may not be equal), works for all data types, and saves one precious variable.
Comment by Anonymous — August 8, 2008 @ 10:39 am
