【C++ Templates（22）】Typelist

2018-06-29 本文已影响49人 downdemo

高效编程一般需要使用各种数据结构，元编程也不例外。对于类型元编程，核心数据结构就是typelist，顾名思义，一个包含类型的列表。模板元编程能操作这些类型列表以生成部分可执行程序。大多数调用typelist的操作使用了模板元编程，所以此前务必先熟悉元编程

Typelist解析

typelist提供和一个列表相关的操作：迭代列表中的元素，添加或移除元素。然而typelist不同于大多数运行时数据结构，如std::list，typelist不允许转变。比如，添加一个元素到std::list改变链表本身，且改变能被其他有访问权的任何部分观测到。添加一个元素到typelist则不会改变原本的typelist，而是创建一个新的typelist
一个typelist通常实现为一个类模板特化，它对模板实参中typelist的内容（即包含的类型及其顺序）进行编码。一个直接的实现就是对参数包抓红的元素编码

// typelist/typelist.hpp
template<typename... Elements>
class Typelist
{
};

Typelist（上面这个类）的元素直接写为模板实参，一个空的typelist写为Typelist<>，只包含int的typelist则写为Typelist<int>，以此类推。下面是包含所有有符号整型的typelist

using SignedIntegralTypes =
    Typelist<signed char, short, int, long, long long>;

操作这个typelist通常需要将它拆分开，一般分离第一个元素在一个列表（头部），剩下的在另一个列表（尾部）。比如下面的Front元函数从typelist解压第一个元素

// typelist/typelistfront.hpp

template<typename List>
class FrontT;

template<typename Head, typename... Tail>
class FrontT<Typelist<Head, Tail...>>
{
public:
    using Type = Head;
};

template<typename List>
using Front = typename FrontT<List>::Type;

因此FrontT<SignedIntegralTypes>::Type将生成signed char。类似地，下面的PopFront元函数从typelist移除第一个元素，它将typelist元素分为头部和尾部，然后从尾部元素构建一个新的Typelist特化

// typelist/typelistpopfront.hpp

template<typename List>
class PopFrontT;

template<typename Head, typename... Tail>
class PopFrontT<Typelist<Head, Tail...>> {
public:
    using Type = Typelist<Tail...>;
};

template<typename List>
using PopFront = typename PopFrontT<List>::Type;

PopFront<SignedIntegralTypes>生成Typelist<short, int, long, long long>
也可以通过捕获一个模板参数包中所有现有的元素，插入元素到typelist之前，然后创建一个新的包含所有那些元素的Typelist特化

// typelist/typelistpushfront.hpp

template<typename List, typename NewElement>
class PushFrontT;

template<typename... Elements, typename NewElement>
class PushFrontT<Typelist<Elements...>, NewElement> {
public:
    using Type = Typelist<NewElement, Elements...>;
};

template<typename List, typename NewElement>
using PushFront = typename PushFrontT<List, NewElement>::Type;

PushFront<SignedIntegralTypes, bool>生成Typelist<bool, signed char, short, int, long, long long>

Typelist算法

基本的typelist操作Front、PopFront和PushFront能组合起来创建更有趣的typelist操作，比如可以通过应用PushFront到PopFront的结果，替代typelist的第一个元素

using Type = PushFront<PopFront<SignedIntegralTypes>, bool>;
// equivalent to Typelist<bool, short, int, long, long long>

更远一些，可以实现模板元函数操作在typelist上的算法，如搜索、转换、翻转

索引

一个typelist上最基本的操作之一是从列表解压一个特定的元素，这里归纳这个操作以解压第N个元素，比如解压给定typelist的在索引2位置的类型

using TL = NthElement<Typelist<short, int, long>, 2>;

这里使得TL相当于long的别名，NthElement操作使用递归元程序实现，它将遍历typelist直到找到需要的元素

// typelist/nthelement.hpp

// recursive case:
template<typename List, unsigned N>
class NthElementT : public NthElementT<PopFront<List>, N-1>
{
};

// basis case:
template<typename List>
class NthElementT<List, 0> : public FrontT<List>
{
};

template<typename List, unsigned N>
using NthElement = typename NthElementT<List, N>::Type;

