Choosing the Right swap() Implementation

wap() is one of those tricky algorithms that has several implementations, each of which offers its own advantages and disadvantages. In the following sections I will show why familiarity with these implementations may be beneficial, albeit for different reasons than you might think.



The Standard Template Library offers a ready-made generic swap() algorithm (in the form of std::swap() which is defined in ). Still, there are several other implementations of this algorithm. How do you choose which implementation to use? On which criteria should your evaluation be based?



Familiarize yourself with other implementations of swap(). Then, base your evaluation on the following criteria: performance, ease of maintenance, and genericity.

Step 1: Textbook swap()
The implementation of the plain, vanilla swap() algorithm is straightforward: take two arguments of the same type, copy the first one to a temporary variable, assign the second to the first, and finally, assign the temporary value to the second. Here is the complete function template:

 template void v_swap(T& t1, T& t2)//plain vanilla{ T temp=t1; t1=t2; t2=temp;}

This implementation has a prominent advantage: it’s generic. As such, it’s applicable to built-in types and user-defined types alike. Not very surprisingly, this is exactly how the std::swap() is implemented so there’s no need to reinvent the wheel if you wish to use this version. What about performance? In order to evaluate it, let’s compare this implementation to other implementations.

Step 2: Swapping Without a Temporary
A common question in college exams and job interviews is: “Can you write a swap() function that doesn’t use a temporary variable?” As the question implies, it is possible to get rid of the temporary variable. The trick is to use the += and -= operators, thereby performing two operations in a single expression. Here is the complete implementation of this function template:

template  void nt_swap(T& i, T& j) //no temporary{   i -= j;   j += i; // j gets the original value of i   i = (j - i); // i gets the original value of j}

In terms of readability, this version is more cryptic than v_swap(). As for genericity, this implementation is applicable to built-in types and user-defined types that overload the += and -= properly. For unknown reasons, people believe that this version should be faster because of the omission of a temporary variable. To compare the performance of these two swap() implementations, I’ll use two loops that call each of these functions 50,000,000 times and measure their speed using the good old stopwatch class (you may change the number of iterations to adjust the test program for different hardware and compiler setting). The complete program looks as follows:

int num=5000000; //adjust this value as needed//for the sake of brevity, the definition //of class stopwatch was omittedint main(){ { //We use a block to automate the construction   //and destruction of the stopwatch object  int n=5,m=10;  stopwatch s;  for (int i=0; i>num; //just to delay output on the screen}

On my machine, the non-optimized debug version of this program didn’t exhibit statistically-significant differences between the two swap() implementations when applied to integers. When applied to double, the plain vanilla wins big time. Its execution speed was less than a third of nt_swap()’s execution speed!

Step 3: Swapping Without a Temporary, Take II
Another common variant of swap() uses the bitwise operators to eliminate a temporary variable. The snag is that this version can only take arguments of integral types. That is why I didn’t use a template in this case:

void nt2_swap(int& i, int& j)//temporary-free, 2nd version{ i ^= j; j ^= i; i ^= j;}// i and j have been swapped

Clearly, the type-dependence of this algorithm severely restricts its usefulness. In terms of readability, it’s even more cryptic than nt_swap(). Performance-wise, this implementation doesn’t differ significantly from the previous two.

Favor Efficiency
Cuteness hurts,” says C++ guru Herb Sutter, and rightfully so. Comparing swap() implementations yields an important lesson: the road to convoluted, hard to maintain, and inefficient code is paved with programs that try to be cute. Not only does plain, vanilla swap() turn out to be at least as efficient as the other two implementations, it is also completely generic, readable?and most importantly, you don’t have to write it from scratch. The more general lesson to take home is that whenever you have several possible implementations of a certain component, you should prefer the one that’s available in the Standard Library, as it’s also the most efficient one in most cases. Finally, if you prefer to evaluate several different implementations, base your decision on empirical tests and sound criteria rather than myths and gut feeling.

Indeed, familiarity with nt_swap() and nt2_swap() might be useful in certain cases: when maintaining legacy code orwhen applying for a new job. However, in production code, std::swap() is the preferable choice.

Share the Post:
Share on facebook
Share on twitter
Share on linkedin

Overview

Recent Articles: