Recursive template metaprogramming (Part II)
Previously I wrote about basic utility and simple examples of recursive template programming. On this part I will show how to write Find, Remove, PopFront, PopBack.
Find
Since we are dealing with search of value, we can’t use std::conditional. The main trick of this utility is to determine whether the current state consists of the value to find. The rest is just simple recursion.
//////////////////////////////////////////////////////////
////// Find
// declaration
template<int toFind, typename T>
struct Find;
template<int value, int index, int ... Ints>
struct FindImpl;
// recursion
template<int toFind, int index, int head, int ... tail>
struct FindImpl<toFind, index, head, tail ...> {
static constexpr bool fromLater =
FindImpl<toFind, index + 1, tail ...>::isFound;
static constexpr bool fromCurrent = toFind == head;
static constexpr bool isFound = fromLater | fromCurrent;
static constexpr int value = fromCurrent == true ?
index :
FindImpl<toFind, index+1, tail ...>::value;
};
// specialization
template<int toFind, int index, int single>
struct FindImpl<toFind, index, single> {
static constexpr bool fromLater = false;
static constexpr bool fromCurrent = toFind == single;
static constexpr bool isFound = fromLater | fromCurrent;
static constexpr int value = fromCurrent == true ?
index : index + 1;
};
template<int toFind, int ... Ints>
struct Find<toFind, IntList<Ints ...>> {
static constexpr int value =
FindImpl<toFind, 0, Ints ...>::value;
};
Remove
The tricky part that took me some moments is the derivations between RemoveInt and RemoveIntImpl. The first one returns a list of integer and the second one takes a look on the values inside the list.
While looking inside the list, when we decide to add some value to the resulting list, a PushFront utility would be needed. It can be simply implemented and you can make the following snippet workable by adding a PushFront utility.
I think one of the main take-away from this practice is the way of “abstraction” between utilities. In Remove, by implementing PushFront we can rely on the utility and work on the level of lists.
//////////////////////////////////////////////////////////
////// Remove
// declaration
template<int toRemove, typename T>
struct RemoveInt;
template<int toRemove, int ... Ints>
struct RemoveIntImpl;
// recursion
template<int toRemove, int head, int ... tail>
struct RemoveIntImpl <toRemove, head, tail ...> {
using proceedingRemovedList =
typename RemoveInt<toRemove, IntList<tail ...>>::type;
using type = typename std::conditional<
(toRemove == head),
proceedingRemovedList,
typename PushFront<head, proceedingRemovedList>::type
>::type;
};
// specialization
template<int toRemove, int single>
struct RemoveIntImpl <toRemove, single> {
using type = typename std::conditional<
(toRemove == single),
IntList<>,
IntList<single>
>::type;
};
template<int toRemove, int ... Ints>
struct RemoveInt<toRemove, IntList<Ints ...>> {
using type = typename RemoveIntImpl<toRemove, Ints ...>::type;
};
PopBack
PopFront is easy, so I only show PopBack here. The trick is to concatenate returned list from recursions with the current one. So simply implementing utility Concat would make the following code workable.
//////////////////////////////////////////////////////////
////// PopBack
template<typename T>
struct PopBack;
template<int ... Ints>
struct PopBackImpl;
template<int front, int ... tail>
struct PopBackImpl<front, tail ...> {
using type = typename Concat<IntList<front>, typename PopBackImpl<tail ...>::type>::type;
};
template<int single>
struct PopBackImpl<single> {
using type = IntList<>;
};
template<>
struct PopBackImpl<> {
using type = IntList<>;
};
template<int ... Ints>
struct PopBack<IntList<Ints ...>> {
using type = typename PopBackImpl<Ints ...>::type;
};
After this post I hope you had a nice trip on abstractions. The next part I would implement MergeSort with recursive template metaprogramming.
More reading: Abstraction – the key to Computing?
Original link: eopXD