c++templatestemplate-meta-programmingcompile-time

C++ Template Arguments Sort


I'm looking for template code to sort template arguments by the return value of their static member function static constexpr int getType(), something like:

#include <iostream>
#include <type_traits>

struct A {
    static constexpr int getType() { return 1; }
};

struct B {
    static constexpr int getType() { return 2; }
};

struct C {
    static constexpr int getType() { return 3; }
};

template <typename...T>
struct Sort { /*...*/ };

int main() {
    using Sorted = Sort<C, A, B>::type; // std::tuple<A, B, C> or something like
    std::cout << typeid(Sorted).name() << std::endl;
    return 0;
}

Anyway, I want a typename sequence in ascending order in any form.


Solution

  • OK, I made it -- a compile time quick sort!

    #include <iostream>
    #include <typeinfo>
    
    template <typename T1, typename T2>
    struct compare {
        static constexpr bool less = T1::value < T2::value;
    };
    
    template <typename... Seq>
    struct Sequence {
    };
    
    template <typename S1, typename S2>
    struct SequenceExtend;
    
    template <typename... Seq1, typename... Seq2>
    struct SequenceExtend<Sequence<Seq1...>, Sequence<Seq2...>> {
        using type = Sequence<Seq1..., Seq2...>;
    };
    
    template <typename S, typename T>
    struct SequenceAppend;
    
    template <typename... Seq, typename T>
    struct SequenceAppend<Sequence<Seq...>, T> {
        using type = Sequence<Seq..., T>;
    };
    
    template <typename Pivot, typename Seq>
    struct SequencePartition;
    
    template <typename Pivot, typename First>
    struct SequencePartition<Pivot, Sequence<First>> {
        using less = std::conditional_t<compare<First, Pivot>::less, Sequence<First>, Sequence<>>;
        using greater = std::conditional_t<!compare<First, Pivot>::less, Sequence<First>, Sequence<>>;
    };
    
    template <typename Pivot, typename First, typename...Rest>
    struct SequencePartition<Pivot, Sequence<First, Rest...>> {
        using less = std::conditional_t<
            compare<First, Pivot>::less,
            typename SequenceAppend<typename SequencePartition<Pivot, Sequence<Rest...>>::less, First>::type,
            typename SequencePartition<Pivot, Sequence<Rest...>>::less
        >;
    
        using greater = std::conditional_t <
            !compare<First, Pivot>::less,
            typename SequenceAppend<typename SequencePartition<Pivot, Sequence<Rest...>>::greater, First>::type,
            typename SequencePartition<Pivot, Sequence<Rest...>>::greater
        >;
    };
    
    template <typename... Ts>
    struct QuickSort {
    private:
        template <typename S>
        struct SortPass;
    
        template <>
        struct SortPass<Sequence<>> {
            using type = Sequence<>;
        };
    
        template <typename T>
        struct SortPass<Sequence<T>> {
            using type = Sequence<T>;
        };
    
        template <typename Pivot, typename... Rest>
        struct SortPass<Sequence<Pivot, Rest...>> {
            using less = typename SequencePartition<Pivot, Sequence<Rest...>>::less;
            using greater = typename SequencePartition<Pivot, Sequence<Rest...>>::greater;
            using type = typename SequenceExtend<
                typename SequenceAppend<typename SortPass<less>::type, Pivot>::type,
                typename SortPass<greater>::type
            >::type;
        };
    
    public:
        using type = typename SortPass<Sequence<Ts...>>::type;
    };
    
    struct A {
        static constexpr int value = 1;
    };
    
    struct B {
        static constexpr int value = 2;
    };
    
    struct C {
        static constexpr int value = 3;
    };
    
    int main() {
        using sorted1 = QuickSort<A, B, C>::type;
        using sorted2 = QuickSort<A, C, B>::type;
        using sorted3 = QuickSort<B, A, C>::type;
        using sorted4 = QuickSort<B, C, A>::type;
        using sorted5 = QuickSort<C, A, B>::type;
        using sorted6 = QuickSort<C, B, A>::type;
    
        return 0;
    }