如何更换网站服务器,岳阳建网站,注册公司深圳,网站图片如何做防盗链定义
类型列表#xff0c;字面意思就是一个存储类型的列表#xff0c;例如std::tupleint, float, double, std::string就是一个类型列表。
templatetypename ...Ts struct type_list {};基础操作
操作约束#xff1a;对于所有操作#xff0c;均要求参数…定义
类型列表字面意思就是一个存储类型的列表例如std::tupleint, float, double, std::string就是一个类型列表。
templatetypename ...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
templatetypename Ts
struct is_empty_impl : std::integral_constantbool, false {};template
struct is_empty_impltype_list : std::integral_constantbool, true {};templatetypename Ts
constexpr static bool is_empty is_empty_implTs::value;Front
templatetypename T struct front_impl {};templatetypename T, typename ...Ts
struct front_impltype_listT, Ts... {using type T;
};templatetypename T using front front_implT::type;Pop front
templatetypename T struct pop_front_impl {};templatetypename T, typename ...Ts
struct pop_front_impltype_listT, Ts... {using type type_listTs...;
};templatetypename T using pop_front pop_front_implT::type;Push front
templatetypename Tl, typename T struct push_front_impl {};templatetypename ...Ts, typename T
struct push_front_impltype_listTs..., T {using type type_listT, Ts...;
};templatetypename Tl, typename T
using push_front push_front_implTl, T::type;Push back
templatetypename Tl, typename T struct push_back_impl {};templatetypename ...Ts, typename T
struct push_back_impltype_listTs..., T {using type type_listTs..., T;
};templatetypename Tl, typename T
using push_back push_back_implTl, T::type;Back
templatetypename Tl struct back_impl {};templatetypename T, typename ...Ts
struct back_impltype_listT, Ts... : back_impltype_listTs... {};templatetypename T
struct back_impltype_listT { using type T; };templatetypename Tl using back back_implTl::type;Pop back
templatetypename Tl struct pop_back_impl {};templatetypename T, typename ...Ts
struct pop_back_impltype_listT, Ts...: push_front_impltypename pop_back_impltype_listTs...::type, T {};templatetypename T
struct pop_back_impltype_listT { using type type_list; };templatetypename Tl using pop_back pop_back_implTl::type;Reverse
templatetypename Tl, bool empty is_emptyTl struct reverse_impl {};templatetypename Tl
struct reverse_implTl, false: push_back_impltypename reverse_implpop_frontTl::type, frontTl {};templatetypename Tl
struct reverse_implTl, true { using type type_list; };templatetypename Tl
using reverse reverse_implTl::type;Largest (可接收自定义类型比较函数参考compare实现)
templatebool judge, typename T1, typename T2
struct type_choose {using type T2;
};templatetypename T1, typename T2
struct type_choosetrue, T1, T2 {using type T1;
};templatetypename T1, typename T2
struct compare : std::integral_constantbool, false {};templatetypename T1, typename T2
requires (sizeof(T1) sizeof(T2))
struct compareT1, T2 : std::integral_constantbool, true {};templatetypename Tl, templatetypename ... typename C struct largest_impl {};templatetypename T, templatetypename ... typename C
struct largest_impltype_listT, C {using type T;
};templatetypename T, typename ...Ts, templatetypename ... typename C
struct largest_impltype_listT, Ts..., C: type_chooseCT, typename largest_impltype_listTs..., C::type::value,T, typename largest_impltype_listTs..., C::type {};templatetypename Tl, templatetypename ... typename C
using largest largest_implTl, C::type;merge
templatetypename Tl1, typename Tl2 struct merge_impl {};templatetypename ...Ts1, typename ...Ts2
struct merge_impltype_listTs1..., type_listTs2... {using type type_listTs1..., Ts2...;
};templatetypename Tl1, typename Tl2
using merge merge_implTl1, Tl2::type;insert
两个子模板会在insert_impltype_listTs..., 0, T sizeof...(Ts) 0的时候冲突所以加上一个requires约束一下。
templatetypename Tl, int index, typename T struct insert_impl {};templatetypename Tf, typename ...Ts, int index, typename T
requires (index 0)
struct insert_impltype_listTf, Ts..., index, T: push_front_impltypename insert_impltype_listTs..., index - 1, T::type, Tf {};templatetypename ...Ts, typename T
struct insert_impltype_listTs..., 0, T: push_front_impltype_listTs..., T {};templatetypename Tl, int index, typename T
using insert insert_implTl, index, T::type;TEST
符合TDD简单测试一下
int main() {// is empty: 1 0 0std::cout is empty: ;std::cout is_emptytype_list is_emptytype_listint is_emptytype_listint, float, double \n\n;// front: 1 0std::cout front: ;std::cout std::is_same_vint, fronttype_listint, float std::is_same_vfloat, fronttype_listint, float \n\n;// pop front: 1 0 1std::cout pop front: ;std::cout std::is_same_vtype_list, pop_fronttype_listint std::is_same_vtype_listint, pop_fronttype_listint std::is_same_vtype_listint, pop_fronttype_listfloat, int \n\n;// push front: 1 0 1std::cout push front: ;std::cout std::is_same_vtype_listint, push_fronttype_list, int std::is_same_vtype_listint, float, push_fronttype_listint, float std::is_same_vtype_listfloat, int, push_fronttype_listint, float \n\n;// push back: 1 1 0std::cout push back: ;std::cout std::is_same_vtype_listint, push_backtype_list, int std::is_same_vtype_listint, float, push_backtype_listint, float std::is_same_vtype_listfloat, int, push_backtype_listint, float \n\n;// back: 1 0 1std::cout back: ;std::cout std::is_same_vint, backtype_listint std::is_same_vint, backtype_listint, float std::is_same_vfloat, backtype_listint, float \n\n;// pop back: 1 1 0std::cout pop back: ;std::cout std::is_same_vtype_list, pop_backtype_listint std::is_same_vtype_listfloat, pop_backtype_listfloat, int std::is_same_vtype_listint, pop_backtype_listfloat, int \n\n;// reverse: 1 0 1 1std::cout reverse: ;std::cout std::is_same_vtype_list, reversetype_list std::is_same_vtype_listint, float, reversetype_listint, float std::is_same_vtype_listfloat, int, reversetype_listint, float std::is_same_vtype_listint, float, double, reversetype_listdouble, 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_listchar, short, int32_t, int64_t, double;using type2 type_listchar, short, int32_t, double, int64_t;std::cout largest: ;std::cout std::is_same_vdouble, largesttype1, compare std::is_same_vdouble, largesttype2, compare std::is_same_vint64_t, largesttype2, compare \n\n;// merge: 1 1 1 0std::cout merge: ;std::cout std::is_same_vtype_listint, mergetype_list, type_listint std::is_same_vtype_listint, mergetype_listint, type_list std::is_same_vtype_listint, float, mergetype_listint, type_listfloat std::is_same_vtype_listint, float, mergetype_listfloat, type_listint \n\n;// insert: 1 1 1std::cout insert: ;std::cout std::is_same_vtype_listint, inserttype_list, 0, int std::is_same_vtype_listint, float, double, inserttype_listint, double, 1, float std::is_same_vtype_listint, float, double, inserttype_listint, float, 2, double \n;return 0;
}Algorithm
Insert sort
维护尾部的有序性每次加入一个新值同时保证尾部的有效性那么先实现一个insert_in_sortedtype_listTs..., T
找到第一个满足C的位置并且在这个值前面插入
templatetypename Tl, typename T, templatetypename ... typename C,bool empty is_emptyTl
struct insert_in_sorted_impl {};templatetypename ...Ts, typename T, templatetypename ... typename C
struct insert_in_sorted_impltype_listTs..., T, C, false: type_choose(Cfronttype_listTs..., T::value),push_fronttype_listTs..., T,push_fronttypename insert_in_sorted_implpop_fronttype_listTs..., T, C::type,fronttype_listTs... {};templatetypename ...Ts, typename T, templatetypename ... typename C
struct insert_in_sorted_impltype_listTs..., T, C, true {using type type_listT;
};templatetypename Tl, typename T, templatetypename ... typename C
using insert_in_sorted insert_in_sorted_implTl, T, C::type;排序实现
templatetypename Tl, templatetypename ... typename C,bool empty is_emptyTl struct insert_sort_impl {};templatetypename ...Ts, templatetypename ... typename C
struct insert_sort_impltype_listTs..., C, true {using type type_list;
};templatetypename ...Ts, templatetypename ... typename C
struct insert_sort_impltype_listTs..., C, false: insert_in_sorted_impltypename insert_sort_implpop_fronttype_listTs..., C::type,fronttype_listTs..., C {};templatetypename Tl, templatetypename ... typename C
using insert_sort insert_sort_implTl, C::type;测试一下结果对不对
int main() {// insert in sorted: 1 1 1 1 1std::cout insert in sorted: ;std::cout std::is_same_vtype_listint32_t, insert_in_sortedtype_list, int32_t , compare std::is_same_vtype_listchar, short, int32_t, int64_t, insert_in_sortedtype_listchar, short, int32_t, int64_t, compare std::is_same_vtype_listchar, short, int32_t, int64_t, insert_in_sortedtype_listchar, short, int64_t, int32_t, compare std::is_same_vtype_listchar, short, int32_t, float, int64_t, insert_in_sortedtype_listchar, short, int32_t, int64_t, float, compare std::is_same_vtype_listchar, int32_t, long long, float, int64_t, insert_in_sortedtype_listchar, long long, float, int64_t, int32_t, compare \n;// insert sort: 1 1 1 1std::cout insert sort: ;std::cout std::is_same_vtype_list, insert_sorttype_list, compare std::is_same_vtype_listchar, insert_sorttype_listchar, compare std::is_same_vtype_listfloat, int, insert_sorttype_listint, float, compare ;// 非稳定排序相同大小的类型初始在前面的会跑到后面去using type_list_sort type_listshort int, char, short, int, long long, unsigned int, unsigned, unsigned long long, unsigned char;using type_list_sort_ans type_listunsigned char, char, short, short int, unsigned, unsigned int, int, unsigned long long, long long;std::cout std::is_same_vtype_list_sort_ans, insert_sorttype_list_sort, compare \n;return 0;
}
