CPP-Templates-2nd--第 24 章 类型列表（Typelists）

 

目录

24.1 类型列表剖析（Anatomy of a Typelist） 

24.2 类型列表的算法

24.2.1 索引（Indexing)

24.2.2 寻找最佳匹配

24.2.3 向类型类表中追加元素

24.2.4 类型列表的反转

24.2.5 类型列表的转换

24.2.6 类型列表的累加（Accumulating Typelists）

24.2.7 插入排序

24.3 非类型类型列表（Nontype Typelists）

24.3.1 可推断的非类型参数

24.4 对包扩展相关算法的优化（Optimizing Algorithms with Pack Expansions ）

24.5 Cons-style Typelists（不完美的类型列表？）

---

参考：GitHub - Walton1128/CPP-Templates-2nd--: 《C++ Templates 第二版》中文翻译，和原书排版一致，第一部分（1至11章）以及第18，19，20，21、22、23、24、25章已完成，其余内容逐步更新中。 个人爱好，发现错误请指正

高效的编程通常需要用到各种各样的数据结构，元编程也不例外。对于类型元编程，核心的 数据结构是 typelist，和其名字的意思一样，它指的是一个包含了类型的列表。模板元编程 可以操作 typelist 并最终生成可执行程序的一部分。

24.1 类型列表剖析（Anatomy of a Typelist） 

类型列表指的是一种代表了一组类型，并且可以被模板元编程操作的类型。它提供了典型的 列表操作方法：遍历列表中的元素，添加元素或者删除元素。但是类型列表和大多数运行期 间的数据结构都不同（比如 std::list），它的值不允许被修改。向类型列表中添加一个元素 并不会修改原始的类型列表，只是会创建一个新的、包含了原始类型列表和新添加元素的类 型列表。

类型列表通常是按照类模板特例的形式实现的，它将自身的内容（包含在模板参数中的类型 以及类型之间的顺序）编码到了参数包中。一种将其内容编码到参数包中的类型列表的直接 实现方式如下：

template<typename… Elements>
class Typelist
{};

下面是一个包含了所有有符号整型的类型列 表：

using SignedIntegralTypes =
Typelist<signed char, short, int, 

 操作这个类型列表需要将其拆分，通常的做法是将第一个元素（the head）从剩余的元素中 分离（the tail）。比如 Front 元函数会从类型列表中提取第一个元素：

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

同样 PopFront 元函数会 删除类型列表中的第一个元素。在实现上它会将类型列表中的元素分为头（head）和尾（tail） 两部分，然后用尾部的元素创建一个新的 Typelist 特例。

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

PopFront会产生如下类型列表：

Typelist<short, int, long, long long>

同样也可以向类型列表中添加元素，只需要将所有已经存在的元素捕获到一个参数包中，然 后在创建一个包含了所有元素的 TypeList 特例就行：

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

和预期的一样，

PushFrontbool>

会生成：

Typelist<bool, signed char, short, int, long, long>

24.2 类型列表的算法

基础的类型列表操作Front，PopFront和PushFront可以被组合起来实现更有意思的列表操作。 比如通过将 PushFront 作用于 PopFront 可以实现对第一个元素的替换：

using Type = PushFront, bool>;

更近一步，我们可以按照模板原函数的实现方式，实现作用于类型列表的诸如搜索、转换和 反转等操作。

24.2.1 索引（Indexing)

接下来我们将这一操作推广到可以提取第 N th个元素。比如，为了提 取给定类型列表中的第 2 个元素，可以这样： 

NthElement 操作的实现方式是使用一个递归的元 程序遍历

// recursive case:
template<typename List, unsigned N>
class NthElementT : public NthElementT, N-1>
{};
// basis case:
template<typename List>
class NthElementT0> : public FrontT
{ };
template<typename List, unsigned N>
using NthElement = typename NthElementT::Type;

24.2.2 寻找最佳匹配

有些类型列表算法会去查找类型列表中的数据。例如可能想要找出类型列表中最大的类型 （比如为了开辟一段可以存储类型列表中任意类型的内存）。这同样可以通过递归模板元程 序实现：

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

注意上文中的基本情况显式的用到了空的类型列表 Typelist<>。这样有点不太好，因为它 可能会妨碍到其它类型的类型列表（我们会在第 24.3 节和第 24.5 节中讲到这一类类型列表） 的使用。为了解决这一问题，引入了 IsEmpty 元函数，它可以被用来判断一个类型列表是否 为空：

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

结合 IsEmpty，可以像下面这样将 LargestType 实现成适用于任意支持了 Front，PopFront 和 IsEmpty 的类型：

