实现快速排序：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