“The time has come…to talk of many [technologies].” –Lewis Carroll(‘The Walrus and the Carpenter’)
Don’t Let the “Smart” Way to Write the Swap Function in C++ Fool You
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:
[cpp]
template
void swap(T &a, T &b)
{
T t = a;
a = b;
b = t;
}
[/cpp]
Simple, straightforward, and correct.
The second, wrong version goes like this:
[cpp]
template
void swap(T &a, T &b)
{
a = a + b;
b = a – b;
a = a – b;
}
[/cpp]
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!
[cpp]
int a;
//read something into a
::swap(a, a); //BOOM! ‘a’ is now corrupted and beyond recovery.
[/cpp]
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.
[cpp]
int a;
//read something into a
::swap(a, a); //BOOM! ‘a’ is now corrupted and beyond recovery.
[/cpp]
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.
11 comments
someone (1333 days)
>>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.
Anonymous (1333 days)
Anonymous (1333 days)
You might also want to consider doing your homework by reading http://en.wikipedia.org/wiki/XOR_swap_algorithm
Michael (1333 days)
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.
tabrez (1333 days)
@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.
Michael (1332 days)
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.
tabrez (1331 days)
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.
Anonymous (1287 days)
yibu (492 days)
I don’t know where the author got the idea of the second version. The “add/subtract” version and “xor” version were clearly mentioned only in the context of integer swapping. To make them even compile for user-defined types, you need to define operator “+”, “-” for that type, which may make it still work if properly designed.
And, have you given it enough thoughts when you say “The code fails even for the integers when the the sum of two passed variables exceeds the maximum integer limit on that machine.”?
yibu (492 days)
I tested three versions of integer swapping methods (temp storage, xor, add/subtract) on my laptop (Intel X86, Linux, gcc). Here’s the conclusion:
With moderate compiler optimization: all three are roughly the same.
Without optimization: the traditional (temp storage) method is significantly FASTER than the other two.
I started to test the performance because Wikepedia is saying that temp storage method is probably faster on current architecture due to instruction pipelining and the other two method must be executed sequentially thus no parallelism can be exploited. And my testing result just proved that.
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.