cpp template metaprogramming

select_sort.cpp

#include <iostream>
#include <array>

// vector
template<int ...data>
struct mvector;

template<int first, int ...data>
struct mvector<first, data...> {
    static constexpr int size = sizeof...(data) + 1;
    static constexpr int value = first;
    typedef mvector<data...> next_type;
    constexpr static std::array<int, sizeof...(data) + 1> array = {first, data...};
};

template<int first>
struct mvector<first> {
    static constexpr int size = 1;
    static constexpr int value = first;
    typedef mvector<> next_type;
    constexpr static int array[] = {first};
};

template<>
struct mvector<> {
    static constexpr int size = 0;
    static constexpr int value = -1;
    typedef mvector<> next_type;
    constexpr static int array[] = {};
};


// 分割向量
template<int index, typename T, typename S>
struct SplitVector;

template<int index, int ...LeftData, int ...RightData>
struct SplitVector<index, mvector<LeftData...>, mvector<RightData...>> {
    typedef SplitVector<index - 1, mvector<LeftData..., mvector<RightData...>::value>, typename mvector<RightData...>::next_type> next_split;
    typedef typename next_split::LeftVector LeftVector;
    typedef typename next_split::RightVector RightVector;
};

template<int ...LeftData, int ...RightData>
struct SplitVector<0, mvector<LeftData...>, mvector<RightData...>> {
    typedef mvector<LeftData...> LeftVector;
    typedef typename mvector<RightData...>::next_type RightVector;
};


// 合并向量
template<typename T, typename S>
struct MergeVector;

template<int ...dataa, int ...datab>
struct MergeVector<mvector<dataa...>, mvector<datab...>> {
    typedef mvector<dataa..., datab...> result_type;
};


// 寻找最大值
template<int now_index, typename U, typename V>
struct FindMax;

template<int now_index, int ...Looped, int ...unLooped>
struct FindMax<now_index, mvector<Looped...>, mvector<unLooped...>> {
    typedef FindMax<now_index + 1, mvector<Looped..., mvector<unLooped...>::value>, typename mvector<unLooped...>::next_type> next_max;
    constexpr static int max = mvector<unLooped...>::value > next_max::max ? mvector<unLooped...>::value : next_max::max;
    constexpr static int max_index = mvector<unLooped...>::value > next_max::max ? now_index : next_max::max_index;
};

template<int now_index, int ...Looped>
struct FindMax<now_index, mvector<Looped...>, mvector<>> {
    typedef FindMax<now_index, mvector<Looped...>, mvector<>> next_max;
    constexpr static int max = -1;
    constexpr static int max_index = now_index;
};

// 
template<typename T, typename S>
struct SelectSortWork;

template<int ...unSorted, int ...Sorted>
struct SelectSortWork<mvector<unSorted...>, mvector<Sorted...>> {
    typedef FindMax<0, mvector<>, mvector<unSorted...>> max_find_type;
    constexpr static int max = max_find_type::max;
    constexpr static int max_index = max_find_type::max_index;
    typedef SplitVector<max_index, mvector<>, mvector<unSorted...>> split_type;
    typedef SelectSortWork<typename MergeVector<typename split_type::LeftVector, typename split_type::RightVector>::result_type, mvector<max, Sorted...>> next_select_sort_work_type;
    typedef typename next_select_sort_work_type::sorted_type sorted_type;
};

template<int ...Sorted>
struct SelectSortWork<mvector<>, mvector<Sorted...>> {
    typedef mvector<Sorted...> sorted_type;
};

template<int ...data>
struct SelectSort {
    typedef SelectSortWork<mvector<data...>, mvector<>> select_sort_type;
    static constexpr std::array<int, sizeof...(data)> value = select_sort_type::sorted_type::array;
};

constexpr static std::array<int, 8> result = SelectSort<1, 2, 4, 3, 12, 34, 56, 78>::value;

int main() {
    for (int loop_i = 0; loop_i < 8; ++loop_i) {
        std::cout << result[loop_i] << std::endl;
    }
    return 0;
}