从 List 源码理解 allocator、迭代器与类型转换

阅读 stl1weekend 的 List.hpp 时，链表的四处写法值得展开：为什么要把元素分配器重新绑定到节点类型；为什么 push 使用两个重载；为什么常量迭代器的 value_type 仍然是 T；以及为什么节点访问使用 static_cast。这里以源码的 C++20 写法为准。已有的 Vector 笔记介绍了 allocator 的基本职责，本文重点看链表引入的节点类型。

allocator_traits 和节点分配器

为什么分配 T 的 allocator 不够

List 的公开类型参数是元素类型 T 和元素分配器 Alloc：

template <class T, class Alloc = std::allocator<T>>
struct List;

但链表在内存中需要的不只是一个 T，还需要前后指针。源码将它们组合成节点：

template <class T>
struct ListBaseNode {
    ListBaseNode* m_next;
    ListBaseNode* m_prev;
};
 
template <class T>
struct ListValueNode : ListBaseNode<T> {
    union { T m_value; };
};

这是简化摘录。ListValueNode<T> 包含链表指针和元素所需的存储，其大小、对齐要求可能与 T 不同。因此，不能假定为一个 T 分配的空间足以容纳一个节点。容器需要一个同一分配器家族中、面向节点类型的分配器。

如果用户使用默认分配器，所需的类型关系直观上是：

std::allocator<int>  →  std::allocator<ListValueNode<int>>

自定义 allocator 不一定叫 std::allocator，也可能携带内存池等状态。容器需要一种通用方式取得对应的节点分配器，而不是把它硬编码为 std::allocator<ListValueNode<T>>。

traits 提供统一入口

std::allocator_traits<A> 是针对分配器类型 A 的适配层。它提供统一的关联类型与操作，并为部分可选成员提供默认规则。例如，容器可以通过 allocator_traits<A>::allocate(a, n) 调用分配操作；也可以通过 traits 查询指针类型或取得面向其他类型的分配器。

traits 本身不是那个内存池，也不是 A 的实例。以源码为例，Alloc 是类型，m_alloc 才是保存的分配器对象。traits 接收分配器对象并协调操作。

对部分 allocator，traits 可以推导省略的类型；更特殊的 allocator 则可提供相应成员定制。这是 traits 的价值：泛型容器面对不同 allocator，使用同一个入口，而不需要要求每个 allocator 都把所有可推导成员写一遍。

为什么需要这一层

根据标准草案的 allocator 要求，allocator 封装分配模型的信息；某项类型或表达式有规定的默认值时，allocator 可以省略该项，再由标准库的 allocator_traits 补齐。这样既能让简单 allocator 只提供必要的接口，也允许使用特殊指针或自定义构造行为的 allocator 提供自己的实现。容器的作者因此可以统一查询 traits，而不必在每个容器里重复检测各个可选成员。

例如，一个典型的简单 MyAlloc<T> 提供 value_type、allocate、deallocate，以及 allocator 要求的构造、转换和比较等操作，但不必再手写 pointer 和 rebind：traits 在满足默认规则时分别得到 T* 和 MyAlloc<U>。这不是说仅实现三个成员就一定是完整合格的 allocator：复制、相等性及重绑定后的类型关系等要求仍须满足。草案还给出了最小接口的示例。

traits 具体提供什么

下面按标准草案的成员类型和静态成员函数归纳常用接口。表中的“默认”只适用于对应的可选成员缺失或表达式不成立时；value_type、基础分配操作等不能都靠 traits 凭空生成。

类别	接口	提供的行为
类型信息	`value_type`	使用 `Alloc::value_type`；它说明 allocator 面向的类型。
指针	`pointer`、`const_pointer`、`void_pointer`、`const_void_pointer`	优先使用 allocator 提供的对应类型。`pointer` 缺省为 `value_type*`；其余指针缺省时通过 `pointer_traits<pointer>::rebind` 得到，从而允许合规的自定义指针类型。
大小与差值	`size_type`、`difference_type`	优先使用 allocator 的定义；否则差值类型来自 `pointer_traits<pointer>`，大小类型为对应的无符号类型。
重新绑定	`rebind_alloc<U>`、`rebind_traits<U>`	前者取得面向 `U` 的分配器类型，后者是该类型的 `allocator_traits`；下一节结合链表节点展开。
分配与释放	`allocate`、`deallocate`	普通形式分别调用 `a.allocate(n)` 和 `a.deallocate(p, n)`；带提示的 `allocate` 在相应重载不可用时退回 `a.allocate(n)`。
元素构造与销毁	`construct`、`destroy`	若 allocator 提供的对应调用有效就使用它；否则在当前草案中分别使用 `construct_at` 和 `destroy_at`。
容量上限	`max_size`	可调用 `a.max_size()`；缺省为 `numeric_limits<size_type>::max() / sizeof(value_type)`。
容器操作策略	`propagate_on_container_copy_assignment`、`propagate_on_container_move_assignment`、`propagate_on_container_swap`、`is_always_equal`	向容器提供 allocator 传播和相等性信息。前三者缺省为 `false_type`；`is_always_equal` 缺省为 `is_empty<Alloc>::type`。
拷贝构造时选择	`select_on_container_copy_construction`	若 allocator 提供相应成员则调用它，否则返回源 allocator 的副本。