首先考虑N为0的基本情况，这个特化通过提供在列表前的元素终止递归，它通过公有继承自FrontT<List>实现这点
递归情况也是模板的基本定义，它遍历typelist，由于局部特化保证N>0，递归情况移除前面的元素并请求剩余列表的第（N-1）个元素。在我们的例子中

NthElementT<Typelist<short, int, long>, 2>
// 继承自
NthElementT<Typelist<int, long>, 1>
// 继承自
NthElementT<Typelist<long>, 0>

找到最佳匹配

有许多查找数据的typelist算法，比如找到typelist中最大的类型（比如为了给列表中的任何类型分配足够的存储空间），这可以用一个递归模板元程序实现

// typelist/largesttype.hpp

template<typename List>
class LargestTypeT;

// recursive case:
template<typename List>
class LargestTypeT
{
private:
    using First = Front<List>;
    using Rest = typename LargestTypeT<PopFront<List>>::Type;
public:
    using Type = IfThenElse<(sizeof(First) >= sizeof(Rest)), First, Rest>;
};

// basis case:
template<>
class LargestTypeT<Typelist<>>
{
public:
    using Type = char;
};

template<typename List>
using LargestType = typename LargestTypeT<List>::Type;

LargestType算法将返回typelist中第一个最大的类型，比如给出Typelist<bool, int, long, short>，这个算法将返回第一个和long一样大的类型，可能是int或long，取决于平台
LargestTypeT的基本模板兼职算法的递归的情况，它采用通用的first/rest idiom，有三个步骤。第一步，计算只基于第一个元素的部分结果，在这个例子中，它是列表的前一个元素，并将其放在First中。接着，它递归计算列表中剩余元素的结果，并把结果放在Rest中。比如在Typelist<bool, int,
long, short>的第一步递归中，First是bool，Rest是将这个算法用于Typelist<int, long, short>的结果。第三步结合First和Rest结果来产生答案。这里IfThenElse选择列表中的第一个元素（First）或迄今为止最好的候选（Rest）中更大的那个，并返回优胜者。>=打破支持更早出现在列表中的元素的关系
当列表为空时，递归终止。默认地，使用char作为一个哨兵类型来初始化算法，因为每个类型和char一样大
注意基本情况显式指出空的typelist为Typelist<>，这有点不幸，因为它排除了使用其他类型的typelist。为了解决这个问题，引入一个IsEmpty元函数来判断给出的typelist是否没有元素

// typelist/typelistisempty.hpp

template<typename List>
class IsEmpty
{
public:
    static constexpr bool value = false;
};

template<>
class IsEmpty<Typelist<>> {
public:
    static constexpr bool value = true;
};

使用IsEmpty，可以实现LargestType以使它对于任何实现Front、PopFront和IsEmpty的typelist同样适用

// typelist/genericlargesttype.hpp

template<typename List, bool Empty = IsEmpty<List>::value>
class LargestTypeT;

// recursive case:
template<typename List>
class LargestTypeT<List, false>
{
private:
    using Contender = Front<List>;
    using Best = typename LargestTypeT<PopFront<List>>::Type;
public:
    using Type = IfThenElse<(sizeof(Contender) >= sizeof(Best)),
        Contender, Best>;
};

// basis case:
template<typename List>
class LargestTypeT<List, true>
{
public:
    using Type = char;
};

template<typename List>
using LargestType = typename LargestTypeT<List>::Type;

添加Typelist

PushFront原始操作允许添加新元素到typelist之前，生成一个新的typelist，假如想添加到列表末尾，只要小小改动PushFront就能得到PushBack

// typelist/typelistpushback.hpp

template<typename List, typename NewElement>
class PushBackT;

template<typename... Elements, typename NewElement>
class PushBackT<Typelist<Elements...>, NewElement>
{
public:
    using Type = Typelist<Elements..., NewElement>;
};

template<typename List, typename NewElement>
using PushBack = typename PushBackT<List, NewElement>::Type;

然而，和LargestType算法一样，可以为PushBack实现一个通用的算法，只要使用原始操作Front、PushFront、PopFront和IsEmpty

// typelist/genericpushback.hpp

template<typename List, typename NewElement, bool =
IsEmpty<List>::value>
class PushBackRecT;

// recursive case:
template<typename List, typename NewElement>
class PushBackRecT<List, NewElement, false>
{
    using Head = Front<List>;
    using Tail = PopFront<List>;
    using NewTail = typename PushBackRecT<Tail, NewElement>::Type;
public:
    using Type = PushFront<Head, NewTail>;
};

