Compile time quick sort using C++ variadic templates

Edit June 4th 2015: This article is very dated. Read this revisiting article for a far better solution

C++ is a strange language. In many ways it's a crap language, but it's a very fun crap language to use. It's also a very powerful one, especially the templates. Now that ISO C++ 2011 has brought variadic templates, it becomes easier to use and requires less typing.

I decided to explore variadic templattes, and I thought one way of exploring it was to express a compile-time quick-sort. Note that I didn't set out to explore if it can be done - that I was certain of. I set out to explore if I can do it, and I very specifically decided not to check what others had done as I had no illusions of being the first.

The first problem to solve was that of expressing a list of numbers.

template <typename T, T... elems>struct list;

That's all that is required. The second template parameter is a list of zero or more elements of type T. That's what "..." denotes.

Its use is simple:

typedef list<int, 3, 8, 69, 2> integers;typedef list<char, 'c', 'h', 'a', 'r', 's', '\n'> word;

That the template is only declared, not defined, is not a mistake. It's not a problem that the types are incomplete and can't be instantiated. Instantiated objects are a run time thing, and this is about compile time computation.

It is, however, a good idea to be able to show what a list of numbers looks like, so a function to print the list is handy. More handy is a mechanism to call a function for every value in the list, in order.

Specializing function templates is still a no-go, but the classic forwarding to a helper class works.

template <typename T>struct foreach_t;

This just introduces the helper class template. All work is done in the specializations.

template <typename T, T head, T... tail>struct foreach_t<list<T, head, tail...> >{  template <typename F>  static void apply(F f)  {    f(head);    foreach_t<list<T, tail...> >::apply(f);  }}; template <typename T>struct foreach_t<list<T> >{  template <typename F>  static void apply(F)  {  }};

The first specialization calls the function provided in the apply member function to the first element of the list, and then recurses to do the same with the tail of the list. The second specialization ends the recursion by handling an empty list.

Ah the memories. This time of the year, in 1989, I was in university and took my first academic programming course - " Functional Programming with Standard ML." I thought I had a good idea about programming, but boy was I wrong. Who would've known that I'd find that course useful for C++ 22 years later? The programming technique is the same. The syntax is far worse in C++, though.

As a convenience, a function template is added:

template <typename T, typename F>void foreach(F f = F()){  foreach_t<T>::apply(f);}

The thing with the default parameter is just so that the function can either be called with an object, or using a type that is instantiated. It's just convenient. A small test program shows why.

#include <iostream>#include <ostream>#include <cstdio> struct print{  template <typename T>  void operator()(T t)  {    std::cout << t << ' ';  }}; int main(){  typedef list<int, 3, 8, 69, 2> integers;  typedef list<char, 'c', 'h', 'a', 'r', 's', '\n'> word;  foreach<integers, print>();  std::cout << '\n';  foreach<word>(std::putchar);}

The output when run is:

3 8 69 2
chars

Not very exciting, I admit, but it shows that the list works and that traversing it works. In all test programs to follow, the print struct is presumed available.

In order to implement a quick sort on the lists, two things must be possible to do with them, partitioning and concatenating them.

First the concatenation, since it's the easier operation.

template <typename ...T>struct concat;

As before, the generic concat template just introduces the name for the specializations.

template <typename T, T... p1, T... p2, typename ...Tail>struct concat<list<T, p1...>, list<T, p2...>, Tail... >{  typedef list<T, p1..., p2...> first_two;  typedef typename concat<first_two, Tail...>::type type;}; template <typename T, T... elems>struct concat<list<T, elems...> >{  typedef list<T, elems...> type;};

Local typedef:s galore in template meta programming, otherwise the lines becomes way too long to see properly.

The recursion is the same pattern, but here it is all about creating new types.

Another simple program shows the use

int main(){  typedef list<int, 2, 4, 8> first;  typedef list<int, 3, 5, 7> second;  foreach<concat<first, second>::type, print>();  std::cout << '\n';}

The output is

2 4 8 3 5 7 

It seems to work. Good.

Partitioning a list is possible to do with one template, but the code becomes messy to read. This is about learning a technique, not about managing messy code, so I decided to go for filtering instead. Less efficient, but much easier to read and understand.

The filter template solution takes a predicate and a list. The predicate picks the elements to keep. Doing this first requires a simple helper, the if_else template. I was pretty certain that this one made it to the standard library, but perhaps I was wrong. At least I can't find it.

template <bool b, typename T, typename F>struct if_else{  typedef T type;}; template <typename T, typename F>struct if_else<false, T, F>{  typedef F type;};

It's not very complicated. The template accepts a boolean value and two types. The typedef is the first type when the boolean value is true, and the second type otherwise.

With this, the filter template is reasonably straight forward as it follows a by now familiar pattern.

