Don't forget to swap!

STL swap member functions

Most of the STL containers have a member function called "swap". Swap does what the name implies -- it causes two objects to trade places.

My first thought when I read about the swap methods was to ask: "why bother writing such a thing?" Obviously swap can be easily accomplished like this:

SomeType tmp = firstItem; firstItem = secondItem; secondItem = tmp;

So why bother writing a specific "swap" method?

The answer is simple: optimization. Consider swapping two vectors using the above algorithm. Here's what has to happen:
  1. all the items in firstItem are copied into tmp.
  2. all the items in first item are deleted.
  3. all the items in second item are copied into firstItem.
  4. all the items in secondItem are deleted.
  5. all the items in tmp are copied into second item.
  6. all the items in tmp are deleted.
If firstItem and secondItem are large, this is a HUGE performance cost.

BUT!

If the container has a swap method, you can do this:

firstItem.swap(secondItem);
And, instead of all the above nasty copies, which are proportional to O(N), where N is the maximum number of objects in either firstItem or secondItem, we get a performance cost which is proportional to O(1).

How you might ask?

A vector consists of three pointers internally. To swap two vectors, you only need to swap the three pointers. The total cost is trivial compared to that of actually swapping the data in the vectors.

So whenever possible, use swap!

Using swap in non-obvious places

Swap can be used in more places than is immediately obvious. Consider this: if a function takes a pointer or reference to a variable, you can swap instead of returning the container. For example:
vector<int> vi = function();
In this case, there is a garanteed copy of every element in the return vector produced by function.

But! If you write the code like this:

vector<int> vi;
function(vi);
Then it is entirely possible that vi will returned via a swap and the return cost will be O(1) not O(N)!

std::swap()

Finally: the <algorithm> header fine defines a global free function template, swap<>() that can swap any two types. The default implementation for this function is a duplicate of the expensive swap algorith shown above. But, all the standard template library containers superseed this global function template such that if you swap two vectors, lists, maps, sets, etc, the specialized form just calls the class specific swap method -- guaranteeing maximal performance.

So if you write this code: 

    vector<int> v1; ...
    vector<int> v2; ...
    std::swap(v1,v2);
You are really getting a call like this:
v1.swap(v2);

Adding swap() to your own code

You too can add your own specialization to the global swap signature. This means that you can speed up your own class using the above techniques and make this available to any algorithm which understands the benefits of swap.

Be careful not create a maintenance problem though -- when people add new data structures to their classes, it is hard enough to remember maintain the copy constructor and operator=. You'll need a lot of comments to rememind yourself not to forget to swap.