template<typename List, bool Empty = IsEmpty::value>
class LargestTypeT;
// recursive case:
template<typename List>
class LargestTypeTfalse>
{
private:
using Contender = Front;
using Best = typename LargestTypeT>::Type;
public:
using Type = IfThenElse<(sizeof(Contender) >=
sizeof(Best)),Contender, Best>;
};
// basis case:
template<typename List>
class LargestTypeTtrue>
{
public:
using Type = char;
};
template<typename List>
using LargestType = typename LargestTypeT::Type;

24.2.3 向类型类表中追加元素

通过 PushFront 可以向类型列表的头部添加一个元素，并产生一个新的类型列表。除此之外 我们还希望能够像在程序运行期间操作 std::list 和 std::vector 那样，向列表的末尾追加一个 元素。对于我们的 Typelist 模板，为实现支持这一功能的 PushBack，只需要对 24.1 节中的 PushFront 做一点小的修改：

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

不过和实现 LargestType 的算法一样，可以只用 Front，PushFront，PopFront 和 IsEmpty 等基 础操作实现一个更通用的 PushBack 算法：

template<typename List, typename NewElement, bool =
IsEmpty::value>
class PushBackRecT;
// recursive case:
template<typename List, typename NewElement>
class PushBackRecTfalse>
{
using Head = Front;
using Tail = PopFront;
using NewTail = typename PushBackRecT::Type;
public:
using Type = PushFront;
};
// basis case:
template<typename List, typename NewElement>
class PushBackRecTtrue>
{
public:
using Type = PushFront;
};
// generic push-back operation:
template<typename List, typename NewElement>
class PushBackT : public PushBackRecT { };
template<typename List, typename NewElement>
using PushBack = typename PushBackT

对于比较大的模板元程序，编译时间可能会是一个问题，因此有必要设法去降低算法所需要 的模板实例的数目。事实上，第一版 PushBack 的实现（用 Typelist 进行了部分特例化）只需 要固定数量的模板实例化，这使得它要比通用版本的实现（在编译期）更高效。而且，由于 它被描述成 PushBackT 的一种偏特化，在对一个 Typelist 执行 PushBack 的时候这一高效的实 现会被自动选择，从而为模板元程序引入了“算法特化”的概念（参见 20.1 节）。该章节 中介绍的很多技术都可以被模板元程序用来降低算法所需模板实例的数量。

24.2.4 类型列表的反转

当类型列表的元素之间有某种顺序的时候，对于某些算法而言，如果能够反转该顺序的话， 事情将会变得很方便。

template<typename List, bool Empty = IsEmpty::value>
class ReverseT;
template<typename List>
using Reverse = typename ReverseT::Type;
// recursive case:
template<typename List>
class ReverseTfalse>:public PushBackT>,
Front> { };
// basis case:
template<typename List>
class ReverseTtrue>{
public:
using Type = List;
};

24.2.5 类型列表的转换

之前介绍的类型列表的相关算法允许我们从类型列表中提取任意元素，在类型列表中做查 找，构建新的列表以及反转列表。

但是我们还需要对类型列表中的元素执行一些其它的操作。 比如可能希望对类型列表中的所有元素做某种转换，例如通过 AddConst 给列表中的元素加 上 const 修饰符：

template<typename T>
struct AddConstT
{
using Type = T const;
};
template<typename T>
using AddConst = typename AddConstT::Type;
 
template<typename List, template<typename T> class MetaFun, bool Empty
= IsEmpty::value>
class TransformT;
// recursive case:
template<typename List, template<typename T> class MetaFun>
class TransformTfalse>
: public PushFrontT<typename TransformT,
MetaFun>::Type, typename MetaFun>::Type>
{};
// basis case:
template<typename List, template<typename T> class MetaFun>
class TransformTtrue>
{
public:
using Type = List;
};
template<typename List, template<typename T> class MetaFun>
using Transform = typename TransformT::Type;

24.2.6 类型列表的累加（Accumulating Typelists）

转换（Transform）算法在需要对类型列表中的元素做转换时很有帮助。通常将它和累加 （Accumulate）算法一起使用，它会将类型列表中的所有元素组合成一个值。

Accumulate 算 法以一个包含元素 T1，T2，...，TN的类型列表 T，一个初始类型 I，和一个接受两个类型作 为参数的元函数 F 为参数，并最终返回一个类型。它的返回值是 F (F (F (…F(I, T1), T2), …, TN−1), TN )，其中在第 i th步，F 将作用于前 i-1 步的结果以及 Ti。