template <template <typename U, U> class Pred,          typename Data>struct filter; template <template <typename U, U> class Pred,          typename T, T head, T... tail>struct filter<Pred, list<T, head, tail...> >{  typedef list<T, tail...> tlist;  typedef typename filter<Pred, tlist>::type ftail;  typedef list<T, head> h;  typedef typename if_else<Pred<T, head>::value,                           typename concat<h, ftail>::type,                           ftail>::type type;}; template <template <typename U, U> class Pred, typename T>struct filter<Pred, list<T> >{  typedef list<T> type;};

The predicate is a template that provides a boolean value given a type and an input value. The filter template recurses over the elements of the list, and uses if_else to select either only the tail, or the selected value concatenated with the tail.

A simple program demonstrates.

template <typename T, T t>struct is_odd{  static const bool value = t & T(1);}; int main(){  typedef list<int, 8, 9, 2, 1, 0, 23, 11, 23, 3, 512 > data;  foreach<filter<is_odd, data>::type, print>();  std::cout << '\n';}

The output is:

9 1 23 11 23 3 

It seems like the filtering works.

Quick sort is now only about picking a pivot element, and filtering the elements from the list that are smaller and those that aren't into separate lists, quick sort the lists and concatenate the results.

To be generic, though, the sort order should be defined by a comparison template. A reasonable comparison template is

template <typename T, T l, T r>struct lt{  static const bool value = l < r;};

Using a selected pivot value, this comparison template must be transformed into a predicate that the filter template can use. Inspired by the std::bind functions from the standard library, here is a bind template that provides the needed transformation.

template <template <typename U, U, U> class C,          typename T, T t>struct bind{  template <typename V, V v>  struct pred  {    static const bool value = C<T, v, t>::value;  };};

The template parameter C is the comparison template, and the member template pred is the resulting predicate.

It can be used like this:

int main(){  typedef list<int, 8, 9, 2, 1, 0, 23, 11, 23, 3, 512 > data;  typedef filter<bind<lt, int, 10>::pred, data>::type lt10;  foreach<lt10, print>();  std::cout << '\n';}

The output is

8 9 2 1 0 3 

Presumably it works.

Now, for the quick sort, both the set selected by the predicate, and its complement, must be available. A simple way to get the complement is to negate the predicate. Enter another helper template.

template <template <typename U, U> class Pred>struct neg{  template <typename T, T v>  struct pred  {    static const bool value = !Pred<T, v>::value;  };};

The template parameter Pred is the predicate to negate, and the member template pred, is the negated predicate to use.

A simple variation of the previous example program is

int main(){  typedef list<int, 8, 9, 2, 1, 0, 23, 11, 23, 3, 512 > data;  typedef filter<neg<bind<lt, int, 10>::pred>::pred,                 data>::type ge10;  foreach<ge10, print>();  std::cout << '\n';}

Unsurprisingly the output is

23 11 23 512 

Now, finally, all the bits and pieces are there. It's just a matter of assembling them to a quick sort template

template <template <typename T, T, T> class Comp,          typename Data>struct q_sort; template <template <typename U, U, U> class Comp,          typename T, T head, T... tail>struct q_sort<Comp, list<T, head, tail...> >{  template <typename V, V v>  struct pred : bind<Comp, V, v>::template pred<T, head> {};  template <typename V, V v>  struct npred : neg<pred>::template pred<V, v> {};  typedef typename filter<npred, list<T, tail...> >::type fl;  typedef typename filter< pred, list<T, tail...> >::type tl;  typedef typename q_sort<Comp, fl>::type sfl;  typedef typename q_sort<Comp, tl>::type stl;  typedef list<T, head> hl;  typedef typename concat<sfl, hl, stl>::type type;}; template <template <typename U, U, U> class Pred,          typename T>struct q_sort<Pred, list<T> >{  typedef list<T> type;};

The middle template that does all the work is a bit overwhelming, but it's not as bad as it looks.

The head element is chosen as the pivot element.

First a predicate is made out of the Comp comparison template parameter, using the bind helper template introduced earlier and the pivot element.

Next a negated predicate npred is made with the help of the neg helper template.

Using these two predicates, two new lists are made, fl for false, i.e. when the negated predicate picked the elements, and tl for true, i.e. when the predicate picked the elements.

Then the two lists are sorted recursively, by creating two new types sfl and stl (for sorted versions of fl and tl.)

The only thing that remains is to concatenate the lists and the pivot element into a resulting type.

The use is simple:

int main(){  typedef list<int, 8, 9, 2, 1, 0, 23, 11, 23, 3, 512 > data;  foreach<q_sort<lt, data>::type, print>();  std::cout << '\n';}

The result (drumroll)

0 1 2 3 8 9 11 23 23 512 

Quick sort in compile time using C++ variadic templates. Now how useless is that?

Hope you enjoyed the show!