Recursive template metaprogramming (Part II)

2021 年 12 月 9 日

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

CC BY-NC-ND 2.0 授权

喜欢我的作品吗？别忘了给予支持与赞赏，让我知道在创作的路上有你陪伴，一起延续这份热忱！

eopXDHi 我是 eop 。畢業於台灣大學資訊工程系（NTU CSIE），現在是 Sifive 的 Compiler Engineer。（Ex-Skymizer Compiler Engineer）你可以在 eopxd.com 找到我！我會發布一些對技術的整理、閱讀或觀影的心得或是生活的感悟。如果覺得這些創作有價值，歡迎支持我。希望人生能一直過得有趣又有挑戰。

来自作者
相关推荐