Type List（C++ 模板元编程）

定义

类型列表，字面意思就是一个存储类型的列表，例如std::tuple<int, float, double, std::string>就是一个类型列表。

template<typename ...Ts> struct type_list {};

基础操作

操作约束：对于所有操作，均要求参数合法，即要求type_list中至少有一个类型，或者提供的下标不越界。

• is_empty

• front

• pop_front

• push_front

• push_back

• back

• pop_back

• reverse

• largest（支持自定义compare）

• merge

• insert

is_empty

template<typename Ts>
struct is_empty_impl : std::integral_constant<bool, false> {};template<>
struct is_empty_impl<type_list<>> : std::integral_constant<bool, true> {};template<typename Ts>
constexpr static bool is_empty = is_empty_impl<Ts>::value;

Front

template<typename T> struct front_impl {};template<typename T, typename ...Ts>
struct front_impl<type_list<T, Ts...>> {using type = T;
};template<typename T> using front = front_impl<T>::type;

Pop front

template<typename T> struct pop_front_impl {};template<typename T, typename ...Ts>
struct pop_front_impl<type_list<T, Ts...>> {using type = type_list<Ts...>;
};template<typename T> using pop_front = pop_front_impl<T>::type;

Push front

template<typename Tl, typename T> struct push_front_impl {};template<typename ...Ts, typename T>
struct push_front_impl<type_list<Ts...>, T> {using type = type_list<T, Ts...>;
};template<typename Tl, typename T>
using push_front = push_front_impl<Tl, T>::type;

Push back

template<typename Tl, typename T> struct push_back_impl {};template<typename ...Ts, typename T>
struct push_back_impl<type_list<Ts...>, T> {using type = type_list<Ts..., T>;
};template<typename Tl, typename T>
using push_back = push_back_impl<Tl, T>::type;

Back

template<typename Tl> struct back_impl {};template<typename T, typename ...Ts>
struct back_impl<type_list<T, Ts...>> : back_impl<type_list<Ts...>> {};template<typename T>
struct back_impl<type_list<T>> { using type = T; };template<typename Tl> using back = back_impl<Tl>::type;

Pop back

template<typename Tl> struct pop_back_impl {};template<typename T, typename ...Ts>
struct pop_back_impl<type_list<T, Ts...>>: push_front_impl<typename pop_back_impl<type_list<Ts...>>::type, T> {};template<typename T>
struct pop_back_impl<type_list<T>> { using type = type_list<>; };template<typename Tl> using pop_back = pop_back_impl<Tl>::type;

Reverse

template<typename Tl, bool empty = is_empty<Tl>> struct reverse_impl {};template<typename Tl>
struct reverse_impl<Tl, false>: push_back_impl<typename reverse_impl<pop_front<Tl>>::type, front<Tl>> {};template<typename Tl>
struct reverse_impl<Tl, true> { using type = type_list<>; };template<typename Tl>
using reverse = reverse_impl<Tl>::type;

Largest (可接收自定义类型比较函数：参考compare实现)

template<bool judge, typename T1, typename T2>
struct type_choose {using type = T2;
};template<typename T1, typename T2>
struct type_choose<true, T1, T2> {using type = T1;
};template<typename T1, typename T2>
struct compare : std::integral_constant<bool, false> {};template<typename T1, typename T2>
requires (sizeof(T1) > sizeof(T2))
struct compare<T1, T2> : std::integral_constant<bool, true> {};template<typename Tl, template<typename ...> typename C> struct largest_impl {};template<typename T, template<typename ...> typename C>
struct largest_impl<type_list<T>, C> {using type = T;
};template<typename T, typename ...Ts, template<typename ...> typename C>
struct largest_impl<type_list<T, Ts...>, C>: type_choose<C<T, typename largest_impl<type_list<Ts...>, C>::type>::value,T, typename largest_impl<type_list<Ts...>, C>::type> {};template<typename Tl, template<typename ...> typename C>
using largest = largest_impl<Tl, C>::type;

merge

template<typename Tl1, typename Tl2> struct merge_impl {};template<typename ...Ts1, typename ...Ts2>
struct merge_impl<type_list<Ts1...>, type_list<Ts2...>> {using type = type_list<Ts1..., Ts2...>;
};template<typename Tl1, typename Tl2>
using merge = merge_impl<Tl1, Tl2>::type;