以构造函数为例，下面是便于理解的示意代码，不是标准库实现：

// C++20 示意：省略约束和标准库实现细节
template<class A, class T, class... Args>
void traits_construct(A& a, T* p, Args&&... args) {
    if constexpr (requires { a.construct(p, std::forward<Args>(args)...); })
        a.construct(p, std::forward<Args>(args)...);
    else
        std::construct_at(p, std::forward<Args>(args)...);
}

同一个 traits::construct 调用因而既能使用 allocator 的定制，也能在没有定制时使用通用构造方式。List.hpp 实际上直接使用 construct_at，所以不会走这个定制入口；它只在节点分配和释放处使用了 traits。

传播策略解决的问题是：如果两个容器持有指向不同内存资源的有状态 allocator，容器赋值或交换时，是否也应传播 allocator？例如移动赋值时，若允许传播，目标容器可以按相应规则取得源 allocator；若不传播且两个 allocator 不相等，就不能仅假定目标原有 allocator 可以释放源节点。标志提供决策所需的信息，traits 本身不会替容器执行传播，也不会自动修复错误的内存归属。拷贝构造选择函数与拷贝赋值传播标志分别处理不同操作。

草案还列出 allocate_at_least：这是 C++23 加入的接口，允许返回至少请求数量的存储；未提供专门实现时回退到 {a.allocate(n), n}。本文的 List.hpp 使用 C++20 风格，且只调用普通 allocate。草案是持续更新的工作草案，查阅时要区分版本。

rebind_alloc 的类型和对象

源码先计算节点分配器的类型：

using AllocNode = typename std::allocator_traits<Alloc>
    ::template rebind_alloc<ListValueNode<T>>;

再在分配节点时，用保存的元素分配器创建节点分配器对象：

AllocNode allocNode{m_alloc};
return std::allocator_traits<AllocNode>::allocate(allocNode, 1);

以 List<int> 的默认类型为例：

using Alloc = std::allocator<int>;
using AllocNode = std::allocator_traits<Alloc>
    ::rebind_alloc<ListValueNode<int>>;
// AllocNode 为 std::allocator<ListValueNode<int>>

rebind_alloc<U> 只产生类型，不分配内存，也不自动创建或复制任何对象。接下来的 AllocNode allocNode{m_alloc} 才从已有分配器构造出对应类型的对象；有状态 allocator 的跨类型转换应按分配器要求保留相应的资源关系，使分配和释放可以正确配对。它并不意味着任意两个同类型 allocator 都能互相释放对方的内存。

traits 如何找到这个类型？概念上，它优先使用分配器自己提供的 rebind<U>::other；对于符合相应形式的类模板分配器，若未提供该成员，则可以将首个类型参数替换为 U，保留其余类型参数。例如 MyAlloc<T, Policy> 可按规则得到 MyAlloc<U, Policy>。不符合默认形式的自定义 allocator 则需要提供合适的 rebind。

表达式中的两个关键字也各有作用：

typename 表明依赖模板参数的整个限定名表示类型。
template 表明依赖类型中的 rebind_alloc 是成员模板，使后面的 <...> 能按模板实参解析。

这里 ::allocate(allocNode, 1) 的 1 表示分配一个节点类型的单位，不是一个字节，也不是一个 T。

源码支持 allocator 的范围

这份教学实现演示了重绑定，但不应据此认为它完整支持所有标准 allocator：节点指针在实现中固定为普通指针；元素构造和销毁直接调用 construct_at / destroy_at，绕过 traits 可提供的构造与销毁定制。移动等操作也需要仔细处理有状态分配器的传播与相等性，确保最终使用兼容的分配器释放节点。

List 的 union 与 Vector 的元素存储

ListValueNode<T> 在节点里声明了一个匿名 union，其中只有一个成员 T m_value。虽然 union 常用于让不同成员共享存储，这里只有一个候选成员，重点是允许节点中预留元素的位置，而由容器单独决定何时开始和结束元素的生命周期。