// basis case:
template<typename List, typename NewElement>
class PushBackRecT<List, NewElement, true>
{
public:
    using Type = PushFront<List, NewElement>;
};

// generic push-back operation:
template<typename List, typename NewElement>
class PushBackT : public PushBackRecT<List, NewElement> { };

template<typename List, typename NewElement>
using PushBack = typename PushBackT<List, NewElement>::Type;

PushBackRecT模板管理递归，在基本情况中，使用PushFront添加NewElement到空列表，因为在空列表中PushFront等价于PushBack。递归情况有趣得多：它分离这个列表为第一个元素（Head）和一个包含剩余元素的typelist（Tail），新元素再添加到Tail，递归地生成NewTail，然后再使用PushFront添加Head到NewTail之前来构建最后的列表
来对一个简单的例子打开递归

PushBackRecT<Typelist<short, int>, long>

在我们的最外层步骤中，Head是short，Tail是Typelist<int>，递归为

PushBackRecT<Typelist<int>, long>

Head是int，Tail是Typelist<>，再次递归计算

PushBackRecT<Typelist<>, long>

触发基本情况并返回PushFront<Typelist<>, long>，它本身计算为Typelist<long>，随后递归展开，把之前的Head压入列表前

PushFront<int, Typelist<long>>

这生成Typelist<int, long>，递归再次展开，把最外层的Head（short）压入列表

PushFront<short, Typelist<int, long>>

这产生最终结果

Typelist<short, int, long>

通用的PushBackRecT实现能用于任何类型的typelist，就像之前的算法一样，它需要一个线性数量的模板实例化来计算，因为对于长度为N的typelist，将有N+1个PushBackRect和PushFrontT的实例化，以及N个FrontT和PopFrontT的实例化。计算这些模板实例化的数量能粗略估计编译一个特定元程序的时间，因为模板实例化本身相当于一个编译器的调用进程
对于巨大的模板元程序，编译时间是一个问题，因此尝试减少通过执行这些算法产生的模板实例化数量是合理的。事实上，在第一个PushBack的实现中，采用了一个Typelist的局部特化，只需要一个常数数量的模板实例化，这使其在编译期比泛型版本更高效。此外，由于它被描述为一个PushBackT的局部特化，当在一个Typelist实例上执行PushBack时，这个高效的实现将自动被选择，将算法特化的概念引入模板元编程

翻转Typelist

当typelist的元素有一定顺序时，用一些算法可以很方便地翻转元素顺序。比如SignedIntegralTypes根据升序排序，然而翻转为降序来产生Typelist<long
long, long, int, short, signed char>可能更有用，Reverse算法可实现这个元函数

// typelist/typelistreverse.hpp

template<typename List, bool Empty = IsEmpty<List>::value>
class ReverseT;

template<typename List>
using Reverse = typename ReverseT<List>::Type;

// recursive case:
template<typename List>
class ReverseT<List, false>
: public PushBackT<Reverse<PopFront<List>>, Front<List>> { };

// basis case:
template<typename List>
class ReverseT<List, true>
{
public:
    using Type = List;
};

元函数的递归基本情况是一个空的typelist上的识别函数，递归情况把列表分离为首元素和剩余元素。比如，如果给出Typelist<short, int, long>，递归先把short分离出来，然后递归地翻转剩余的元素（生成Typelist<long,
int>），最后用PushBackT把首元素添加到翻转后的列表（生成Typelist<long, int, short>）
Reverse算法使得实现一个移除尾元素的PopBackT操作可行

// typelist/typelistpopback.hpp

template<typename List>
class PopBackT {
public:
    using Type = Reverse<PopFront<Reverse<List>>>;
};

template<typename List>
using PopBack = typename PopBackT<List>::Type;

这个算法翻转列表，使用PopFront移除首元素，然后再次翻转列表

转换Typelist

有时可能想转换列表中的所有类型，比如使用AddConst元函数把每个类型转换为const版本

// typelist/addconst.hpp

template<typename T>
struct AddConstT
{
    using Type = T const;
};

template<typename T>
using AddConst = typename AddConstT<T>::Type;

接着，实现一个Transform算法，使用一个typelist和一个元函数（Transform<SignedIntegralTypes, AddConstT>），生成另一个typelist

