1

As part of a personal project, i have developed a template metaprogramming library that has an implemetation of type lists using C++11 variadic templates.

To test typelists operations, such as merge two typelists, split a typelist in two typelists, push_back a type in a typelist, etc (And to do a very freak programming excercise); i have implemented a compile-time version of the quicksort sorting algorithm using template metaprogramming:

NOTE: "dl32" is the prefix of my library types.

#include "dl32MetaprogrammingLibrary.h" #include <iostream> using namespace std; /* quicksort sorts lists of unsigned ints */ template<unsigned int... Ns> using uint_list = dl32TypeList<dl32UintWrapper<Ns>...>; using empty_uint_list = dl32EmptyTypeList; /* set of unsigned int comparers */ template<typename UINT1, typename UINT2> struct equal : public dl32BoolWrapper< UINT1::value == UINT2::value > {}; template<typename UINT1, typename UINT2> struct not_equal : public dl32BoolWrapper< UINT1::value != UINT2::value > {}; template<typename UINT1, typename UINT2> struct bigger_than : public dl32BoolWrapper< (UINT1::value > UINT2::value) > {}; template<typename UINT1, typename UINT2> struct less_than : public dl32BoolWrapper< (UINT1::value < UINT2::value) > {}; template<typename UINT1, typename UINT2> struct bigger_or_equal : public dl32BoolWrapper< UINT1::value >= UINT2::value > {}; template<typename UINT1, typename UINT2> struct less_or_equal : public dl32BoolWrapper< UINT1::value <= UINT2::value > {}; /* Compile-time quicksort implementation */ template<typename UINT_LIST> class quicksort { private: //Forward declaration: template<unsigned int lenght , typename SUBLIST> struct _quicksort; //Base-case for empty sublists: template<typename... Ns> struct _quicksort<0,dl32TypeList<Ns...>> { using result = empty_uint_list; }; //Base case for one element sublists: template<typename UINT_WRAPPER> struct _quicksort<1,dl32TypeList<UINT_WRAPPER>> { using result = dl32TypeList<UINT_WRAPPER>; }; //Base-case for two elements sublists (Simple compare and swap): template<typename FIRST , typename LAST > struct _quicksort<2,dl32TypeList<FIRST,LAST>> { using result = typename dl32tmp_if< bigger_or_equal<FIRST,LAST>::value , //CONDITION dl32TypeList<FIRST,LAST>, //THEN dl32TypeList<LAST,FIRST> //ELSE >::type; }; //Recursive case: template<unsigned int lenght , typename... Ns> struct _quicksort<lenght,dl32TypeList<Ns...>> { private: /* STEP 1: Reorder the sublist in two sublists: Left sublist, with elements greater than pivot, and right, with the others */ //Forward declaration: template<typename PIVOT , typename RIGHT /* initial (or actual) right sublist */ , typename LEFT /* initial (or actual) left sublist */ , typename _UINT_LIST /* original sublist */> struct _reorder_sublists; //Recursive case: template<typename PIVOT , typename... RIGHT_UINTS , typename... LEFT_UINTS , typename HEAD , typename... TAIL> struct _reorder_sublists<PIVOT,dl32TypeList<RIGHT_UINTS...>,dl32TypeList<LEFT_UINTS...>,dl32TypeList<HEAD,TAIL...>> { using _next_left = dl32TypeList<LEFT_UINTS...,HEAD>; ///< Next left sublist if HEAD is greather than PIVOT. using _next_right = dl32TypeList<HEAD,RIGHT_UINTS...>; ///< Next right sublist if HEAD is less than PIVOT. // CONDITION THEN ELSE using next_left = typename dl32tmp_if< !bigger_or_equal<PIVOT,HEAD>::value , _next_left , dl32TypeList<LEFT_UINTS...>>::type; using next_right = typename dl32tmp_if< bigger_or_equal<PIVOT,HEAD>::value , _next_right , dl32TypeList<RIGHT_UINTS...>>::type; using next_reorder = _reorder_sublists<PIVOT,next_right,next_left,dl32TypeList<TAIL...>>; // "Recursive call" (Iteration) using right = typename next_reorder::right; //Recursive result return using left = typename next_reorder::left; //Recursive result return }; //Base case (End of the iteration): template<typename PIVOT , typename RIGHT , typename LEFT> struct _reorder_sublists<PIVOT,RIGHT,LEFT,empty_uint_list> { using right = RIGHT; using left = LEFT; }; template<typename PIVOT> using _right_sublist = typename _reorder_sublists<PIVOT,empty_uint_list,empty_uint_list,dl32TypeList<Ns...>>::right; //Right sublist computation template<typename PIVOT> using _left_sublist = typename _reorder_sublists<PIVOT,empty_uint_list,empty_uint_list,dl32TypeList<Ns...>>::left; //Left sublist computation private: static const unsigned int _half_size = lenght/2; static const unsigned int _pivot_index = _half_size; //"Silly" pivot policy. Random-pivot instead? http://stackoverflow.com/questions/11498304/generate-random-numbers-in-c-at-compile-time using _pivot = typename dl32TypeAt<_pivot_index,dl32TypeList<Ns...>>::type; using _right = _right_sublist<_pivot>; //"Call" to reordered right sublist computation using _left = _left_sublist<_pivot>; //"Call" to reordered left sublist computation public: /* STEP 2: Recursive "call" to quicksort passing the two generated sublists */ using result = typename dl32Merge< typename _quicksort< _left::size , _left >::result , typename _quicksort< _right::size , _right >::result >::result; }; public: using result = typename _quicksort<UINT_LIST::size,UINT_LIST>::result; //"Call" to quicksort computation; }; /* input/output printing tools */ template<typename OUTPUT> struct print_output; template<> struct print_output<empty_uint_list>{ static void print() { cout << endl << endl; } }; template<typename HEAD , typename... TAIL> struct print_output<dl32TypeList<HEAD,TAIL...>> { static void print() { cout << HEAD::value << (sizeof...(TAIL) > 0 ? "," : ""); print_output<dl32TypeList<TAIL...>>::print(); } }; /* unsigned int lists generator */ template<unsigned int BEGIN , unsigned int END> class uint_list_generator { private: template<unsigned int _CURRENT,unsigned int _END> struct _generator { using result = typename dl32Merge<uint_list<_CURRENT>,typename _generator<(BEGIN <= END ? _CURRENT + 1 : _CURRENT - 1) , _END>::result>::result; }; template<unsigned int _END> struct _generator<_END,_END> { using result = uint_list<_END>; }; public: using result = typename _generator<BEGIN,END>::result; }; using input = typename uint_list_generator<0,499>::result; using output = typename quicksort<input>::result; int main() { print_output<input>::print(); print_output<output>::print(); return 0; }

