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 😉
Original link: eopXD