// typelist/transform.hpp

template<typename List, template<typename T> class MetaFun,
bool Empty = IsEmpty<List>::value>
class TransformT;

// recursive case:
template<typename List, template<typename T> class MetaFun>
class TransformT<List, MetaFun, false>
: public PushFrontT<typename TransformT<PopFront<List>,
MetaFun>::Type,
typename MetaFun<Front<List>>::Type>
{
};

// basis case:
template<typename List, template<typename T> class MetaFun>
class TransformT<List, MetaFun, true>
{
public:
    using Type = List;
};

template<typename List, template<typename T> class MetaFun>
using Transform = typename TransformT<List, MetaFun>::Type;

累加Typelist

Transform常和Accumulate算法一起使用。Accumulate算法使用一个带有元素T1，T2，...，TN的typelist T，一个初始化类型I，一个接受两个类型返回一个类型的元函数F。Accumulate返回F (F (F (...F (I, T1), T2), ..., TN−1), TN )
根据typelist，选用的F，初始化类型，可以使用Accumulate生成许多不同的输出。比如如果F选择两个类型中最大的那个，Accumulate的行为就像LargestType算法，如果F接受一个typelist和一个类型并把类型放到typelist尾部，Accumulate的行为就像Reverse算法

// typelist/accumulate.hpp

template<typename List,
    template<typename X, typename Y> class F,
    typename I,
    bool = IsEmpty<List>::value>
class AccumulateT;

// recursive case:
template<typename List,
    template<typename X, typename Y> class F,
    typename I>
class AccumulateT<List, F, I, false>
: public AccumulateT<PopFront<List>, F,
    typename F<I, Front<List>>::Type>
{
};

// basis case:
template<typename List,
    template<typename X, typename Y> class F,
    typename I>
class AccumulateT<List, F, I, true>
{
public:
    using Type = I;
};

template<typename List,
    template<typename X, typename Y> class F,
    typename I>
using Accumulate = typename AccumulateT<List, F, I>::Type;

使用Accumulate，可以使用PushFrontT作为元函数F，空的typelist（TypeList<T>）作为初始类型I，来翻转typelist

using Result = Accumulate<SignedIntegralTypes, PushFrontT, Typelist<>>;
// produces TypeList<long long, long, int, short, signed char>

实现一个Accumulator-based版本的LargestType，LargestTypeAcc需要一些努力，因为需要生成一个返回两个类型中较大者的元函数

// typelist/largesttypeacc0.hpp

template<typename T, typename U>
class LargerTypeT
: public IfThenElseT<sizeof(T) >= sizeof(U), T, U>
{
};

template<typename Typelist>
class LargestTypeAccT
: public AccumulateT<PopFront<Typelist>, LargerTypeT,
Front<Typelist>>
{
};

template<typename Typelist>
using LargestTypeAcc = typename LargestTypeAccT<Typelist>::Type;

注意这个LargestType的构建需要一个非空的typelist，因为它提供typelist的首元素作为初始类型。可以显式处理这个空列表情况，通过返回一些哨兵类型（char或void）或通过使得算法本身SFINAE-friendly

// typelist/largesttypeacc.hpp

template<typename T, typename U>
class LargerTypeT
: public IfThenElseT<sizeof(T) >= sizeof(U), T, U>
{
};

template<typename Typelist, bool = IsEmpty<Typelist>::value>
class LargestTypeAccT;
template<typename Typelist>
class LargestTypeAccT<Typelist, false>
: public AccumulateT<PopFront<Typelist>, LargerTypeT,
Front<Typelist>>
{
};

template<typename Typelist>
class LargestTypeAccT<Typelist, true>
{
};

template<typename Typelist>
using LargestTypeAcc = typename LargestTypeAccT<Typelist>::Type;

插入排序

最终的typelist算法是实现插入排序，和其他算法一样，递归把列表分解首元素（头部）和剩余元素（尾部），尾部随后递归地排序，头部再插入排序后的列表的正确的位置

// typelist/insertionsort.hpp

template<typename List,
    template<typename T, typename U> class Compare,
    bool = IsEmpty<List>::value>
class InsertionSortT;

template<typename List,
    template<typename T, typename U> class Compare>
using InsertionSort = typename InsertionSortT<List, Compare>::Type;