insert

两个子模板会在insert_impl<type_list<Ts...>, 0, T> sizeof...(Ts) > 0的时候冲突，所以加上一个requires约束一下。

template<typename Tl, int index, typename T> struct insert_impl {};template<typename Tf, typename ...Ts, int index, typename T>
requires (index > 0)
struct insert_impl<type_list<Tf, Ts...>, index, T>: push_front_impl<typename insert_impl<type_list<Ts...>, index - 1, T>::type, Tf> {};template<typename ...Ts, typename T>
struct insert_impl<type_list<Ts...>, 0, T>: push_front_impl<type_list<Ts...>, T> {};template<typename Tl, int index, typename T>
using insert = insert_impl<Tl, index, T>::type;

TEST

符合TDD，简单测试一下：

int main() {// is empty: 1 0 0std::cout << "is empty: ";std::cout << is_empty<type_list<>> << " "<< is_empty<type_list<int>> << " "<< is_empty<type_list<int, float, double>> << "\n\n";// front: 1 0std::cout << "front: ";std::cout << std::is_same_v<int, front<type_list<int, float>>> << " "<< std::is_same_v<float, front<type_list<int, float>>> << "\n\n";// pop front: 1 0 1std::cout << "pop front: ";std::cout << std::is_same_v<type_list<>, pop_front<type_list<int>>> << " "<< std::is_same_v<type_list<int>, pop_front<type_list<int>>> << " "<< std::is_same_v<type_list<int>, pop_front<type_list<float, int>>> << "\n\n";// push front: 1 0 1std::cout << "push front: ";std::cout << std::is_same_v<type_list<int>, push_front<type_list<>, int>> << " "<< std::is_same_v<type_list<int, float>, push_front<type_list<int>, float>> << " "<< std::is_same_v<type_list<float, int>, push_front<type_list<int>, float>> << "\n\n";// push back: 1 1 0std::cout << "push back: ";std::cout << std::is_same_v<type_list<int>, push_back<type_list<>, int>> << " "<< std::is_same_v<type_list<int, float>, push_back<type_list<int>, float>> << " "<< std::is_same_v<type_list<float, int>, push_back<type_list<int>, float>> << "\n\n";// back: 1 0 1std::cout << "back: ";std::cout << std::is_same_v<int, back<type_list<int>>> << " "<< std::is_same_v<int, back<type_list<int, float>>> << " "<< std::is_same_v<float, back<type_list<int, float>>> << "\n\n";// pop back: 1 1 0std::cout << "pop back: ";std::cout << std::is_same_v<type_list<>, pop_back<type_list<int>>> << " "<< std::is_same_v<type_list<float>, pop_back<type_list<float, int>>> << " "<< std::is_same_v<type_list<int>, pop_back<type_list<float, int>>> << "\n\n";// reverse: 1 0 1 1std::cout << "reverse: ";std::cout << std::is_same_v<type_list<>, reverse<type_list<>>> << " "<< std::is_same_v<type_list<int, float>, reverse<type_list<int, float>>> << " "<< std::is_same_v<type_list<float, int>, reverse<type_list<int, float>>> << " "<< std::is_same_v<type_list<int, float, double>, reverse<type_list<double, float, int>>> << "\n\n";// largest: 1, 0, 1// char, short, int32_t, int64_t, doublestd::cout << sizeof(char) << " " << sizeof(short) << " " << sizeof(int32_t)<< " " << sizeof(int64_t) << " " << sizeof(double) << "\n";using type1 = type_list<char, short, int32_t, int64_t, double>;using type2 = type_list<char, short, int32_t, double, int64_t>;std::cout << "largest: ";std::cout << std::is_same_v<double, largest<type1, compare>> << " "<< std::is_same_v<double, largest<type2, compare>> << " "<< std::is_same_v<int64_t, largest<type2, compare>> << "\n\n";// merge: 1 1 1 0std::cout << "merge: ";std::cout << std::is_same_v<type_list<int>, merge<type_list<>, type_list<int>>> << " "<< std::is_same_v<type_list<int>, merge<type_list<int>, type_list<>>> << " "<< std::is_same_v<type_list<int, float>, merge<type_list<int>, type_list<float>>> << " "<< std::is_same_v<type_list<int, float>, merge<type_list<float>, type_list<int>>> << "\n\n";// insert: 1 1 1std::cout << "insert: ";std::cout << std::is_same_v<type_list<int>, insert<type_list<>, 0, int>> << " "<< std::is_same_v<type_list<int, float, double>, insert<type_list<int, double>, 1, float>> << " "<< std::is_same_v<type_list<int, float, double>, insert<type_list<int, float>, 2, double>> << "\n";return 0;
}

