Last week I introduced swapping, and mentioned that is it often faster than assignment — a fact that often allows algorithms that swap to be dramatically faster than they would be if they used assignment. Here's why.

C++ requires all objects of a given class to have the same size, and for the size to be known during compilation. This requirement makes it possible for the compiler to lay out each function's stack memory during compilation, thereby making it much easier to generate efficient machine code.

Of course, this requirement conflicts with the desire for variable-sized data structures such as strings and vectors. The C++ library deals with this conflict by implementing each such data structure as a fixed-size part, which resides in each object, and a variable-size part, which the library allocates and frees dynamically. A string or vector therefore consists typically of a small amount of information that includes a pointer to dynamic memory containing the actual data.

Copying such a data structure requires allocating new dynamic memory and copying the data from the original into it. Destroying such a data structure requires freeing that dynamic memory. Both allocating and freeing dynamic memory are relatively slow operations. Moreover, copying the contents of the dynamic memory will also be slow if there is a lot to copy.

As a result of this implementation strategy, it is expensive to copy or destroy a string, vector, or similar data structure. Swapping two such data structures, on the other hand, is usually much simpler: It suffices to swap the contents of the objects themselves, and the dynamic memory can be left alone. As a result, swapping two such data structures is often much faster than copying or destroying them. If the contents are large, the speed difference can be a factor of 100 or more.

Now let's think about a vector of strings, which we'll name vs. Here is a code fragment to remove element number n from vs. We will assume that n is unsigned:

assert (n < vs.size());

for (size_t i = n+1; i != vs.size(); ++i)
           vs[i-1] = vs[i];
vs.resize(vs.size()–1);

The assert does not need to check that n >= 0 because n is unsigned; so of course it is always >=0.

The for loop copies vs[n+1] into vs[n], then copies vs[n+2] into vs[n+1], and so on. After it has finished, we no longer need the last element of vs, so we shrink vs by one, discarding the last element.

This code is capable of wasting a great deal of time. Copying vs[n+1] into vs[n] creates a copy of vs[n+1], after which the original vs[n+1] is overwritten by a copy of vs[n+2] , and so on. So all but one of the elements following vs[n] will be copied and the copies then overwritten.

Now consider this rewrite:

 
assert (n < vs.size());

for (size_t i = n+1; i != vs.size(); ++i)
           vs[i].swap(vs[i-1]);   // changed
vs.resize(vs.size()–1);

In this version, instead of copying each element after vs[n] into its predecessor, we swap the elements. When the loop completes, the original value of vs[n] will have been swapped all the way into the last element of vs, so it is this original value that the call to vs.resize will destroy. Moreover, the loop will accomplish this feat without ever making a copy of any element of vs.

This example suggests a general principle:

For types that are faster to swap than to copy, 
a sequence of assignments of the form
a = b; b = c; … will be faster if rewritten as
swap(a, b); swap(b, c); and so on.

If it is necessary to preserve the last value in the sequence, the last assignment can be left alone. So, for example,

 
             a = b; b = c; c = d; d = e;
 

can become

 
             swap(a, b); swap(b, c); swap(c, d); d = e;

and only the value of e is copied.

Of course, this swapping strategy is similar to the strategy for using the move operation that is part of C++11. Next week we will look at the curious relationship between swapping and moving.