Probably the second most used container in the C++ standard library is std::vector (with std::string being the most used). Like most standard library containers std::vector has a small memory footprint (e.g. 3 pointers in STLport) with the bulk of its storage being on the heap (on behalf of its contained objects). This leads to the observation that it may be significantly faster to swap elements rather than assign or copy construct them. So a new std::vector like class template called swap_vector is proposed.

Copy construction

For primitive C/C++ types, copy construction (and assignment) is faster than swapping. Furthermore there is no primitive C function to swap integers (or pointers) so the "copy via a temporary variable" method is usually employed. All the standard C++ containers support a swap(T &) method which turns out to be useful for meeting exception safety guarantees [Sutter00]. As standard containers are nested within one another, for example vector<vector<string> >, the cost of copy construction in the outer container increases markedly. Interestingly, the cost of swapping elements in the outer container stays the same. The swap() method in standard containers is guaranteed to be constant time complexity. Other design idioms such as "pimpl" [Sutter00] lead to objects that will have constant time complexity swap() methods. Significant performance improvements can be obtained when vector<vector<string> > (for example) is replaced by swap_vector<vector<string> >. Normally, when swap is used to replace copy construction, then a default object construction and a corresponding empty object destruction are required. So swapping techniques used by swap_vector become attractive when this relation is met (preferably by a comfortable margin).
    time[copy_ctor]  >  (time[swap] + time[default_ctor] + time[empty_dtor])


This class template has been implemented by just "borrowing" an existing implementation of std::vector and keeping its interface. Several new member functions have been added to allow elements to be passed to a swap_vector using a swap rather than value semantics (i.e. using a copy constructor), but strictly speaking these extra methods are not required. None of the existing member functions borrowed for std::vector change their semantics. When the new member functions are not being used, the only change is the way the vector elements are re-arranged when an insert method (e.g. push_back() ) finds the internal storage all used up. Using STLport's implementation of std::vector as a guide, a larger block (typically twice as big as before) of contiguous memory is allocated and then the elements of the previous block are copied across to the new, larger block. swap_vector still creates the new, larger contiguous block but then uses the default constructor to initialize the elements of the new block and swaps the original elements into the new block. This leaves the old block full of default constructed elements but the old block is destined to be deleted anyway.

If the contained class does not have a swap(T&) method then compilation while break. However there is no way to check at compile time that a class that supports swap(T&) has implemented it with the intended semantics. [Another problem is that swap semantics may be supported by a differently named member function (e.g. Swap(T &) ). An adapter class could take care of this.]

swap_vector's extra methods

    // swap second argument with element at pos
void swap_at(size_type pos, T &) throw(std::out_of_range);

    // swap argument with empty object that was pushed as part of this method
void swap_push_back(T &);

    // swap second argument with empty object inserted at before pos
typedef swap_vector<T>::iterator iterator;
iterator swap_insert(iterator pos, T &);

    // swap the elements in the range [from, to[ with empty objects
    // inserted before pos
void swap_insert(iterator pos, ForwardIterator from, ForwardIterator to);

    // first make the swap_vector (this) have the same number of elements
    // as [from, to[ (by adding empty objects at the end or erasing objects),
    // then swap each element in this with those in [from, to[.
void swap_assign(ForwardIterator from, ForwardIterator to);

The last member function has some interesting possibilities. It allows a large std::vector to be cheaply swapped into a swap_vector (and possibly swapped again into a std::deque or a std::list). Swapping into associative containers is more problematic :-)


Some standard algorithms could have "swap" variants. std::reverse, sort and stable_sort spring to mind. Would a swappable trait be useful?

Exception Safety

Intuitively the types for which swap_vector<T>  is efficient, will have a T::swap(T&) that moves pointers and integers rather than "heavy" objects. For the case where T is a standard container then T::swap(T&) gives the "no throw" guarantee. While swap_vector substitutes all copy constructors with swap() calls when the capacity() is exceeded, there are still copy constructors when arguments are passed into and out of the container. [These "interface" copy constructors can be avoided by using the extra methods outlined above, however standard algorithms will continue to use the vector-like interface when given iterators to a swap_vector.] Also swap_vector<T> uses T's default constructor a lot, but it is unlikely that this will be less exception safe than T's copy constructor.


An implementation is available which overlays on top of STLport's version 4.5.3 (current at the time of writing). The patch is non-invasive in the sense that it does not modify any existing STLport files, it just adds three new files. It has been tested on Linux (Mandrake 8.1 with a gcc 3.0 compiler), Solaris (5.0 with a Forte 5.3 C++ compiler), HP aCC (3.30) and Visual Studio 7. A Makefile is included for Linux and Solaris. It is best to unzip the tarball (or zip archive) in the directory that contains the STLport-4.5.3 distribution. In the "my_test" directory there is  a test program which exercise swap_vector (and allows std::vector to be dropped back in for timing comparisons).

The my_test program illustrates that swap_vector can be slower (around 15%) for repeated push_back()s on a vector of small strings. However, as a contrived example, repeated insertion at the beginning of a vector<vector<string> > can be over a magnitude faster if the outer vector is changed to a swap_vector.

Note:  _STLP_DEBUG is not supported {need to add proper implementations of stlport/stl/debug/_swap_vector.[hc] for that}. I am not STLport library expert and this implementation could no doubt be improved by Boris Fomitchev and his colleagues.


Here is a gzipped tarball: swap_vec08.tgz and this is a zip archive: swap_vec07.zip . They have the similar contents.

[Sutter00] "Exceptional C++" by Herb Sutter, 2000 ISBN: 0-201-61562-2

Last updated: 7th April 2002

Douglas Gilbert