编译期实现排序

编译期间实现排序

  • 在b站上看到的,凭借一点c++ 的知识勉强读懂

思路

  • Values实现将基类对象类型放在(展开在)tuple中,std::tuple<>是个聚合类,能将参数包中不同元素类型糅合成一种类型,排序就是在tuple上进行的

  1. 模板类实现判断, template<bool,typename Then,typename Else> If

  2. 封装成Compare函数模板类用来比较(相同or不同类型)的值,

    1
    2
    3
    4
    // 模板类中的模板类成员
    template<typename T1> struct Less {
    	template<typename T2>  struct Apply {};
    };

  1. 通过编译期对类型的递归推导(其实这里是遍历),配合Compare进行比较,得到std::tuple<>的类型的value的极值

    1. 写出template的递归终止推导情况
    2. 写出递归的普通情况,

  2. 既然能够得到std::tuple<>的极值,那么还要排序,就必须对位置进行调整,实现一个将tuple中的元素去掉一个的模板类

    利用std::tuple_cat()和FindLimit<Comp,std::tuple<>>

  3. 利用FindLimit<>和PopLimit<>,每一步都找到tuple中最小的一个类型(::value),从tuple<>中分离出去,然后对剩下的tuple进行递归,

  • 本质上都是利用对类型的推导,在写的过程中要注意很多细节.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <type_traits>
#include <tuple>
#include <iostream>

template<int ...values>
struct Values {
	// 把值values转换成类型然后展开,放在tuple中
	using type = std::tuple<std::integral_constant<int,values>...>;
};

template<bool,typename Then,typename Else> struct If;

// 结果状态
template<typename Then,typename Else>
struct If<true,Then,Else> {
	using type = Then;
};

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

template<typename T1>
struct Less {
	template<typename T2> struct Apply {
		using type = typename If<(T1::value < T2::value),T1,T2>::type;
	};
};

template<typename T1>
struct GE {
	template<typename T2> struct Apply {
		using type = typename If<(T1::value >= T2::value),T1,T2>::type;
	};
};

// 通过递归两两比较找到std::tuple<>中的极值,
template<template <typename T1> class Comp, typename Tuples> struct FindLimit;
template<template <typename T1> class Comp, typename Head>
struct FindLimit<Comp,std::tuple<Head>> { // 
	using type = Head;
};
template<template<typename T1> class Comp,typename Head,typename ...Tails>
struct FindLimit<Comp,std::tuple<Head,Tails...>> {
	using type =typename Comp<Head>::template Apply<
		typename FindLimit<Comp,std::tuple<Tails...>>::type
		>::type;
};

//从std::tuple中弹出极值
template<typename Limit,typename ...Tuples> struct PopLimit;
// tuple为空,现在只有一个值无需弹出
template<typename Limit>
struct PopLimit<Limit,std::tuple<>> {
	// 弹出后的结果如下
	using type = std::tuple<>;
};
// 给出要Pop的值(类型)和所有值
template<typename Limit,typename ...Others>
//　模板参数推导从tuple中找到了Limit
struct PopLimit<Limit,std::tuple<Limit,Others...>> {
	using type = std::tuple<Others...>;
};
// 没有从当前参数包中的第一个参数中找到,继续找
template<typename Limit,typename Head,typename ...Others>
struct PopLimit<Limit,std::tuple<Head,Others...>> {
	//using type = decltype(std::tuple_cat(std::tuple<Head>(),
	//			PopLimit<Limit,std::tuple<Others...>>::type));
	//using type = decltype(std::tuple_cat(std::tuple<Head>{},
	//(typename PopLimit<Limit,std::tuple<Others...>>::type){}));
	using type = decltype(std::tuple_cat(std::tuple<Head>{},
				typename PopLimit<Limit,std::tuple<Others...>>::type{}));
};

// 排序
template<template <typename T1> class Comp,typename T> struct bSort;
// class Comp中需要推到的类型是　template <typename T1> class Comp
template<template <typename T1> class Comp> 
struct bSort<Comp,std::tuple<>> {
	using type = std::tuple<>;
};

template<template <typename T1> class Comp,typename ...values>
struct bSort<Comp,std::tuple<values...>> {
	// 先递归找到极值
	using limit = typename FindLimit<Comp,std::tuple<values...>>::type;
	using others = typename PopLimit<limit,std::tuple<values...>>::type;
	using type = decltype(std::tuple_cat(std::tuple<limit>{},typename bSort<Comp,others>::type{}));

};

void test() {
	// 都是tuple
	using lst_1_3 = Values<1,2,3>::type;
	using lst_1_2 = Values<1,2>::type;
	using lst_3_1 = Values<3,2,1>::type;
	using lst = Values<1,99,9,4,2,6,100>::type;
	using ans = Values<1,2,4,6,9,99,100>::type;

	using i1 = std::integral_constant<int,1>::type;
	using i2 = std::integral_constant<int,2>::type;
	using i3 = std::integral_constant<int,3>::type;

	// 1. 测试比大小 If判断或者Less
	//static_assert(!std::is_same<If<(i1::value < i2::value),i1,i2>::type,i1>::value,"no problem");
	//static_assert(!std::is_same<Less<i2>::Apply<i3>::type,i2>::value,"i2 < i3");
//	if (std::is_same<If<(i1::value < i2::value),i1,i2>::type,i1>::value)
//		std::cout << "i1 < i2";
	
	// 2. 测试编译找到的极值
	static_assert(!std::is_same<FindLimit<GE,lst>::type,i1>::value, "最小值是　i1");
	
	// 3. 测试排序结果
//	static_assert(!std::is_same<bSort<Less,lst>::type,ans>::value , "排序成功");

}

int main(int argc,char *argv[]) {
	test();
    return 0;
}
C++primer读书笔记

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！