Fun with C++ template specialization

Today I had some fun with C++ template specialization.

The EQ2 codebase doesn't use std::vector anymore in an effort to reduce compile and link times. Instead, we have our own templated array type that is, for all intents and purposes, equivalent to std::vector but without some of the template overhead for allocators and such. Call it ArrayType< T >.

Now, ArrayType relies upon a static traits structure to do certain things for it, such as construct a range of T objects or copy T objects. Template specialization is used, especially for built-in types such as int or float, to perform the necessary operation in the most efficient way. For a built-in type, a copy could typically be implemented as a memcpy() or a memmove(). That wouldn't work very well for most custom classes.

STL libraries such as STLport use complicated type traits to answer questions like is_POD_type. Ours is much simpler and specialized to remove that template overhead.

In any case, back to my use of specialization. Consider what happens when you do something like this:

std::vector< std::vector< int > > vec;
vec.push_back( std::vector< int >( 1 ) );
vec.push_back( std::vector< int >( 2 ) );

vec.insert( vec.begin() + 1, std::vector< int >( 3 ) );

If you have vectors of vectors, each reallocate of the underlying data structure is going to cause the contained vectors to be copied. That's potentially a LOT of allocations. Likewise, the insert is going to move all of the elements including and after the insert position to make room for the new element. More allocations. Theoretically, there is a way to overcome this. Vectors (and most other STL containers) have a nifty little function called swap which swaps the contents of two same-type containers in O(1). To handle the insert, all you'd need to do is construct a default object (or copy-construct the new object) at the end and swap with previous starting at the end. The default object ends up right where you want your inserted element to go, so you can use the assignment operator to set it to the new element. No deep copies of all of the vectors, just nice-and-tidy memory management.

The rub is that there doesn't seem to be a tidy, generic way to do this with the STL. If you know how the traits work for STLport, you might be able to extend it to get what you want. That's far from a generic solution. This is where I get to brag about our ArrayType. All I had to do to make this work the way it should was define the swap semantics in a partially specialized ArrayType_traits:

template< typename U >
struct ArrayType_traits {
    ...
    static void rev_copy( VeArray<U>* dest, VeArray<U>* src, unsigned n )
        { dest += n, src += n;
          while ( n-- ) { (*--dest).swap( *--src ); } }
    ...
};

Neener, neener.