取决于具体的类型列表，F 的选择以及初始值 I 的选择，可以通过 Accumulate 产生各种不 同的输出。比如如果 F 可以被用来在两种类型中选择较大的那一个，Accumulate 的行为就和 LargestType 差不多。而如果 F 接受一个类型列表和一个类型作为参数，并且将类型追加到类 型列表的后面，其行为又和 Reverse 算法差不多。

Accumulate 的实现方式遵循了标准的递归元编程模式：

template<typename List,
template<typename X, typename Y> class F,
typename I,
bool = IsEmpty::value>
class AccumulateT;
// recursive case:
template<typename List,
template<typename X, typename Y> class F,
typename I>
class AccumulateTfalse>
: public AccumulateT, F,
typename F>::Type>
{};
// basis case:
template<typename List,
template<typename X, typename Y> class F,
typename I>
class AccumulateTtrue>
{
public:
using Type = I;
};
template<typename List,
template<typename X, typename Y> class F,
typename I>
using Accumulate = typename AccumulateT::Type

24.2.7 插入排序

24.3 非类型类型列表（Nontype Typelists）

通过类型列表，有非常多的算法和操作可以用来描述并操作一串类型。某些情况下，还会希 望能够操作一串编译期数值，比如多维数组的边界，或者指向另一个类型列表中的索引。

有很多种方法可以用来生成一个包含编译期数值的类型列表。一个简单的办法是定义一个类 模板 CTValue（compile time value），然后用它表示类型列表中某种类型的值：

template<typename T, T Value>
struct CTValue
{
static constexpr T value = Value;
};

定义 一个能够直接存储数值的、全新的类型列表类 Valuelist：

template<typename T, T… Values>
struct Valuelist {
};
template<typename T, T… Values>
struct IsEmpty> {
static constexpr bool value = sizeof…(Values) == 0;
};
template<typename T, T Head, T… Tail>
struct FrontT> {
using Type = CTValue;
static constexpr T value = Head;
};
template<typename T, T Head, T… Tail>
struct PopFrontT> {
using Type = Valuelist;
};
template<typename T, T… Values, T New>
struct PushFrontT, CTValue> {
using Type = Valuelist;
};
template<typename T, T… Values, T New>
struct PushBackT, CTValue> {
using Type = Valuelist;
};

通过代码中提供的 IsEmpty，FrontT，PopFrontT 和 PushFrontT，Valuelist 就可以被用于本章 中介绍的各种算法了。PushBackT 被实现为一种算法的特例化，这样做可以降低编译期间该 操作的计算成本。比如 Valuelist 可以被用于前面定义的算法 InsertionSort：

template<typename T, typename U>
struct GreaterThanT;
template<typename T, T First, T Second>
struct GreaterThanT, CTValue> {
static constexpr bool value = First > Second;
};
void valuelisttest()
{
using Integers = Valuelist<int, 6, 2, 4, 9, 5, 2, 1, 7>;
using SortedIntegers = InsertionSort;
static_assert(std::is_same_vint, 9, 7,
6, 5, 4, 2, 2, 1>>, "insertion sort failed");
}

24.3.1 可推断的非类型参数

在 C++17 中，可以通过使用一个可推断的非类型参数（结合 auto）来进一步优化 CTValue 的 实现：

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

这样在使用 CTValue 的时候就可以不用每次都去指定一个类型了，从而简化了使用方式：

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

在 C++17 中也可以对 Valuelist 执行同样的操作，但是结果可能不一定会变得更好。正如在第 15.10.1 节提到的那样，对一个非类型参数包进行类型推断时，各个参数可以不同：

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

虽然这样一个列表可能也很有用，但是它和之前要求元素类型必须相同的 Valuelist 已经不一 样了。虽然我们也可以要求其所有元素的类型必须相同（参见 15.10.1 节的讨论），但是对 于一个空的。

24.4 对包扩展相关算法的优化（Optimizing Algorithms with Pack Expansions ）

也可以基于索引值从一个已有列表中选择一些元素，并生成新的列表。Select 元函数接受一 个类型列表和一个存储索引值的 Valuelist 作为参数，并最终生成一个包含了被索引元素的新 的类型列表：

template<typename Types, typename Indices>
class SelectT;
template<typename Types, unsigned… Indices>
class SelectTunsigned, Indices…>>
{
public:
using Type = Typelist…>;
};
template<typename Types, typename Indices>
using Select = typename SelectT::Type;

24.5 Cons-style Typelists（不完美的类型列表？）