Automatic Algorithm Selection Using Templates

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.