// recursive case (insert first element into sorted list):
template<typename List,
    template<typename T, typename U> class Compare>
class InsertionSortT<List, Compare, false>
: public InsertSortedT<InsertionSort<PopFront<List>, Compare>,
    Front<List>, Compare>
{
};

// basis case (an empty list is sorted):
template<typename List,
    template<typename T, typename U> class Compare>
class InsertionSortT<List, Compare, true>
{
public:
    using Type = List;
};

插入排序的核心是InsertSortedT元函数，它把一个值插入一个已排序的列表中

// typelist/insertsorted.hpp

#include "identity.hpp"
template<typename List, typename Element,
    template<typename T, typename U> class Compare,
    bool = IsEmpty<List>::value>
class InsertSortedT;

// recursive case:
template<typename List, typename Element,
    template<typename T, typename U> class Compare>
class InsertSortedT<List, Element, Compare, false>
{
    // compute the tail of the resulting list:
    using NewTail =
        typename IfThenElse<Compare<Element, Front<List>>::value,
        IdentityT<List>,
        InsertSortedT<PopFront<List>, Element, Compare>
        >::Type;

    // compute the head of the resulting list:
    using NewHead = IfThenElse<Compare<Element, Front<List>>::value,
        Element,
        Front<List>>;
public:
    using Type = PushFront<NewTail, NewHead>;
};

// basis case:
template<typename List, typename Element,
    template<typename T, typename U> class Compare>
class InsertSortedT<List, Element, Compare, true>
: public PushFrontT<List, Element>
{
};

template<typename List, typename Element,
    template<typename T, typename U> class Compare>
using InsertSorted = typename InsertSortedT<List, Element, Compare>::Type;

这个实现包含一个禁止初始化不使用的类型的编译期优化，下面的实现技术上也是正确的

template<typename List, typename Element,
    template<typename T, typename U> class Compare>
class InsertSortedT<List, Element, Compare, false>
: public IfThenElseT<Compare<Element, Front<List>>::value,
    PushFront<List, Element>,
    PushFront<InsertSorted<PopFront<List>,
        Element, Compare>,
    Front<List>>>
{
};

然而这样一个递归情况的构建是没必要的，因为它计算了IfThenElseT所有分支的模板实参，这里then分支的PushFront是低开销的，但else分支的InsertSorted则不是
下面演示了对一个类型的列表基于他们的大小使用插入排序

// typelist/insertionsorttest.hpp

template<typename T, typename U>
struct SmallerThanT {
    static constexpr bool value = sizeof(T) < sizeof(U);
};

void testInsertionSort()
{
    using Types = Typelist<int, char, short, double>;
    using ST = InsertionSort<Types, SmallerThanT>;
    std::cout << std::is_same<ST,Typelist<char, short, int, double>>::value
        << '\n';
}

非类型Typelist

在一些情况下，typelist也能用于编译期值的序列，一个简单的生成编译期值的typelist的方法是定义一个CRValue类模板，它表示一个typelist中特定类型的值

// typelist/ctvalue.hpp
template<typename T, T Value>
struct CTValue
{
    static constexpr T value = Value;
};

使用CTValue模板，现在可以表达一个包含质数整型值的typelist

using Primes = Typelist<CTValue<int, 2>, CTValue<int, 3>,
    CTValue<int, 5>, CTValue<int, 7>,
    CTValue<int, 11>>;

使用这个表示，可以在一个值typelist上进行数值计算。一个MultiplyT模板接受两个同类型的编译期值并生成一个新的同类型编译期值，它为接受的两个值的乘积

// typelist/multiply.hpp

template<typename T, typename U>
struct MultiplyT;

template<typename T, T Value1, T Value2>
struct MultiplyT<CTValue<T, Value1>, CTValue<T, Value2>>
{
public:
    using Type = CTValue<T, Value1 * Value2>;
};

template<typename T, typename U>
using Multiply = typename MultiplyT<T, U>::Type;

*通过使用MultiplyT，下面的表达式产生所有质数的乘积结果

Accumulate<Primes, MultiplyT, CTValue<int, 1>>::value

不幸的是，这个对Typelist和CTValue的使用十分冗长，尤其是对于所有值类型相同的情况。通过引入一个别名模板CTTypelist能优化这种情况，它提供一个描述为CTValues的Typelist的统一的值列表

