31
I just implemented the quick sort algorithm by using C++11 variadic templates to evaluate it at compilation time. However, I encounter a performance issue when the data set is too large.
#include <iostream>
using namespace std;
template<int... vs>
struct Seq
{};
template<int v1, int...vs>
struct Seq<v1, vs...>{
};
template<typename newT, typename srcT>
struct PushFront{
};
template<int vadded, int...vs>
struct PushFront<Seq<vadded>, Seq<vs...>>{
typedef Seq<vadded, vs...> ResultType;
};
template<typename T>
struct PopFront{
};
template<int v1, int...vs>
struct PopFront<Seq<v1, vs...>>{
typedef Seq<vs...> RemaindType;
typedef Seq<v1> ResultType;
};
template<typename T1, typename T2>
struct CatSeq{};
template<int...v, int...us>
struct CatSeq<Seq<v...>, Seq<us...>>{
typedef Seq< v..., us... > ResultType;
};
template<bool c, typename NewT, typename TrueClsT, typename FalseClsT>
struct Classify{
};
template<typename NewT, typename TrueClsT, typename FalseClsT>
struct Classify<true, NewT, TrueClsT, FalseClsT>{
typedef typename PushFront<NewT, TrueClsT>::ResultType NewTrueClsT;
typedef FalseClsT NewFalseClsT;
};
template<typename NewT, typename TrueClsT, typename FalseClsT>
struct Classify<false, NewT, TrueClsT, FalseClsT>{
typedef TrueClsT NewTrueClsT;
typedef typename PushFront<NewT, FalseClsT>::ResultType NewFalseClsT;
};
template<typename T1, typename T2>
struct Compare{};
template<int v1, int v2>
struct Compare<Seq<v1>, Seq<v2>>{
static const bool result=(v1>=v2);
};
template<typename AnchorT, typename SeqT, typename GESet, typename LSet>
struct PartitionImpl{};
template<typename GESet, typename LSet, int anchorv, int v1>
struct PartitionImpl<Seq<anchorv>, Seq<v1>, GESet, LSet>{