由于日志库的需求，需要一个编译时排序来处理 tag（模板的 typename 只能 append!），所以尝试写了一版，工地 C++ 选手头一回写这么一大串的 template 元编程
接口/目标
注意要实现的是基于类型的排序，
就是给定各个类型不同的优先级，然后给不同的类型排序，直观上就是一个 key(type) 和 value 完全倒置的排序
假设已知各个类型 Ts... 的优先级，期望的接口是
Sort<Ts...>::type 返回一个排好序的 Us...
由于 type 必须是指定某一个类型，因此我使用了 std::tuple
Sort<Ts...>::type = std::tuple<Us...>
例子：
假设，
int优先级为0
double优先级为1
std::string优先级为5
Sort<double, std::string, int>::type则可以展开为std::tuple<int, double, std::string>
需求
现在分析为了实现这个接口需要些什么东西
对比运行时排序
void selectsort(int data[], int lo, int hi) {
for(int i = lo; i <= hi; ++i) {
int choose = i;
for(int j = i+1; j <= hi; ++j) {
if(data[choose] > data[j]) choose = j;
}
std::swap(data[choose], data[i]);
}
}
可以发现需要的东西非常朴素：
- 把类型表示成值
- 找出某个区间的最小值
- 在某个区间交换两个值
下面来逐一实现
KV
要把类型表示成值，本质上来说就是提供一个 kv 映射
// 类型的优先级映射如下
template <ssize_t V>
struct Value {
static constexpr ssize_t value = V;
};
template <typename K>
struct Key {
using type = K;
};
template <typename V>
struct Elem;
// DEMO: sort comp register
// template <>
// struct Elem<int>: Key<int>, Value<1> {};
// template <>
// struct Elem<double>: Key<double>, Value<2> {};
// template <>
// struct Elem<char>: Key<char>, Value<3> {};
// template <>
// struct Elem<float>: Key<float>, Value<4> {};
// template <>
// struct Elem<unsigned>: Key<unsigned>, Value<5> {};
实现了 kv 映射后就可以用来求出所谓最小的类型了
Min
求 min 的过程使用经典的递归处理，为了方便就直接把 value 和 type 都求出来了
template <typename ...Ts>
struct Min {
constexpr static ssize_t value = MinValue<Ts...>::value;
using type = typename MinType<Ts...>::type;
};
template <typename T, typename ...Ts>
struct MinValue {
constexpr static ssize_t value = std::min(Elem<T>::value, MinValue<Ts...>::value);
};
template <typename T>
struct MinValue<T> {
constexpr static ssize_t value = Elem<T>::value;
};
template <typename T, typename ...Ts>
struct MinType {
using type = std::conditional_t<
/*if */Elem<T>::value <= MinValue<Ts...>::value,
/*then*/T,
/*else*/typename MinType<Ts...>::type>;
};
template <typename T>
struct MinType<T> {
using type = T;
};
区间操作
需求三比较蛋疼，类型并没有 swap 或者赋值这种概念
一种间接的方法是，基于 std::tuple，实现一系列的区间操作，比如把区间掰开以及拼接
具体的，假设需要交换 std::tuple<> 中下标为$L$,$R$的类型，
就是要把子区间$[0,L), L, (L, R), R, (R, sizeof…)$分别拆开
最后依次拼接$[0,L), R, (L, R), L, (R, sizeof…)$即可
首先来看拼接 Concat，实现非常简洁
template <typename ...Ts> // 既匹配一个 T，也匹配两个 T,U
struct Concat;
// input: Concat< std::tuple<L....>, std::tuple<R....> >
// output: type -> std::tuple<L..., R...>
template <typename ...L, typename ...R>
struct Concat<std::tuple<L...>, std::tuple<R...>> {
using type = std::tuple<L..., R...>;
};
// std::tuple<T> => type->std::tuple<T>
template <typename T>
struct Concat<std::tuple<T>> {
using type = std::tuple<T>;
};
还有 Select，表示从区间中获取子区间$[L,R]$
（别吐槽命名了，本质就是同一个 Select 过程，做一个分层）
// 从 Ts...中返回 [L,R] 的子区间，用 `std::tuple` 封装
template <ssize_t L, ssize_t R, typename ...Ts>
struct Select {
using type = typename Select1<L, R, 0, Ts...>::type;
using check = std::enable_if_t<L <= R && L >= 0 && R <= sizeof...(Ts)>;
};
// Select1 引入当前下标 `Cur`，用于定位
// Select2 用于直接获取类型
// Select1 区分 Start == Cur 和 不等于的处理情况
// 找到 Start == Cur 的定位后，执行 Select2，表示从当前位置找出连续 End-start+1 个 Type
// 由于过程中返回 `std::tuple`，因此需要复用前面的 `Concat` 来拼接
// not equal
template <ssize_t Start, ssize_t End, ssize_t Cur, typename T, typename ...Ts>
struct Select1 {
using type = typename Select1<Start, End, Cur+1, Ts...>::type;
};
// start == cur
template <ssize_t Start, ssize_t End, typename T, typename ...Ts>
struct Select1<Start, End, Start, T, Ts...> {
using type = typename Select2<End-Start+1, T, Ts...>::type; // MOCK
};
template <ssize_t N, typename T, typename ...Ts>
struct Select2 {
using type = typename Concat<std::tuple<T>, typename Select2<N-1, Ts...>::type >::type;
};
template <typename T, typename ...Ts>
struct Select2<0, T, Ts...>;
template <typename T, typename ...Ts>
struct Select2<1, T, Ts...> {
using type = std::tuple<T>;
};
template <typename T>
struct Select2<1, T> {
using type = std::tuple<T>;
};
顺便，Select 需要用到 L, R 这些下表是需要定位的，就是找出位置，因此加了一个 Find
// T 表示要找出对应下标的类型
template <typename T, typename U, typename ...Ts>
struct Find {
constexpr static ssize_t value = Find1<0, T, U, Ts...>::value;
};
// 还没找到的时候
template <ssize_t Cur, typename T, typename U, typename ...Ts>
struct Find1 {
constexpr static ssize_t value = Find1<Cur+1, T, Ts...>::value;
};
// 找到的时候
template <ssize_t Cur, typename T, typename ...Ts>
struct Find1<Cur, T, T, Ts...> {
constexpr static ssize_t value = Cur;
};
Sort
终于，前面写了一大坨的，我们可以用上了
这里需要注意的是，编译时是不允许“越界”的，
运行时判断越界只需要 if-else 判定下标范围，而在编译时的环境下，是直接编译报错的，毕竟模板没法展开实例化
因此，一个方法就是通过重载决议，把各种边界条件都对上一个（偏）特化的类模板即可
template <typename ...Ts>
struct Sort {
using type = typename Sort1<std::tuple<Ts...>>::type;
};
template <typename T, typename ...Ts>
struct Sort1;
template <typename T>
struct Sort1<std::tuple<T>> {
using type = std::tuple<T>;
};
template <typename T, typename ...Ts>
struct Sort1<std::tuple<T, Ts...>> {
using type = typename Sort2<
Find<typename Min<T, Ts...>::type, T, Ts...>::value,
sizeof...(Ts),
T, Ts...
>::type;
};
// minpos mid
// no std::tuple
template <ssize_t MinPos, ssize_t MaxIdx, typename T, typename ...Ts>
struct Sort2 {
using check = std::enable_if_t<MinPos+1 <= MaxIdx && MinPos-1 >= 0>;
using type = typename Concat<
typename Select<MinPos, MinPos, T, Ts...>::type,
typename Sort1<
typename Concat<
typename Select<0, MinPos-1, T, Ts...>::type,
typename Select<MinPos+1, MaxIdx, T, Ts...>::type
>::type
>::type
>::type;
};
// minpos == 0
template <ssize_t MaxIdx, typename T, typename ...Ts>
struct Sort2<0, MaxIdx, T, Ts...> {
using type = typename Concat<
std::tuple<T>,
typename Sort1<typename Select<1, MaxIdx, T, Ts...>::type>::type
>::type;
};
// minpos == end
template <ssize_t MaxIdx, typename T, typename ...Ts>
struct Sort2<MaxIdx, MaxIdx, T, Ts...> {
using type = typename Concat<
typename Select<MaxIdx, MaxIdx, T, Ts...>::type,
typename Sort1<typename Select<0, MaxIdx-1, T, Ts...>::type>::type
>::type;
};