Login | Register   
LinkedIn
Google+
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


advertisement
 

Choosing the Right swap() Implementation : Page 2

Though the Standard Template Library offers a generic swap() algorithm, there are several other implementations from which to choose. Which implementation best suits your program's needs? This month's solution shows you how to evaluate each of them, enabling you to utilize each implementation to its greatest benefit.


advertisement
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 <class T> 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 omitted int 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; i++) v_swap(n,m); //plain vanilla swap() } { int n=5,m=10; stopwatch s; for (int i=0; i<num; i++) nt_swap(n,m); //temporary-free swap } cin>>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.



Danny Kalev is a system analyst and software engineer with 15 years of experience, specializing in C++ and object-oriented analysis and design. He was a member of the ANSI C++ standardization committee between 1997-2001. Danny is the author of ANSI/ISO C++ Professional Programmer's Handbook and the C++ Section Leader for DevX He can be reached at dannykk@inter.net.il
Comment and Contribute

 

 

 

 

 


(Maximum characters: 1200). You have 1200 characters left.

 

 

Sitemap
Thanks for your registration, follow us on our social networks to keep up-to-date