The algorithm works perfectly (After the compiler has eaten 4GB of RAM, and waste two minutes to compile an execution of a 500 elements list...).

As you can see, i used a bigger-or-equal comparer in the quicksort implementation. My question is: There are any method to pass the comparer through a template parameter?

The problem is that the algorithm uses lists of unsigned int wrappers as data (See "uint_list" declaration at the beginning of the code), and comparers expect uint wrappers as parameters. So i cannot pass a "generic" comparer through the quicksort template.

Improve this question
2
  • That much code, really? Also, prefixes for types were trendy in C : there are namespaces in C++. Commented Jun 8, 2013 at 23:20
  • Yeah, its true. I'm thinking about erase the prefixes and put namespaces since a long time ago. But I hesitate. Commented Jun 9, 2013 at 11:26

1 Answer 1

Reset to default
0

What about a template template parameter:

template <typename UINT_LIST, template <typename UINT1, typename UINT2> class compare = less_than> class quicksort { ... using result = typename dl32tmp_if<compare<FIRST,LAST>::value, ... }; ... using output = typename quicksort<input, bigger_than>::result;

Besides, with such signature, you are not restricted to unsigned int-s at all.

Other than that, sometimes it may be useful to use a wrapper class hiding the template inside to mimic a template typedef.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

The problem with template template solution is that numbers are stored at compile-time as wrapper types ( template<unsigned int n> struct dl32UintWrapper{ static const unsigned int value = n; }; ). So you MUST pass the two values to the comparer. In your solution, you forget the two parameters of less_than. That parameters must be generic, so your solution has the same problem :)
Before asking the question, i had tried the wrap-around solution, but results in compilation errors. If you use a wrapper of the comparer (For example: struct bigger_than_wrapper { template<typename UINT1 , typename UINT2> using comparer = bigger_than<UINT1,UINT2>; }; ), the use of that comparer is as folows: ... dl32tmp_if< COMPARER::comparer<PIVOT,HEAD>::value , ... . This results in a "expected nested-name specifier" error in GCC, event if you put or not the typename keyword before the use of COMPARER::comparer.
I don't understand the first comment: I clearly see compare<FIRST,LAST>::value in the answer passing two parameters to the comparer.
At the quicksort template, last template parameter COMPARER has a default value of less_than. You must passtwo uint wrappers as parameters of less_than. And this makes less_than non-generic. I want a method to pass a generic comparer to the quicksort template.
Note that, for example, less_than<dl32UintWrapper<0>,dl32UintWrapper<1>> is not the same type as less_than<dl32UintWrapper<10>,dl32UintWrapper<11>> THIS is the problem. I can't pass a comparer "filled" (With parameters) as quicksort parameter, beacuse the comparer passed is not generic. Its only a comparer for the two numbers that was passed as template parameters to it.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.