好久没写 C++,今天下午突然有点兴趣就搓了个模板元快排,思路和 Learn you a Haskell 里面快排的思路是一致的。

测试
type 中的结果

下面是代码:

// conditional type
template <bool B, typename Then, typename Else>
struct If
{ using type = Then; };

template <typename Then, typename Else>
struct If <false, Then, Else>
{ using type = Else; };

template <int... T>
struct sequence {};

// catenate 2 (or more) sequences
template <typename... Ts>
struct catenate;

// for catenation of more than 2 sequences
template <typename T, typename... Ts>
struct catenate <T, Ts...>
{
    using type = catenate<T, catenate<Ts...>>::type;
};

// ordinary situations
template <int... Ts, int... Us>
struct catenate<sequence<Ts...>, sequence<Us...>>
{ using type = sequence<Ts..., Us... >; };

template <int... Ts, typename U>
struct catenate<sequence<Ts...>, U>
{ using type = catenate<sequence<Ts...>, typename U::type>::type; };

// less and greater equal filters
template <int X, typename Li>
struct _greq;

template <int X, int Y, int... Ys>
struct _greq<X, sequence<Y, Ys...>>
{
private:
    using next = _greq<X, sequence<Ys...>>::type;
    static constexpr bool Pred = X <= Y;
public:
    using type = If<Pred,
                    typename catenate<sequence<Y>, next>::type,
                    next>::type;
};

template <int X>
struct _greq<X, sequence<>>
{ using type = sequence<>; };

template <int X, typename Li>
struct _less;

template <int X, int Y, int... Ys>
struct _less<X, sequence<Y, Ys...>>
{
private:
    using next =  _less<X, sequence<Ys...>>::type;
    static constexpr bool Pred = X > Y;
public:
    using type = If<Pred,
                    typename catenate<sequence<Y>, next>::type,
                    next>::type;
};

template <int X>
struct _less<X, sequence<>>
{ using type = sequence<>; };

template <typename Li>
struct quick_sort;

// deal with empty sequence
template <>
struct quick_sort<sequence<>>
{ using type = sequence<>; };

// deal with ordinary sequences
template <int X, int... Xs>
struct quick_sort<sequence<X, Xs...>>
{
private:
    using smallerSorted = quick_sort<typename _less<X, sequence<Xs...>>::type>::type;
    using  biggerSorted = quick_sort<typename _greq<X, sequence<Xs...>>::type>::type;
public:
    using type =
        catenate<
            smallerSorted,    
            sequence<X>,
            biggerSorted
        >::type;
};

Offensive77

A little learning is a dangerous thing.

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注