Algorithm

Insert sort

维护尾部的有序性，每次加入一个新值，同时保证尾部的有效性，那么先实现一个insert_in_sorted<type_list<Ts...>, T>

• 找到第一个满足C的位置，并且在这个值前面插入

template<typename Tl, typename T, template<typename ...> typename C,bool empty = is_empty<Tl>>
struct insert_in_sorted_impl {};template<typename ...Ts, typename T, template<typename ...> typename C>
struct insert_in_sorted_impl<type_list<Ts...>, T, C, false>: type_choose<(C<front<type_list<Ts...>>, T>::value),push_front<type_list<Ts...>, T>,push_front<typename insert_in_sorted_impl<pop_front<type_list<Ts...>>, T, C>::type,front<type_list<Ts...>>>> {};template<typename ...Ts, typename T, template<typename ...> typename C>
struct insert_in_sorted_impl<type_list<Ts...>, T, C, true> {using type = type_list<T>;
};template<typename Tl, typename T, template<typename ...> typename C>
using insert_in_sorted = insert_in_sorted_impl<Tl, T, C>::type;

• 排序实现

template<typename Tl, template<typename ...> typename C,bool empty = is_empty<Tl>> struct insert_sort_impl {};template<typename ...Ts, template<typename ...> typename C>
struct insert_sort_impl<type_list<Ts...>, C, true> {using type = type_list<>;
};template<typename ...Ts, template<typename ...> typename C>
struct insert_sort_impl<type_list<Ts...>, C, false>: insert_in_sorted_impl<typename insert_sort_impl<pop_front<type_list<Ts...>>, C>::type,front<type_list<Ts...>>, C> {};template<typename Tl, template<typename ...> typename C>
using insert_sort = insert_sort_impl<Tl, C>::type;

• 测试一下结果对不对

int main() {// insert in sorted: 1 1 1 1 1std::cout << "insert in sorted: ";std::cout << std::is_same_v<type_list<int32_t>, insert_in_sorted<type_list<>, int32_t , compare>> << " "<< std::is_same_v<type_list<char, short, int32_t, int64_t>, insert_in_sorted<type_list<char, short, int32_t>, int64_t, compare>> << " "<< std::is_same_v<type_list<char, short, int32_t, int64_t>, insert_in_sorted<type_list<char, short, int64_t>, int32_t, compare>> << " "<< std::is_same_v<type_list<char, short, int32_t, float, int64_t>, insert_in_sorted<type_list<char, short, int32_t, int64_t>, float, compare>> << " "<< std::is_same_v<type_list<char, int32_t, long long, float, int64_t>, insert_in_sorted<type_list<char, long long, float, int64_t>, int32_t, compare>> << "\n";// insert sort: 1 1 1 1std::cout << "insert sort: ";std::cout << std::is_same_v<type_list<>, insert_sort<type_list<>, compare>> << " "<< std::is_same_v<type_list<char>, insert_sort<type_list<char>, compare>> << " "<< std::is_same_v<type_list<float, int>, insert_sort<type_list<int, float>, compare>> << " ";// 非稳定排序，相同大小的类型，初始在前面的会跑到后面去using type_list_sort = type_list<short int, char, short, int, long long, unsigned int, unsigned, unsigned long long, unsigned char>;using type_list_sort_ans = type_list<unsigned char, char, short, short int, unsigned, unsigned int, int, unsigned long long, long long>;std::cout << std::is_same_v<type_list_sort_ans, insert_sort<type_list_sort, compare>> << "\n";return 0;
}