C++ 模板元编程 | 插入排序

实现快速排序：https://howardlau.me/programming/cpp-templates-metaprogramming-quick-sort.html

辅助模板类

下面这些类利用了 C++ 的模板，实现了一些基本的逻辑功能：

#include <iostream>
// 布尔常量类型
struct TrueType {
    constexpr static bool value = true;
};

struct FalseType {
    constexpr static bool value = false;
};

// SFINAE 用来特定时机启用模板
template<bool, typename T = void>
struct EnableIfT { 
};

template<typename T>
struct EnableIfT<true, T> {
  using Type = T;
};

template<bool Cond, typename T = void>
using EnableIf = typename EnableIfT<Cond, T>::Type;

template <class T>
struct IdentityT {
    using Type = T;
};

template <class T>
using Identity = typename IdentityT<T>::Type;

// 模板的逻辑表达式功能
template <bool COND, typename TrueType, typename FalseType>
struct IfThenElseT {
    using Type = TrueType;
};

template <typename TrueType, typename FalseType>
struct IfThenElseT<false, TrueType, FalseType> {
    using Type = FalseType;
};

template <bool COND, typename TrueType, typename FalseType>
using IfThenElse = typename IfThenElseT<COND, TrueType, FalseType>::Type;

// 列表的值类型
template <class T, T Value>
struct CTValue {
    using Type = T;
    constexpr static T value = Value;
};

template <class T, T a, T b>
struct LessThanT<CTValue<T, a>, CTValue<T, b>> {
    constexpr static bool value = a < b;
};

template <class T, T a, T b>
struct GreaterThanT<CTValue<T, a>, CTValue<T, b>> {
    constexpr static bool value = a > b;
};

列表的操作

下面这些模板都是用于对于列表类的操作，顾名思义：

// 定义了列表的基本类型
template <class T, T... Values>
struct ValueList {};

template <class T, T... Values>
struct IsEmpty<ValueList<T, Values...>> {
    constexpr static bool value = sizeof...(Values) == 0;
};

template <class T, T Head, T... Tail>
struct FrontT<ValueList<T, Head, Tail...>> {
    using Type = CTValue<T, Head>;
    constexpr static T value = Head;
};

template <class ValueList>
using Front = typename FrontT<ValueList>::Type;

template <class T, T Head, T... Tail>
struct PopFrontT<ValueList<T, Head, Tail...>> {
    using Type = ValueList<T, Tail...>;
};

template <class ValueList>
using PopFront = typename PopFrontT<ValueList>::Type;

template <class T, T... Values, T NewValue>
struct PushFrontT<ValueList<T, Values...>, CTValue<T, NewValue>> {
    using Type = ValueList<T, NewValue, Values...>;
};

template <class ValueList, class NewValue>
using PushFront = typename PushFrontT<ValueList, NewValue>::Type;

编写插入排序

利用上面的操作，我们可将插入排序递归地写成这种形式：把表头元素取出，递归排序表尾，再将表头元素插入到排序好的表尾中；而将元素插入到排序完成的表中，则是递归进行如下操作：如果新的元素直接可以插入到表头，那就成为新的表头，新的表尾就是原来的表尾，否则新的表头就是原来的表头，而新的表尾就是将这个元素插入到表尾的适当位置。

两个递归的终止条件都是是：表为空。这时候认为空表就是排序好的表，对于 InsertionSort 来说，直接返回空表，对于 InsertSorted 来说，直接插入元素即可。

虽然代码看起来比较复杂，但是逻辑还是很清楚的。

template <class ValueList, class Element,
          template <class T, class U> class Compare,
          bool = IsEmpty<ValueList>::value>
struct InsertSortedT;

template <class ValueList, class Element,
          template <class T, class U> class Compare>
using InsertSorted = typename InsertSortedT<ValueList, Element, Compare>::Type;

template <class ValueList, class Element,
          template <class T, class U> class Compare>
struct InsertSortedT<ValueList, Element, Compare, false> {
    using NewTail = IfThenElse<
        Compare<Element, Front<ValueList>>::value, Identity<ValueList>,
        InsertSorted<PopFront<ValueList>, Element, Compare>>;
    using NewHead = IfThenElse<Compare<Element, Front<ValueList>>::value,
                               Element, Front<ValueList>>;

    using Type = PushFront<NewTail, NewHead>;
};

template <class ValueList, class Element,
          template <class T, class U> class Compare>
struct InsertSortedT<ValueList, Element, Compare, true> : PushFrontT<ValueList, Element> {
};

template <class ValueList, template <class T, class U> class Compare,
          bool = IsEmpty<ValueList>::value>
struct InsertionSortT;

template <class ValueList, template <class T, class U> class Compare>
struct InsertionSortT<ValueList, Compare, false>
    : InsertSortedT<InsertionSort<PopFront<ValueList>, Compare>,
                    Front<ValueList>, Compare> {};

template <class ValueList, template <class T, class U> class Compare>
struct InsertionSortT<ValueList, Compare, true> {
    using Type = ValueList;
};

template <typename List, typename Element,
          template <typename T, typename U> class Compare>
using InsertSorted = typename InsertSortedT<List, Element, Compare>::Type;

template <class ValueList, template <class T, class U> class Compare>
using InsertionSort = typename InsertionSortT<ValueList, Compare>::Type;

测试输出

编写用于测试的输出代码：

template <class T>
void OutputValueList(ValueList<T>) {
    std::cout << std::endl;
}

template <class T, T... Values>
void OutputValueList(ValueList<T, Values...>) {
    std::cout << Front<ValueList<T, Values...>>::value << ' ';
    OutputValueList(PopFront<ValueList<T, Values...>>());
};

最后编写主函数测试：

int main() {
    using TestList = ValueList<int, 17, 1, 15, 9, 8, 19, 16, 10, 11, 7, 4, 14,
                               18, 13, 3, 12, 2, 5, 6, 20>;
    using SortedList = InsertionSort<TestList, LessThanT>;
    using ReverseSortedList = InsertionSort<TestList, GreaterThanT>;
    std::cout << "Before sorted" << std::endl;
    OutputValueList(TestList());
    std::cout << "After sorted (from small to great)" << std::endl;
    OutputValueList(SortedList());
    std::cout << "After sorted (from great to small)" << std::endl;
    OutputValueList(ReverseSortedList());
    return 0;
}

最后程序的输出：

Before sorted
17 1 15 9 8 19 16 10 11 7 4 14 18 13 3 12 2 5 6 20 
After sorted (from small to great)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
After sorted (from great to small)
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

完整代码

完整的代码片段：https://gist.github.com/howardlau1999/cd90d591869a98ac72f92ad02b29d9c2