// typelist/cttypelist.hpp
template<typename T, T... Values>
using CTTypelist = Typelist<CTValue<T, Values>...>;

现在使用CTTypelist可以写出一个更简单的Primes的等价定义

using Primes = CTTypelist<int, 2, 3, 5, 7, 11>;

这个方法唯一的缺点是，别名模板只是别名，出现错误信息还是打印下层的CTValueType的Typelist，而这可能造成更冗长的问题。为了解决这个问题，可以创建一个全新的typelist类Valuelist来直接存储值

// typelist/valuelist.hpp

template<typename T, T... Values>
struct Valuelist {
};

template<typename T, T... Values>
struct IsEmpty<Valuelist<T, Values...>> {
    static constexpr bool value = sizeof...(Values) == 0;
};

template<typename T, T Head, T... Tail>
struct FrontT<Valuelist<T, Head, Tail...>> {
    using Type = CTValue<T, Head>;
    static constexpr T value = Head;
};

template<typename T, T Head, T... Tail>
    struct PopFrontT<Valuelist<T, Head, Tail...>> {
    using Type = Valuelist<T, Tail...>;
};

template<typename T, T... Values, T New>
struct PushFrontT<Valuelist<T, Values...>, CTValue<T, New>> {
    using Type = Valuelist<T, New, Values...>;
};

template<typename T, T... Values, T New>
struct PushBackT<Valuelist<T, Values...>, CTValue<T, New>> {
    using Type = Valuelist<T, Values..., New>;
};

通过提供IsEmpty，FrontT，PopFrontT和PushFrontT，使得Valuelist成为能更合适地用于算法的typelist。PushBackT提供为一个减少编译期操作开销的算法特化。比如Valuelist用于之前的定义InsertionSort

// typelist/valuelisttest.hpp

template<typename T, typename U>
struct GreaterThanT;

template<typename T, T First, T Second>
struct GreaterThanT<CTValue<T, First>, CTValue<T, Second>> {
    static constexpr bool value = First > Second;
};

void valuelisttest()
{
    using Integers = Valuelist<int, 6, 2, 4, 9, 5, 2, 1, 7>;
    using SortedIntegers = InsertionSort<Integers, GreaterThanT>;
    static_assert(std::is_same_v<SortedIntegers,
    Valuelist<int, 9, 7, 6, 5, 4, 2, 2, 1>>, "insertion sort failed");
}

注意可以提供使用字面值操作符初始化CTValue的能力，具体细节见Tuple Subscript（Tuple下标）

auto a = 42_c; // initializes a as CTValue<int,42>

可推断的非类型参数

C++17中，CTValue能通过使用单个可推断的非类型参数改进

// typelist/ctvalue17.hpp

template<auto Value>
struct CTValue
{
    static constexpr auto value = Value;
};

这就省去了对每个CTValue的使用指定特定类型的需要

using Primes = Typelist<CTValue<2>, CTValue<3>, CTValue<5>,
    CTValue<7>, CTValue<11>>;

这也能用于C++17的Valuelist，但结果不一定更好。一个带可推断类型的非类型参数包允许每个实参类型不同

template<auto... Values>
class Valuelist { };
int x;
using MyValueList = Valuelist<1,'a', true, &x>;

但这样混杂的值列表可能是有用的，它不同于之前的Valuelist要求所有元素有相同类型

使用包扩展来优化算法

Transform算法就自然地使得本身使用包扩展，因为它对每个列表中的元素进行了相同的操作，这允许了一个对Typelist的Transform的算法特化

// typelist/variadictransform.hpp

template<typename... Elements, template<typename T> class MetaFun>
class TransformT<Typelist<Elements...>, MetaFun, false>
{
public:
    using Type = Typelist<typename MetaFun<Elements>::Type...>;
};

这个实现捕获了typelist元素到参数包Elements中，随后采用了一个模式为typename MetaFun<Elements>::Type的包扩展以应用元函数到Elements中的每个类型，并从结果构建一个typelist。这种实现可以说更简单，因为它不需要递归，并且十分直接地使用语言特性。此外，它需要更少的模板实例化，因为只有一个Transform模板需要实例化。算法仍然要求线性数量的MeraFun实例化，但那些实例化对算法来说是基本的
其他算法间接受益于使用包扩展。比如Reverse算法需要一个线性数量的PushBack的实例化，使用Typelist上的PushBack的包扩展构建，Reverse是线性的。而更通用的Reverse的递归实现本身是线性实例化的，这使得Reverse是二次的
包扩展也可以用于选择给定索引列表中的元素以生成新的typelist。Selecty元函数使用一个typelist和一个包含typelist索引的Valuelist，生成一个新的typelist

