hello;)
I'm
marek

Sorting for beginers — at compile time

08 May 2018 | C++ magic | back home

Every serious programmer knows how to write some of simple cumbersome O(n^2) sorting algorithms. Do you know how to use templates in C++? Great! Today I want to show you some advanced fun with C++ templating principles. Or is it a routine to sort types by their sizeof with merge sort by a compiler?

Why doing such nasty things?

This article is an interesting detail of my project called attr-MU which I have written some time ago. We start with some simple demonstration of C++ parameter pack. Then we move to simple Merge sort implementation. We left Bubble sort as an optional exercise for a reader.

Concat operation — example

C++ meta programming feels a little bit like logic programming in Prolog. It will helps you knowledge any non-procedural language. Let struct list<...> be a structure with variadic number of template parameters. We define Concat(list<a1, …, an>, list<b1, …, bm>) as list<a1, …, an, b1, …, bm>. With some basic knowledge of specialization we can express it in the language of templates really simply:


template<typename... Ts> struct concat {};
template<typename... Ts, typename... TTs>
struct concat<list<Ts...>, list<TTs...>> {
    using type = list<Ts..., TTs...>;
};

Shift operation — the first step

If we think about parameter pack as it would be a list, than how we can push new element front? This is often called shift. We can think about shift as a special case of Concat, therefore this is even simplier than previous example:


template<typename... Ts> struct shift {};
template<typename T, typename... TTs>
struct shift<T, list<TTs...>> {
    using type = typename cat<list<T>, list<TTs...>>::type;
};

Notice the necessary occurance of the typename keyword in the using declaration.

Functional evergreen — drop & take

Let make it more complicated. You should know about integral template parameters before (its the first int param in the following example). If so, we want to forget all type parameter until the indexing variable is equal zero:


template<int I, typename List> struct drop { using type = list<>; };
template<int I, typename T, typename... Ts>
struct drop<I, list<T, Ts...>> {
using type = typename std::conditional<
    (I > 0),
        typename drop<I-1, list<Ts...>>::type,
        list<T, Ts...>
    >::type;
};

As you can see, the main trick is in separation of the first type param from others. The way the code is indent suggests that there is a (terminating) condition. For this purpouses is used std::conditional from standard lib. Notice we can get value of the I-1 as a compile-time constant. Moreover, in the definition of Take operation we use previously written Shift:


template<int I, typename List> struct take { using type = list<>; };
template<int I, typename T, typename... Ts>
struct take<I, list<T, Ts...>> {
    using type = typename std::conditional<
        (I > 0),
            shift_t<T, typename take<I-1, list<Ts...>>::type>,
            list<>
    >::type;
};

Lets merge …

Now it comes to scene the order. In our example we will sort by the number of bytes of the object representation of type — sizeof. Follows code of a specialization. It looks like as a normal Merge sort now, does't it?


template<typename T, typename... Ts, typename TT, typename... TTs>
struct merge<list<T, Ts...>, list<TT, TTs...>> {
    using type = typename std::conditional<
        (sizeof(T) > sizeof(TT)),
            shift_t<T , typename merge<list<   Ts...>, list<TT, TTs...>>::type>,
            shift_t<TT, typename merge<list<T, Ts...>, list<TTs...>>::type>
    >::type;
};

… and sort! Horray!

We have defined all the necessary tools for sorting. If you think over for a while how to use it, you should be able to write it on your own —


template<typename L> struct merge_sort { using type = L; };
template<typename T> struct merge_sort<list<T>> { using type = list<T>; };
template<typename T, typename... Ts>
struct merge_sort<list<T, Ts...>> {
    using type = merge_t<
        typename merge_sort< take_t< ((sizeof...(Ts)+1) / 2), list<T,Ts...>> >::type,
        typename merge_sort< drop_t< ((sizeof...(Ts)+1) / 2), list<T,Ts...>> >::type
    >;
};

In this preview we used another specialization to terminate first-order recursion; list of one element is sorted by default. You may find out, that we use e.g. take_t instead of typename take<...>::type. This usage is taken from standard libraly and it is created with using take_t = typename take<...>::type;.

The complete compile time Merge sort together with Bubble sort is implemented in base.hpp, a main header of the attr-MU project. Feel free to discuss with you anything and thanks for your attention! Stay turned!


„Vždy odpouštějme svým nepřátelům, nic je nedokáže víc rozzuřit.“ Oscar Wilde