根据草案中的 union 规则，只有生命周期已经开始且尚未结束的 union 成员才是活跃成员；一个 union 可以暂时没有活跃成员。匿名 union 的成员名可以在外层类作用域中使用，所以源码可以写 node.m_value，无需再经过一个有名字的 union 成员。

对比普通成员 T m_value;：在通常的节点构造和析构过程中，普通成员会参与节点的初始化和销毁。而把 T 放在 union 中，可以设计节点的构造和析构，使节点就绪时 T 尚未构造，之后再单独构造 T。例如下面是解释机制的 C++20 示意，并非源码中的节点构造过程：

#include <memory>
#include <string>
 
struct Node {
    Node* next = nullptr;
    union { std::string value; };
 
    Node() {}   // 不初始化 union 的 value
    ~Node() {}  // 不自动销毁 value；调用者负责
};
 
Node node;  // 节点存在，value 尚未构造
std::construct_at(std::addressof(node.value), "hello");
// 此时 value 是活跃成员，可以使用 node.value
std::destroy_at(std::addressof(node.value));
// value 的生命周期结束，不再读取它

示例显式定义节点构造函数和析构函数，以支持 std::string 这样的非平凡类型；只有成功构造了 value 才能销毁它。示例也没有实现异常安全管理。不能从“声明了 union”推断成员必然处于未构造状态：实际初始化方式可能选择并构造某个成员，union 的特殊成员函数规则也会随 C++ 版本变化。

Vector 为什么没有 union

Vector 没有把每个元素嵌入一个带链表指针的节点；它保存 _Tp* _M_data，通过 _M_alloc.allocate(n) 取得可放置多个 _Tp 的连续存储，然后在需要的位置调用 std::construct_at。例如源码的 emplace_back 在 _M_data[_M_size] 处构造元素，clear 仅销毁前 _M_size 个元素。

以默认 std::allocator<T> 为例，草案规定 allocate(n) 开始数组对象的生命周期，但不开始各个数组元素的生命周期。因此，元素存储位置可以先存在，元素再逐个构造；[size, capacity) 对应尚未构造元素的预留位置。自定义 allocator 也必须满足适用的分配器要求。Vector 已有这种分配得到的元素存储，无需像这个 List 节点定义一样使用 union 表达一个可独立管理的成员。

	List 的元素节点	Vector 的元素区域
元素位置	每个节点包含链表链接和 union 中的元素位置	一块连续的、供多个 `T` 使用的存储
手动管理的原因	让节点内 `T` 的构造与节点其他部分分开	已分配的容量可能大于已构造的元素数
本实现中的构造	对节点中的 `m_value` 调用 `construct_at`	对 `_M_data` 的相应位置调用 `construct_at`

这说明两者都在手动管理元素，不意味着链表必须使用 union：也可以设计让节点构造函数直接构造普通的 T 成员，或采用其他满足对象生命周期与对齐要求的存储方式。选择取决于节点与元素需要如何构造、销毁，以及 allocator 接口如何参与。

对源码生命周期的注意事项

上面的 Node 示例显式创建了节点对象；List.hpp 的实际代码则由 newNode() 调用节点 allocator 的 allocate，没有显式调用节点构造函数，并在构造 T 前通过 node->value() 取得成员引用。C++20 的隐式对象创建规则有特定条件，也不会替所有非平凡子对象调用构造函数。单凭获得足够大小的存储、或者声明了 union，不能断言任意 T 下派生节点、基类和 union 子对象的生命周期都已经正确开始，也不能把构造前返回 T& 当成无需分析的通用写法。这里的 union 解释的是设计意图和可用机制，并不是对这份教学实现完整生命周期正确性的证明。

push 的拷贝与移动重载

源码为 push_back 写了两个入口，实际构造复用 emplace_back：

void push_back(T const& val) {
    emplace_back(val);
}
 
void push_back(T&& val) {
    emplace_back(std::move(val));
}
 
template <class... Args>
T& emplace_back(Args&&... args) {
    // 省略节点处理
    std::construct_at(&node->value(), std::forward<Args>(args)...);
    return node->value();
}

为什么保留两个 push 重载

两个重载表达的是稳定的容器接口：传入一个 T，根据左值或右值决定拷贝或移动；允许发生到 T 的隐式转换。emplace_back 则接受构造 T 所需的参数，在元素位置直接构造。

转发引用可以实现类似功能，但接口行为并不完全相同。例如对于 List<std::string>，push_back("hello") 的两个 T 重载先允许字符串字面量隐式转换为 std::string；转发引用版本则直接推导出字符数组引用，再把它转发给构造函数。对于只提供显式构造函数的类型，转发版本中的直接构造也可能接受原有 push 接口不接受的参数。没有约束的转发重载还可能匹配过多类型，并把错误推迟到函数体内部。

