컴파일 타임 퀵 정렬 : 템플릿 매개 변수로 비교 자 전달

Question

개인 프로젝트의 일부로 C++ 11 가변 템플릿을 사용하여 형식 목록을 구현 한 템플릿 메타 프로그래밍 라이브러리를 개발했습니다.

두 입력 목록을 병합하거나 두 입력 목록에서 입력 목록을 분리하거나 입력 목록에서 push_back을 입력하는 등 입력 목록 작업을 테스트하려면 (매우 괴상한 프로그래밍 연습을하기 위해); 템플릿 메타 프로그래밍을 사용하여 퀵 정렬 알고리즘의 컴파일 타임 버전을 구현했습니다.

참고 : "dl32"는 내 라이브러리 유형의 접두사입니다.

#include "dl32MetaprogrammingLibrary.h" 

#include <iostream> 
using namespace std; 

/* quicksort sorts lists of unsigned ints */ 
template<unsigned int... Ns> 
using uint_list = dl32TypeList<dl32UintWrapper<Ns>...>; 
using empty_uint_list = dl32EmptyTypeList; 

/* set of unsigned int comparers */ 
template<typename UINT1, typename UINT2> 
struct equal   : public dl32BoolWrapper< UINT1::value == UINT2::value > {}; 
template<typename UINT1, typename UINT2> 
struct not_equal  : public dl32BoolWrapper< UINT1::value != UINT2::value > {}; 
template<typename UINT1, typename UINT2> 
struct bigger_than  : public dl32BoolWrapper< (UINT1::value > UINT2::value) > {}; 
template<typename UINT1, typename UINT2> 
struct less_than  : public dl32BoolWrapper< (UINT1::value < UINT2::value) > {}; 
template<typename UINT1, typename UINT2> 
struct bigger_or_equal : public dl32BoolWrapper<UINT1::value>= UINT2::value > {}; 
template<typename UINT1, typename UINT2> 
struct less_or_equal : public dl32BoolWrapper< UINT1::value <= UINT2::value > {}; 


/* Compile-time quicksort implementation */ 
template<typename UINT_LIST> 
class quicksort 
{ 
private: 
    //Forward declaration: 
    template<unsigned int lenght , typename SUBLIST> 
    struct _quicksort; 

    //Base-case for empty sublists: 
    template<typename... Ns> 
    struct _quicksort<0,dl32TypeList<Ns...>> 
    { 
     using result = empty_uint_list; 
    }; 

    //Base case for one element sublists: 
    template<typename UINT_WRAPPER> 
    struct _quicksort<1,dl32TypeList<UINT_WRAPPER>> 
    { 
     using result = dl32TypeList<UINT_WRAPPER>; 
    }; 

    //Base-case for two elements sublists (Simple compare and swap): 
    template<typename FIRST , typename LAST > 
    struct _quicksort<2,dl32TypeList<FIRST,LAST>> 
    { 
     using result = typename dl32tmp_if< bigger_or_equal<FIRST,LAST>::value , //CONDITION 
              dl32TypeList<FIRST,LAST>,   //THEN 
              dl32TypeList<LAST,FIRST>    //ELSE 
              >::type; 
    }; 

    //Recursive case: 
    template<unsigned int lenght , typename... Ns> 
    struct _quicksort<lenght,dl32TypeList<Ns...>> 
    { 
    private: 
     /* STEP 1: Reorder the sublist in two sublists: Left sublist, with elements greater than pivot, and right, with the others */ 

     //Forward declaration: 
     template<typename PIVOT , typename RIGHT /* initial (or actual) right sublist */ , typename LEFT /* initial (or actual) left sublist */ , typename _UINT_LIST /* original sublist */> 
     struct _reorder_sublists; 

     //Recursive case: 
     template<typename PIVOT , typename... RIGHT_UINTS , typename... LEFT_UINTS , typename HEAD , typename... TAIL> 
     struct _reorder_sublists<PIVOT,dl32TypeList<RIGHT_UINTS...>,dl32TypeList<LEFT_UINTS...>,dl32TypeList<HEAD,TAIL...>> 
     { 
      using _next_left = dl32TypeList<LEFT_UINTS...,HEAD>; ///< Next left sublist if HEAD is greather than PIVOT. 
      using _next_right = dl32TypeList<HEAD,RIGHT_UINTS...>; ///< Next right sublist if HEAD is less than PIVOT. 
      //             CONDITION     THEN     ELSE 
      using next_left = typename dl32tmp_if< !bigger_or_equal<PIVOT,HEAD>::value , _next_left , dl32TypeList<LEFT_UINTS...>>::type; 
      using next_right = typename dl32tmp_if< bigger_or_equal<PIVOT,HEAD>::value , _next_right , dl32TypeList<RIGHT_UINTS...>>::type; 

