title: Quick sort at compilation time using C++11 variadic templates
body: <p>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.</p>
  
  <pre><code>#include &lt;iostream&gt;
  
  using namespace std;
  
  template&lt;int... vs&gt;
  struct Seq
  {}; 
  template&lt;int v1, int...vs&gt;
  struct Seq&lt;v1, vs...&gt;{
  };
  
  
  template&lt;typename newT, typename srcT&gt;
  struct PushFront{
  };
  template&lt;int vadded, int...vs&gt;
  struct PushFront&lt;Seq&lt;vadded&gt;, Seq&lt;vs...&gt;&gt;{
    typedef Seq&lt;vadded, vs...&gt; ResultType;
  };
  
  template&lt;typename T&gt;
  struct PopFront{
  };
  template&lt;int v1, int...vs&gt;
  struct PopFront&lt;Seq&lt;v1, vs...&gt;&gt;{
    typedef Seq&lt;vs...&gt; RemaindType;
    typedef Seq&lt;v1&gt;    ResultType;
  };
  
  template&lt;typename T1, typename T2&gt;
  struct CatSeq{};
  template&lt;int...v, int...us&gt;
  struct CatSeq&lt;Seq&lt;v...&gt;, Seq&lt;us...&gt;&gt;{
    typedef Seq&lt; v..., us... &gt;  ResultType;
  };
  
  
  template&lt;bool c, typename NewT, typename TrueClsT, typename FalseClsT&gt;
  struct Classify{
  };
  template&lt;typename NewT, typename TrueClsT, typename FalseClsT&gt;
  struct Classify&lt;true, NewT, TrueClsT, FalseClsT&gt;{
    typedef typename PushFront&lt;NewT, TrueClsT&gt;::ResultType NewTrueClsT;
    typedef FalseClsT  NewFalseClsT;
  };
  template&lt;typename NewT, typename TrueClsT, typename FalseClsT&gt;
  struct Classify&lt;false, NewT, TrueClsT, FalseClsT&gt;{
    typedef TrueClsT  NewTrueClsT;
    typedef typename PushFront&lt;NewT, FalseClsT&gt;::ResultType NewFalseClsT;
  };
  
  template&lt;typename T1, typename T2&gt;
  struct Compare{};
  template&lt;int v1, int v2&gt;
  struct Compare&lt;Seq&lt;v1&gt;, Seq&lt;v2&gt;&gt;{
    static const bool result=(v1&gt;=v2); 
  };
  
  
  template&lt;typename AnchorT, typename SeqT, typename GESet, typename LSet&gt;
  struct PartitionImpl{};
  template&lt;typename GESet, typename LSet, int anchorv, int v1&gt;
  struct PartitionImpl&lt;Seq&lt;anchorv&gt;, Seq&lt;v1&gt;, GESet, LSet&gt;{
    static const bool isge=Compare&lt;typename PopFront&lt;Seq&lt;v1&gt;&gt;::ResultType, Seq&lt;anchorv&gt;&gt;::result;
    typedef typename Classify&lt;isge, Seq&lt;v1&gt;, GESet, LSet&gt;::NewTrueClsT  RstGESet;
    typedef typename Classify&lt;isge, Seq&lt;v1&gt;, GESet, LSet&gt;::NewFalseClsT  RstLSet;  
  };
  template&lt;typename GESet, typename LSet, int anchorv, int v1, int...vs&gt;
  struct PartitionImpl&lt;Seq&lt;anchorv&gt;, Seq&lt;v1, vs...&gt;, GESet, LSet&gt;{
    static const bool isge=Compare&lt;typename PopFront&lt;Seq&lt;v1, vs...&gt;&gt;::ResultType, Seq&lt;anchorv&gt;&gt;::result;
    typedef typename Classify&lt;isge, Seq&lt;v1&gt;, GESet, LSet&gt;::NewTrueClsT  TmpRstGESet;
    typedef typename Classify&lt;isge, Seq&lt;v1&gt;, GESet, LSet&gt;::NewFalseClsT  TmpRstLSet;
  
    typedef typename PartitionImpl&lt;Seq&lt;anchorv&gt;, Seq&lt;vs...&gt;, TmpRstGESet, TmpRstLSet&gt;::RstGESet RstGESet;
    typedef typename PartitionImpl&lt;Seq&lt;anchorv&gt;, Seq&lt;vs...&gt;, TmpRstGESet, TmpRstLSet&gt;::RstLSet  RstLSet;
  };
  
  
  template&lt;typename T&gt;
  struct Partition{
  };
  template&lt;int v1, int v2, int...vs&gt;
  struct Partition&lt;Seq&lt;v1, v2, vs...&gt;&gt;{
    typedef Seq&lt;v1&gt; AnchorType;
    typedef Seq&lt;&gt; GESet;
    typedef Seq&lt;&gt; LSet;
    typedef typename PartitionImpl&lt;AnchorType, Seq&lt;v1, v2, vs...&gt;, GESet, LSet&gt;::RstGESet  RstGESet;
    typedef typename PartitionImpl&lt;AnchorType, Seq&lt;v1, v2, vs...&gt;, GESet, LSet&gt;::RstLSet   RstLSet;
  };
  
  //why introduce this? refer to Sort
  template&lt;typename SrcT, typename GESet, typename LSet, template&lt;typename &gt; class SortOp&gt;
  struct SortSub{  
    typedef typename SortOp&lt;GESet&gt;::ResultType  TmpGESet2;
    typedef typename SortOp&lt;LSet&gt;::ResultType   TmpLSet2;
  };
  template&lt;typename SrcT, typename LSet, template&lt;typename&gt; class SortOp&gt;
  struct SortSub&lt;SrcT, SrcT, LSet, SortOp&gt;{
    typedef SrcT  TmpGESet2;
    typedef typename SortOp&lt;LSet&gt;::ResultType   TmpLSet2;
  };
  template&lt;typename SrcT, typename GESet, template&lt;typename&gt; class SortOp&gt;
  struct SortSub&lt;SrcT, GESet, SrcT, SortOp&gt;{
    typedef typename SortOp&lt;GESet&gt;::ResultType  TmpGESet2;
    typedef SrcT   TmpLSet2;
  };
  
  template&lt;typename T&gt;
  struct Sort;
  template&lt;&gt;
  struct Sort&lt;Seq&lt;&gt;&gt;{
    typedef Seq&lt;&gt; ResultType;
  };
  template&lt;int v&gt;
  struct Sort&lt; Seq&lt;v&gt; &gt;{
    typedef Seq&lt;v&gt; ResultType;
  };
  template&lt;int v1, int...vs&gt;
  struct Sort&lt; Seq&lt;v1, vs...&gt; &gt;{
    typedef Seq&lt;v1, vs...&gt; SrcType;
    typedef typename Partition&lt; Seq&lt;v1, vs...&gt; &gt;::RstGESet TmpGESet;
    typedef typename Partition&lt; Seq&lt;v1, vs...&gt; &gt;::RstLSet TmpLSet;
  
    //to by pass the case SrcType &lt;==&gt; TmpGESet or  SrcType &lt;==&gt; TmpLSet
    typedef typename SortSub&lt;SrcType, TmpGESet, TmpLSet, Sort&gt;::TmpGESet2  TmpGESet2;
    typedef typename SortSub&lt;SrcType, TmpGESet, TmpLSet, Sort&gt;::TmpLSet2   TmpLSet2;
  
    typedef typename CatSeq&lt;TmpGESet2, TmpLSet2&gt;::ResultType ResultType;
  };
  
  
  void dumpSeqTypeImpl(Seq&lt;&gt; ){
  }
  template&lt;int v1&gt;
  void dumpSeqTypeImpl(Seq&lt;v1&gt; ){
    cout&lt;&lt;v1&lt;&lt;" ";
  }
  template&lt;int v1, int...vs&gt;
  void dumpSeqTypeImpl(Seq&lt;v1, vs...&gt; ){
    cout&lt;&lt;v1&lt;&lt;" ";
    dumpSeqTypeImpl( Seq&lt;vs...&gt;() );
  }
  template&lt;int...vs&gt;
  void dumpSeqType(Seq&lt;vs...&gt; ){
    cout&lt;&lt;"Seq type &lt; ";
    dumpSeqTypeImpl( Seq&lt;vs...&gt;() );
    cout&lt;&lt;" &gt;"&lt;&lt;endl;
  }
  
      //test data
  #include "qsort_input.txt"
  
  int main(){
    //Seq&lt;&gt;  s0;// aggregate ‘Seq&lt;&gt; s0’ has incomplete type and cannot be defined
    Seq&lt;1&gt; s1;
    Seq&lt;1, 2&gt; s2;
  
    typedef Seq&lt;5, 5, 5&gt; TestType_SAME;
    TestType_SAME same;
    dumpSeqType( same );
    typename Partition&lt; TestType_SAME &gt;::RstGESet _ts1;
    typename Partition&lt; TestType_SAME &gt;::RstLSet _ts2;
    dumpSeqType( _ts1 );
    dumpSeqType( _ts2 );
  
  #if 1
    typedef Seq&lt;4, 7, 3, 9, 1, 2, 5, 5, 19, 5&gt; TestType;
    TestType s3;
    dumpSeqType( s3 );
    typename Partition&lt; TestType &gt;::RstGESet ts1;
    typename Partition&lt; TestType &gt;::RstLSet ts2;
    dumpSeqType( ts1 );
    dumpSeqType( ts2 );
  
    typename Sort&lt;TestType&gt;::ResultType so1;
    dumpSeqType( so1 );
  #endif 
  
  #if 1
    typedef Seq&lt;TEST_DATA_100&gt; TAdvanceType;
    typename Sort&lt;TAdvanceType&gt;::ResultType soadvance;
    dumpSeqType(soadvance);
  #endif
  
    return 0;
  }
  </code></pre>
  
  <p>When the data set is TEST_DATA_100, it takes 1.7s to compile.<br>
  When the data set is TEST_DATA_1000, the compiler seems to halt....</p>
  
  <p>I'm using gcc 4.6.0.</p>