此外，两个具体的 T 重载可以为部分花括号实参提供已知目标类型；单独的 U&& 模板通常无法从裸花括号列表推导 U。因此这里的选择不只是避免重复：push 保持清晰的值插入接口，而需要直接传递构造参数时使用 emplace。

const_iterator 的 value_type 为什么是 T

源码中的两个迭代器都把 value_type 定义为 T，但访问类型不同：

// iterator
using value_type = T;
using pointer = T*;
using reference = T&;
 
// const_iterator
using value_type = T;
using pointer = T const*;
using reference = T const&;

value_type 描述迭代器所关联的值的类型；reference 和 operator* 的返回类型描述通过这个迭代器访问时得到什么。对 const_iterator 解引用得到 const T&，所以不能通过该引用修改元素；这不要求值类型本身定义为 const T。

例如一个泛型算法从只读迭代器读取并保存值，仍然希望得到一个普通的可修改副本：

using V = std::iterator_traits<decltype(it)>::value_type;
V copy = *it;  // 对 List<int>::const_iterator，V 是 int
copy = 42;     // 修改副本，不修改原容器
// *it = 42;   // 错误：解引用是 const int&

读取权限属于访问路径，const_iterator 本身仍可递增；这与 const iterator 是不同概念：后者是迭代器对象本身为常量，其解引用结果是否可写由迭代器类型决定。对标准迭代器约定而言，value_type 表示不带顶层 const 的值类型，而解引用类型可以携带 const、是引用，甚至在其他迭代器中是代理对象。

节点向下转换：static_cast 与 dynamic_cast

源码把普通节点和哨兵都通过基类指针连接，但只有普通节点有元素：

struct ListBaseNode<T> { /* 前后指针 */ };
struct ListValueNode<T> : ListBaseNode<T> { /* 元素 */ };
 
T& ListBaseNode<T>::value() {
    return static_cast<ListValueNode<T>&>(*this).m_value;
}

上面是示意性摘录。List 的 m_dummy 本身是 ListBaseNode<T>，普通元素节点则按 ListValueNode<T> 分配。算法若已确定基类引用指向一个真实元素节点的基类子对象，就可用 static_cast 向下转换，并访问其 m_value。这种转换不做运行时类型检查；编译器只检查静态类型关系等条件。

这依赖不变量：value() 的接收对象必须是相应派生对象中的基类子对象。若对只有基类对象的 m_dummy 调用 value()，向下转换本身就产生未定义行为。因此 end() 代表哨兵，不能解引用；空链表上 front()、back() 也不能调用。实际节点是否已满足相关对象生命周期要求，是独立于类型转换正确性的前提。

对于需要运行时判断的多态层次，可以使用 dynamic_cast：

struct Base { virtual ~Base() = default; };
struct Derived : Base {};
 
Base* p = /* 指向某个存活的多态对象 */;
if (auto* d = dynamic_cast<Derived*>(p)) {
    // 运行时检查成功，可以通过 d 使用 Derived
}

运行时向下转换要求源类型为多态类型，即有至少一个虚函数。检查失败时，指针形式返回 nullptr，引用形式抛出 std::bad_cast；它还支持符合条件的跨继承层次转换。运行时检查通常需要 RTTI 等实现支持并有相应成本，具体成本依实现和场景而定。static_cast 不需要这种运行时检查，但错误的向下转换不会给出失败信号。

源码的 ListBaseNode<T> 没有虚函数，因此不能直接对这里的基类引用使用需要运行时检查的 dynamic_cast。链表选择维护节点类型不变量，并让调用方在访问值前避开哨兵。

description	从 stl1weekend 的 List 实现出发，理解分配器重绑定、push 重载、常量迭代器的值类型和节点向下转换。
tags	cpp, stl

🐧 Blog

探索

从 List 源码理解 allocator、迭代器与类型转换

从 List 源码理解 allocator、迭代器与类型转换

allocator_traits 和节点分配器

为什么分配 T 的 allocator 不够

traits 提供统一入口

为什么需要这一层

traits 具体提供什么

rebind_alloc 的类型和对象

源码支持 allocator 的范围

List 的 union 与 Vector 的元素存储

Vector 为什么没有 union

对源码生命周期的注意事项

push 的拷贝与移动重载

为什么保留两个 push 重载

const_iterator 的 value_type 为什么是 T

节点向下转换：static_cast 与 dynamic_cast

参考文献

关系图谱

目录

反向链接