// typelist/select.hpp

template<typename Types, typename Indices>
class SelectT;

template<typename Types, unsigned... Indices>
class SelectT<Types, Valuelist<unsigned, Indices...>>
{
public:
    using Type = Typelist<NthElement<Types, Indices>...>;
};

template<typename Types, typename Indices>
using Select = typename SelectT<Types, Indices>::Type;

索引被捕获在参数包Indices中，它扩展为生成一个给定typelist索引的NthElement类型序列，并将结果捕获在一个新的Typelist中。下面使用Select翻转typelist

using SignedIntegralTypes =
    Typelist<signed char, short, int, long, long long>;

using ReversedSignedIntegralTypes =
    Select<SignedIntegralTypes, Valuelist<unsigned, 4, 3, 2, 1, 0>>;
    // produces Typelist<long long, long, int, short, signed char>

一个包含另一个列表索引的非类型typelist通常称为索引表（index list或index sequence）

Cons-style Typelist

在引入可变参数模板之前，typelist常用于使用一个递归的LISP的cons单元建模后的数据结构的构建。每个cons单元包含一个值（列表的头）和一个嵌套列表，后者可以是另一个cons单元或空列表nil。这个概念可以直接用C++来表达

// typelist/cons.hpp
class Nil { };
template<typename HeadT, typename TailT = Nil>
class Cons {
public:
    using Head = HeadT;
    using Tail = TailT;
};

一个空的typelist写为Nil，一个包含单独的int元素的typelist写为Cons<int, Nil>，或Cons<int>，更长的列表需要嵌套

using TwoShort = Cons<short, Cons<unsigned short>>;

任意长typelist能通过深度递归嵌套构造，尽管手写出这样的长列表十分笨拙

using SignedIntegralTypes = Cons<signed char, Cons<short, Cons<int,
    Cons<long, Cons<long long, Nil>>>>>;

提取cons-style列表中第一个元素，直接指向列表的头

// typelist/consfront.hpp

template<typename List>
class FrontT {
public:
    using Type = typename List::Head;
};

template<typename List>
using Front = typename FrontT<List>::Type;

添加一个元素到前面来包裹现有列表中的另一个Cons

// typelist/conspushfront.hpp

template<typename List, typename Element>
class PushFrontT {
public:
    using Type = Cons<Element, List>;
};

template<typename List, typename Element>
using PushFront = typename PushFrontT<List, Element>::Type;

最后，从一个递归的typelist移除首个元素提取列表的尾部

// typelist/conspopfront.hpp

template<typename List>
class PopFrontT {
public:
    using Type = typename List::Tail;
};

template<typename List>
using PopFront = typename PopFrontT<List>::Type;

一个对Nil的IsEmpty特化完成一系列核心的typelist操作

// typelist/consisempty.hpp
template<typename List>
struct IsEmpty {
    static constexpr bool value = false;
};

template<>
struct IsEmpty<Nil> {
    static constexpr bool value = true;
};

通过这些typelist操作，现在可以对cons-style列表使用InsertionSort算法

// typelist/conslisttest.hpp
template<typename T, typename U>
struct SmallerThanT {
    static constexpr bool value = sizeof(T) < sizeof(U);
};

void conslisttest()
{
    using ConsList = Cons<int, Cons<char, Cons<short, Cons<double>>>>;
    using SortedTypes = InsertionSort<ConsList, SmallerThanT>;
    using Expected = Cons<char, Cons<short, Cons<int, Cons<double>>>>;
    std::cout << std::is_same<SortedTypes, Expected>::value << '\n';
}

【C++ Templates（22）】Typelist

Typelist解析

Typelist算法

索引

找到最佳匹配

添加Typelist

翻转Typelist

转换Typelist

累加Typelist

插入排序

非类型Typelist

可推断的非类型参数

使用包扩展来优化算法

Cons-style Typelist

猜你喜欢

热点阅读