Recursive template metaprogramming (Part III)

On the previous part, I went through some practice on abstractions when writing recursions.

This part would be the last part of the current topic. I would implement MergeSort with recursive template metaprogramming.


Here I assume you are familiar with the algorithms of merge sort.

Splitting 1 list into 2

The first component of this utility shall be the merge sort interface taking a single list of integer and split them to half.

template<typename T>
struct MergeSort;
template<int ... Ints>
struct MergeSort <IntList<Ints ...>> {
  using splitList = Split<IntList<Ints ...>::length / 2, IntList<Ints ...>>;
  using type = typename MergeSortImpl<
    typename splitList::first, 
    typename splitList::second
  >::type;
};

We start by appending attribute length to IntList we mentioned in Part I.

template <int ... Ints>
struct IntList;
template<int head, int ... tail>
struct IntList <head, tail ...> {
  static constexpr int length = 
    IntList<tail ...>::length + 1;
};

The utility Split requires some implementation. With the specified length to split, it is actually like doing “get the front x of list” and “get the last n - x of list” with n as the length of the list.

////////////////////////////////////////////////////////////////
////// Split
template<int length, typename List>
struct Split;
template<int length, int ... Ints>
struct Split <length, IntList<Ints ...>> {
  using first = typename Head<length, IntList<Ints ...>>::type;
  using second = typename Tail<IntList<Ints ...>::length - length, IntList<Ints ...>>::type;
};

Implementing Head and Tail is like PopBack in the previous post, dealing with the list returned from recursion and the current state. It would be nice to do it as a practice.

Taking 2 lists as interface

We need to create another interface that takes the 2 lists split. The recursion goes here. We call MergeSort on both lists before merging them together.

// declaration
template<typename List1, typename List2>
struct MergeSortImpl;
template<int ... Ints1, int ... Ints2>
struct MergeSortImpl<IntList<Ints1 ...>, IntList<Ints2 ...>>;
// recursion
template<int head1, int head2, int ... Ints1, int ... Ints2>
struct MergeSortImpl<IntList<head1, Ints1 ...>, IntList<head2, Ints2 ...>> {
  using left = typename MergeSort<IntList<head1, Ints1 ...>>::type;
  using right = typename MergeSort<IntList<head2, Ints2 ...>>::type;
  using type = typename MergeSortMerge<left, right>::type;
};
// specialization
template<int ... Ints>
struct MergeSortImpl <IntList<>, IntList<Ints ...>> {
  using type = IntList<Ints ...>;
};
template<int ... Ints>
struct MergeSortImpl <IntList<Ints ...>, IntList<>> {
  using type = IntList<Ints ...>;
};
template<>
struct MergeSortImpl <IntList<>, IntList<>> {
  using type = IntList<>;
};

Merge

With 2 list sorted (recursively). We can know iteratively compare the front of list and merge them into a single one. Concat shall be useful here.

template<typename List1, typename List2>
struct MergeSortMerge;
template<int ... Ints1, int ... Ints2>
struct MergeSortMerge<IntList<Ints1 ...>, IntList<Ints2 ...>>;
template<int head1, int head2, int ... Ints1, int ... Ints2>
struct MergeSortMerge<IntList<head1, Ints1 ...>, IntList<head2, Ints2 ...>> {
  using type = typename std::conditional<
    (head1 <= head2),
    typename Concat<
      IntList<head1>,
      typename MergeSortMerge<
        IntList<Ints1 ...>, 
        IntList<head2, Ints2 ...>
      >::type
    >::type,
    typename Concat<
      IntList<head2>,
      typename MergeSortMerge<
        IntList<head1, Ints1 ...>, 
        IntList<Ints2 ...>
      >::type
    >::type
  >::type;
};
template<int ... Ints>
struct MergeSortMerge <IntList<>, IntList<Ints ...>> {
  using type = IntList<Ints ...>;
};
template<int ... Ints>
struct MergeSortMerge <IntList<Ints ...>, IntList<>> {
  using type = IntList<Ints ...>;
};
template<>
struct MergeSortMerge <IntList<>, IntList<>> {
  using type = IntList<>;
};

By combining the above 3 components, you can achieve compile time merge sort! Template metaprogramming is important technique in modern C++ programming. It is used to generalize utilities and writing libraries. Hope I can continue to improve and one day produce code that goes into the standard library 😉

Author: eopXD

Hi 我是 eop ,希望人生過得有趣有挑戰XD

Leave a Reply