Automatic Algorithm Selection Using Templates
<![CDATA[
Programmers are accustomed to writing different code for different kinds of
data but this is a problem for template writers because the author of a template
often has no idea what a template parameter type's options and restrictions
are. Thus, automated ways of selecting algorithms must be employed. Function
overloading and template specialization are the basic mechanisms that make
this possible.
Luckily, automatic selection benefits the users of the templates as well as
the writers -- users don't have to keep track of different interfaces based
on different types of data.
There are 3 main ways of letting the compiler do an algorithm selection:
1. pass a parameter to "helper" function that is unused except that
the helper function has multiple implementations -- each expecting
a different data type as the "unused" parameter. The compiler's
overload selection will do the work. This is the oldest approach
and still works but leads to a slight performance degradation.
For example:
void sort(iterator first, iterator last) // main driver of sorting
{
sort_helper(first, last, iterator_category(first));
}
In this case, the 2 parameter form of the sort routine is the driver
it assumes the existence of a family of 3 parameter sort_helper
functions. The 3rd parameter is always ignored but it helps the
compiler select which algorithm based on the return value of the
iterator_category() function.
In this case, the implementation of iteragor_category is trivial --
in most cases, it returns an object whose type implies that
the iterator is "not a random access iterator". But for true pointers
and for the iterators of vector<>, array, and deque<>, the
iterator_category() returns a value whose type means "this is a
random access iterator."
Interestingly, the easiest way to implement the iterator_category
for generic pointers, is like this:
random_access_iterator_tag iterator_category(void const *)
{
return random_access_iterator_tag();
}
The iterator_category() function could be overloaded in the
vector and deque class header files and also return
random_access_iterator_tag(). Something like this:
template<class T>
random_access_iterator_tag iterator_category(std::vector<T> cons t&)
{
return random_access_iterator_tag();
}
The generic definiton of the iterator_category() method is a template
that returns "forward_iterator_tag" for all data types. The compiler
will choose the void const * form if a real pointer is used, and
will select the specializations for vector and deque if they are used,
otherwise it will call the forward_iterator_tag version.
Thus you need two implementations of sort_helper: one that can
use the quicksort algorithm and its signature looks like this:
template<class Iterator>
void sort_helper(Iterator first, Iterator second, random_access_iterator_tag)
{
// implement quicksort here
}
The other, far slower, implementation of sort_helper would take a
forward_iterator_tag as its 3rd parameter and would use a merge
approach. See the standard sort algorithm in <algorithm> for specifics.
2. The second way to insure that the compiler selects the right
algorithm is to write the code to force a selection via the template
equivalent of a table lookup.
To do this, build a "traits table class" whose job it is to provide
members that implement the proper algorithm. The code that uses the
algorithm must explicity request the needed member of your templatized
implementer class.
For example, you might define a GENERIC algorithm in a
traits class like this:
template<class T>
struct AlgorithmImplementations
{
static void function(T) { ... }
};
Then you could specialize the algorithm for a given data type:
template<class T>
struct AlgorithmImplementations<T const *>
{
static void function(T const *) { ... }
};
In both of these cases, you call the algorithm like this:
int someFunction(SomeType t)
{
AlgorithmImplementations<SomeType>::function(t);
}
However, then you start running into annoyances with const-ness
of type SomeType. That is why the declarations in this
header file are helpful -- you change the above code slightly
and the const-ness problem goes away:
template<class SomeType>
int someFunction(SomeType t)
{
typedef typename removeCV<SomeType>::type implType;
implType::function(t);
}
Its the same basic idea, you just filter Sometype through the
removeCV template, below, to eliminate any possible const-ness
of the data type involved.
3. The third approach is more complex and sneakier but makes for
less text when you write the code. In this case, we take advantage
the fact that it is possible to make a lot of useful compile time
constants -- then use the constants to select between data types
using the fact that templates with integral parameters can
be specialized based on compile time a constant calculation.
For example, the size of a class is a compile time
constant -- as are simple arithmetic and comparisons of other
compile time constants. Combine this fact with the language's
ability to let you specialize templates with integral parameters, and
you have a mechanism by which the user can write compile time constant
expressions that select among either of two data types -- and with them
a potential host of other nested constants, types, and class methods.
For example, if you wanted to write one templatized
algorithm for small class objects and another for larger objects, you
do something like this:
template<bool> void functionHelper();
template<> void functionHelper<false> { /* small objects */ }
template<> void functionHelper<true> { /* large objects */ }
template<class T>
void function(T t)
{
return functionHelper<sizeof(T) > 100> (t); // call desired func
}
Using the same basic techinque, a compile-time type selection can
implemented. The goal is to provide an interface that lets you
do this:
template<class T>
void someFunction(T t)
{
typedef typename EvalTypeIf< someCompileTimeBoolCalculation,
falseChoiceType,
trueChoiceType
>::type helperType;
helperType::algorithm(t);
}
Here is the implementation of EvalTypeIf<>:
template<bool, class falseChoice, class trueChoice>
struct EvalTypeIf; // no implementation
template<class falseChoice, class falseChoice>
struct EvalTypeIf<false, falseChoice, trueChoice>
{
typedef falseChoice type;
}
template<class falseChoice, class falseChoice>
struct EvalTypeIf<true, falseChoice, trueChoice>
{
typedef trueChoice type;
}
This mechanism is actually somewhat superior to the other mechanisms
mentioned above because it lets you reduce interconnectivity between
header files. That is, you can build a traits table that doesn't provide
algorithms, but rather provides only information. Then, you can use that
information in other header files that define templatized algorithms.
This decoupling is very important to project development as it
it reduces the number of changes to your traits tables -- and reduces
their size -- you are not forced to combine all useful traits and
algorithms into a small number of heavily edited tables.
By combining these 3 approaches, many amazing compile time algorithm
selections can be made.
]]>