      using next_reorder = _reorder_sublists<PIVOT,next_right,next_left,dl32TypeList<TAIL...>>; // "Recursive call" (Iteration) 

      using right = typename next_reorder::right; //Recursive result return 
      using left = typename next_reorder::left; //Recursive result return 
     }; 

     //Base case (End of the iteration): 
     template<typename PIVOT , typename RIGHT , typename LEFT> 
     struct _reorder_sublists<PIVOT,RIGHT,LEFT,empty_uint_list> 
     { 
      using right = RIGHT; 
      using left = LEFT; 
     }; 

     template<typename PIVOT> 
     using _right_sublist = typename _reorder_sublists<PIVOT,empty_uint_list,empty_uint_list,dl32TypeList<Ns...>>::right; //Right sublist computation 
     template<typename PIVOT> 
     using _left_sublist = typename _reorder_sublists<PIVOT,empty_uint_list,empty_uint_list,dl32TypeList<Ns...>>::left; //Left sublist computation 

    private: 
     static const unsigned int _half_size = lenght/2; 
     static const unsigned int _pivot_index = _half_size; //"Silly" pivot policy. Random-pivot instead? http://stackoverflow.com/questions/11498304/generate-random-numbers-in-c-at-compile-time 
     using _pivot = typename dl32TypeAt<_pivot_index,dl32TypeList<Ns...>>::type; 

     using _right = _right_sublist<_pivot>; //"Call" to reordered right sublist computation 
     using _left = _left_sublist<_pivot>; //"Call" to reordered left sublist computation 

    public: 
     /* STEP 2: Recursive "call" to quicksort passing the two generated sublists */ 

     using result = typename dl32Merge< typename _quicksort< _left::size , _left >::result , typename _quicksort< _right::size , _right >::result >::result; 
    }; 

public: 
    using result = typename _quicksort<UINT_LIST::size,UINT_LIST>::result; //"Call" to quicksort computation; 
}; 


/* input/output printing tools */ 

template<typename OUTPUT> 
struct print_output; 

template<> 
struct print_output<empty_uint_list>{ static void print() { cout << endl << endl; } }; 

template<typename HEAD , typename... TAIL> 
struct print_output<dl32TypeList<HEAD,TAIL...>> 
{ 
    static void print() 
    { 
     cout << HEAD::value << (sizeof...(TAIL) > 0 ? "," : ""); 
     print_output<dl32TypeList<TAIL...>>::print(); 
    } 
}; 


/* unsigned int lists generator */ 

template<unsigned int BEGIN , unsigned int END> 
class uint_list_generator 
{ 
private: 
    template<unsigned int _CURRENT,unsigned int _END> 
    struct _generator 
    { 
     using result = typename dl32Merge<uint_list<_CURRENT>,typename _generator<(BEGIN <= END ? _CURRENT + 1 : _CURRENT - 1) , _END>::result>::result; 
    }; 

    template<unsigned int _END> 
    struct _generator<_END,_END> 
    { 
     using result = uint_list<_END>; 
    }; 

public: 
    using result = typename _generator<BEGIN,END>::result; 
}; 

using input = typename uint_list_generator<0,499>::result; 
using output = typename quicksort<input>::result; 

int main() 
{ 
    print_output<input>::print(); 
    print_output<output>::print(); 

    return 0; 
} 

알고리즘은 완벽하게 작동합니다 (컴파일러가 4GB의 RAM을 사용하고 500 요소 목록의 실행을 컴파일하는 데 2 ​​분의 시간을 낭비한 후 ...).

보다시피, 나는 quicksort 구현에서 크거나 같은 비교자를 사용했습니다. 내 질문은 : 템플릿 매개 변수를 통해 비교자를 전달하는 방법은 무엇입니까?

알고리즘은 서명되지 않은 int 래퍼 목록을 데이터로 사용하며 (코드 시작 부분의 "uint_list"선언 참조), comparers는 uint 래퍼를 매개 변수로 기대합니다. 그래서 quicksort 템플릿을 통해 "일반"비교자를 전달할 수 없습니다. 어떤 템플릿 템플릿 매개 변수에 대한

Answer 1

은 :

template <typename UINT_LIST, 
      template <typename UINT1, typename UINT2> class compare = less_than> 
class quicksort 
{ 
    ... 
    using result = typename dl32tmp_if<compare<FIRST,LAST>::value, ... 
}; 
... 
using output = typename quicksort<input, bigger_than>::result; 

게다가 이러한 서명, 당신은 모든 unsigned int -s에 제한되지 않습니다.

이외의 경우 가끔 template typedef을 모방하기 위해 내부에 템플릿을 숨기는 래퍼 클래스를 사용하는 것이 유용 할 수 있습니다.