第3章：Typelists

为什么需要 Typelists：The Need for Typelists

普通 container 保存“同一种元素类型的多个值”；generic component 常需要保存“多个不同类型本身”。Functor 要记录参数签名，Abstract Factory 要记录 product family，multimethod dispatcher 要记录参与类型。The Need for Typelists 就是把这组类型变成编译器可遍历、查询和改写的数据结构。

Typelist 不创建对象，不保存 bytes，也不能在运行时 push_back。它的输出通常是另一个类型、一个 integral constant，或由类型序列生成的一套 class hierarchy。今天常用 parameter pack 表示同一概念，但“把类型当数据”的模型没有改变。

Defining Typelists

Defining Typelists 使用二元节点：Head 保存当前类型，Tail 指向余下 Typelist；NullType 是终点。这个结构故意模仿 singly linked list，使模板 specialization 能写出递归算法。

struct NullType {};
 
template<class H, class T>
struct Typelist {
    using Head = H;
    using Tail = T;
};
 
using UiTypes = Typelist<Button,
                Typelist<Window,
                Typelist<Dialog, NullType>>>;

NullType 必须与真实 element type 区分；若业务列表本身可能包含 NullType，termination 语义就含混。现代 parameter pack 通过空包 specialization 终止，不再需要 sentinel，但仍必须明确 empty sequence 的结果。

Linearizing Typelist Creation

嵌套写法随着长度增长很难读。Linearizing Typelist Creation 在书中通过 TYPELIST_1 到 TYPELIST_N 宏把线性参数展开为嵌套节点。宏是当时缺少 variadic templates 的工程折衷：它不能检查类型数量以外的语义，且上限固定。

现代写法可直接定义 template<class... Ts> struct TypeList {};，或用 alias 将 parameter pack 转为旧 Head/Tail 结构。迁移时不要只替换语法：若后续算法依赖 Head/Tail，需要一起改为 pack specialization 或提供兼容 adapter。

Calculating Length 与 Indexed Access

Calculating Length 是最小递归例子：普通节点的长度为 1 + Length<Tail>，NullType 特化返回 0。值在编译期产生，不需要任何 object。

template<class List> struct Length;
 
template<class H, class T>
struct Length<Typelist<H, T>> {
    static constexpr std::size_t value = 1 + Length<T>::value;
};
 
template<>
struct Length<NullType> {
    static constexpr std::size_t value = 0;
};

Indexed Access 的 TypeAt<List, i> 在 i == 0 返回 Head，否则转成 TypeAt<Tail, i - 1>。越界时没有匹配特化，形成编译错误；TypeAtNonStrict 则可在越界时返回 caller-supplied default。两种 contract 都合理，但必须由 API 名和诊断明确。

Searching Typelists

Searching Typelists 的 IndexOf<List,T> 比较当前 Head：相同返回 0；否则递归查询 Tail，找到则加 1，未找到返回 -1。这里的难点是不能对 -1 继续加 1，否则“未找到”会变成合法位置。

IndexOf 的 equality 是 exact type equality；const Widget、Widget& 与 Widget 不同。若业务想按 normalized type 搜索，应在入口明确 remove_cvref，而不是悄悄改变所有 typelist 算法的语义。

Appending to Typelists

Appending to Typelists 不修改原列表，而是产生新类型。Append<NullType, X> 形成一个节点；Append<Typelist<H,T>, X> 保留 H，并递归 append 到 T。若 X 本身是 Typelist，可以 splice 整条序列，contract 需区分“添加一个 element type”和“连接两个 lists”。

Erasing a Type from a Typelist

Erasing a Type from a Typelist 在第一个 matching Head 处返回 Tail，其余层重建原 Head。EraseAll 则匹配时继续递归，不匹配时保留节点。两个函数只差一处递归选择，却表达完全不同的 duplicate contract。

template<class List, class T> struct Erase;
template<class T> struct Erase<NullType, T> { using Result = NullType; };
 
template<class T, class Tail>
struct Erase<Typelist<T, Tail>, T> { using Result = Tail; };
 
template<class Head, class Tail, class T>
struct Erase<Typelist<Head, Tail>, T> {
    using Result = Typelist<Head, typename Erase<Tail, T>::Result>;
};

Erasing Duplicates 与 Replacing an Element

Erasing Duplicates（NoDuplicates）先去重 Tail，再从结果中删掉当前 Head 的后续副本，最后把 Head 接回；因此保留第一次出现顺序。若先删 Head 再递归，可能改变 survivor choice。元算法的顺序就是语义，不只是实现细节。

Replacing an Element in a Typelist 与 Erase 类似：遇到第一个 old type 时用 new type 构造节点并停止，ReplaceAll 则继续。替换后可能产生 duplicate，是否再运行 NoDuplicates 由 caller contract 决定，不能在 Replace 内隐式做。

Partially Ordering Typelists

当列表同时含 Base 与 Derived，dispatcher 通常要先尝试更具体的 Derived。Partially Ordering Typelists 根据 inheritance relation 交换次序，使 derived classes 出现在 bases 之前；互不相关类型保持某种稳定顺序。

这不是全序：两个 sibling 没有自然先后。算法若依赖 input order 保持稳定，应写测试；ambiguous/private inheritance 与 conversion operator 也不能简单等同 public base relation。现代实现使用 std::is_base_of 加明确 accessibility contract。

Class Generation with Typelists

Class Generation with Typelists 把列表的每个类型映射成一个 Unit<T>，再按结构组合。scatter hierarchy 让生成类同时继承 Unit<T1>、Unit<T2>...；每种 T 对应一个 sibling base，适合 heterogeneous tuple 和“每类型一个字段”。

当列表重复同一类型，两个 Unit<T> base 会歧义。Loki 通过 indexed wrapper 或不同中间类型区分位置；访问 tuple field 也要决定按 type 还是按 index。按 type 访问在 duplicate 存在时天然不唯一。

tuple class 在书中由 scatter hierarchy 生成 storage，再提供 Field<T>/Field<i> 访问。它展示“类型列表是 schema，hierarchy 是 materialized representation”：列表顺序、duplicate 与 Unit layout 都影响最终 object。

linear hierarchy 则生成 Unit<T1, Unit<T2, Unit<T3, Root>>> 的链，每个 Unit 只连接下一个，适合 ordered handlers、chain of responsibility 或逐层 policy decoration。

先预测：Typelist<Base, Derived> 直接生成 dispatcher 时，若先测试 Base，Derived object 也会命中 Base 分支，具体处理器永远不可达。先做 inheritance partial order 不只是优化，而是 correctness requirement。

小结

• Typelist 满足对有序异构类型集合的编译期表示需求，Head/Tail/NullType 给出递归数据结构
• 线性化宏只改善书写，现代 parameter pack 改善表达；两者都需要明确 empty 与 bounds contract
• Length、TypeAt、IndexOf 将链表算法搬到模板实例化，推进分支和终止特化同等重要
• Append、Erase、NoDuplicates、Replace 产生新类型，执行顺序决定 duplicate 与 survivor 语义
• inheritance partial order 把 Derived 放在 Base 前，是类型 dispatcher 的 correctness 基础
• scatter hierarchy 生成并列 Unit，适合 tuple；linear hierarchy 生成有序链，适合 handler pipeline
• 运行时零分派不代表免费：编译时间、code size、layout、歧义和 ABI 都是设计成本

名词解释