Chapter 51: Mini List
核心问题与阅读主线
std::list 的核心工程问题是:如何在不搬移已有元素的前提下,以稳定节点地址支持任意位置的 insert、erase、splice 与 clear。本章通过哨兵节点、list_node_base* 迭代器、提交点分离与 allocator_traits 节点管理,实现最小双向链表 MiniList。
全章共用场景样本
本章贯穿材料是一组操作序列:创建 MiniList<int> a 依次插入 1、2、3,在 2 前插入 10,删除 3,再将另一条链表 b 的节点区间接入 a。全章追踪三类对象的状态变化:保存端点关系的哨兵节点、承载元素的普通节点,以及仅保存节点地址的 iterator。
与 MiniVector 相比,MiniList 用每节点独立分配与双指针开销,换取局部修改不搬移元素的能力:
| 对比维度 | MiniList(双向链表) | MiniVector(连续数组) |
|---|---|---|
局部 insert / erase | 仅重连相邻指针,O(1) | 需搬移后续元素,O(n)(扩容时全量搬移) |
| 地址与 iterator 稳定性 | 除被删节点外地址与 iterator 始终稳定 | 插入或扩容可能使全部地址与 iterator 失效 |
| 单元素额外空间 | 每节点多 2 个指针(prev、next)且独立分配 | 无节点指针开销,仅受 capacity 预留策略影响 |
| 遍历局部性 | 节点离散分配,指针追踪易触发 cache miss | 连续内存顺序扫描,硬件预取友好 |
51.1 node 结构
若直接用 nullptr 表示 end(),空表判断、--end() 与头尾边界重连都需要额外分支。MiniList 采用哨兵节点把双向链表收束为统一环状结构:空表时哨兵的 prev 与 next 均指向自身;非空时 next 指向首节点、prev 指向尾节点。
为防止对哨兵执行元素构造或解引用,节点拆分为无值基类 list_node_base 与带值派生类 list_node:
#include <cstddef>
#include <memory>
#include <utility>
template<class T>
class MiniList {
struct list_node_base {
list_node_base* prev;
list_node_base* next;
};
struct list_node : list_node_base {
template<class... Args>
explicit list_node(Args&&... args)
: list_node_base{nullptr, nullptr},
value(std::forward<Args>(args)...) {}
T value;
};
list_node_base sentinel_;
std::size_t size_ = 0;
public:
MiniList() noexcept : sentinel_{&sentinel_, &sentinel_} {}
};
两类节点在存储来源、生命周期与位置语义上严格区分:
| 节点角色 | 节点类型 | 存储来源与生命周期 | 是否持有 T | 端点语义 |
|---|---|---|---|---|
哨兵节点 sentinel_ | list_node_base | MiniList 成员,随容器共存亡 | 否 | end() 返回 &sentinel_,尾插等价于“插到哨兵前” |
| 普通节点 | list_node | allocator 分配,随插删创建销毁 | 是 | begin() 返回 sentinel_.next,空表时等于 end() |
关键事实
- 双向自洽:任意在链节点
p均满足p->next->prev == p与p->prev->next == p。 - 正向闭合:从
sentinel_.next沿next扫描最终回到&sentinel_。 - 反向闭合:从
sentinel_.prev沿prev扫描最终回到&sentinel_。 - 空表基线:空表时
sentinel_.next == &sentinel_且sentinel_.prev == &sentinel_,即begin() == end()。
贯穿材料中,初始空表 a 已具备有效 sentinel_ 且 size_ == 0。依次插入 1、2、3 时,容器为每个元素分配独立 list_node,sentinel_ 只改写首尾指针,自身不保存 int。
51.2 iterator
MiniList 的 iterator 只保存一个 list_node_base*(不持有容器指针或元素副本)。++ 与 -- 沿 next/prev 移动,解引用时将该地址静态转为 list_node* 并访问 value。
下面的简化实现保留核心移动与解引用路径(工程实现还会补全 const_iterator、友元与跨容器调试检查):
template<class T>
class MiniListIterator {
using base_node = typename MiniList<T>::list_node_base;
using value_node = typename MiniList<T>::list_node;
base_node* current_ = nullptr;
public:
using difference_type = std::ptrdiff_t;
using value_type = T;
using reference = T&;
using pointer = T*;
using iterator_category = std::bidirectional_iterator_tag;
explicit MiniListIterator(base_node* p) noexcept : current_(p) {}
reference operator*() const noexcept {
return static_cast<value_node*>(current_)->value;
}
pointer operator->() const noexcept {
return std::addressof(operator*());
}
MiniListIterator& operator++() noexcept {
current_ = current_->next;
return *this;
}
MiniListIterator& operator--() noexcept {
current_ = current_->prev;
return *this;
}
friend bool operator==(MiniListIterator lhs, MiniListIterator rhs) noexcept {
return lhs.current_ == rhs.current_;
}
};
该单指针模型决定了 iterator 的能力边界:
- 双向移动、非随机访问:每个节点保有
prev与next,故++/--为O(1),但推进n步须沿链走O(n)次。 - 指针相等语义:
operator==仅比对current_地址,跨容器比较没有合法语义(调试版通常会记录容器身份以捕获此类误用)。
边界与误区
end() 指向内嵌哨兵 sentinel_,可用于边界比较与 --end()(回退至尾节点),但哨兵并非 list_node 且不含 value。解引用 end() 会越界读取基类对象;release 热路径不做运行时分支校验,由调用约束或调试检查负责拦截。
贯穿材料中,插入 1、2、3 后指向 2 的 iterator 保存节点 N2 的地址。随后在 2 前插入 10 只改写相邻链接而不搬移 N2,原 iterator 仍稳定指向元素 2。
51.3 insert
insert(及 emplace)按“分配节点 → 构造元素 → 链接到 pos 前 → 递增 size_”四步推进。所有可能抛出异常的操作都放在入链提交之前,确保失败时不污染原有链表。
局部链接 link_before(pos, fresh) 只需读取 before = pos->prev,并完成 before <-> fresh <-> pos 的双向接通:
static void link_before(list_node_base* pos, list_node_base* fresh) noexcept {
list_node_base* before = pos->prev;
fresh->prev = before;
fresh->next = pos;
before->next = fresh;
pos->prev = fresh;
}
link_before 先填充新节点的 fresh->prev 与 fresh->next,再改写旧链端点 before->next 与 pos->prev,保证新节点在两侧指针就绪后才暴露到主链。
下面的 emplace 展示完整节点创建与提交路径(insert 可直接转发给 emplace):
template<class T, class Alloc = std::allocator<T>>
class MiniList {
struct list_node_base { list_node_base* prev; list_node_base* next; };
struct list_node : list_node_base {
template<class... Args>
explicit list_node(Args&&... args)
: list_node_base{nullptr, nullptr}, value(std::forward<Args>(args)...) {}
T value;
};
using node_allocator = typename std::allocator_traits<Alloc>
::template rebind_alloc<list_node>;
using node_traits = std::allocator_traits<node_allocator>;
list_node_base sentinel_{&sentinel_, &sentinel_};
std::size_t size_ = 0;
node_allocator node_alloc_;
template<class... Args>
list_node* create_node(Args&&... args) {
list_node* p = node_traits::allocate(node_alloc_, 1);
try {
node_traits::construct(node_alloc_, p, std::forward<Args>(args)...);
} catch (...) {
node_traits::deallocate(node_alloc_, p, 1);
throw;
}
return p;
}
public:
using iterator = MiniListIterator<T>;
template<class... Args>
iterator emplace(iterator pos, Args&&... args) {
list_node* fresh = create_node(std::forward<Args>(args)...);
link_before(pos.current_, fresh);
++size_;
return iterator{fresh};
}
};
核心判断
emplace 的强异常安全来自提交点分离:create_node 中若 T 的构造函数抛出异常,新节点尚未构造完成也未入链,只需 deallocate 归还存储即可恢复旧状态;一旦返回有效 fresh,后续 link_before 与 ++size_ 均为 noexcept。
贯穿材料中,在 2 前插入 10 时 pos 为 N2、before 为 N1。link_before 将局部关系从 N1 <-> N2 更新为 N1 <-> N10 <-> N2,N2 地址不变,原 iterator 继续有效。
51.4 erase
erase 按“记录后继 → 局部断链 → 销毁并释放节点 → 递减 size_ → 返回后继 iterator”顺序执行。工程上要求元素 T 的析构函数不抛异常,确保清理路径可以完整收尾。
断链函数 unlink_node 与 link_before 互为镜像,让 victim->prev 与 victim->next 直接闭合,使待删节点彻底脱离链表:
static void unlink_node(list_node_base* victim) noexcept {
list_node_base* before = victim->prev;
list_node_base* after = victim->next;
before->next = after;
after->prev = before;
}
为支持调用方在遍历循环中原地删除当前元素,erase 必须在销毁节点前暂存 raw->next;释放后再读取 raw->next 会访问已结束生命周期的对象:
iterator erase(iterator pos) noexcept {
list_node_base* raw = pos.current_;
list_node_base* next = raw->next;
unlink_node(raw);
destroy_node(static_cast<list_node*>(raw));
--size_;
return iterator{next};
}
边界与误区
严禁调用 erase(end()):end() 指向容器内嵌的 sentinel_,既没有构造 value,也不能交给 allocator 释放。调试版可断言 pos.current_ != &sentinel_,release 版将该前提交给调用约束以保持热路径无分支。
贯穿材料中,链表 1, 10, 2, 3 删除 3 时 victim 为尾节点 N3、暂存 next 为 &sentinel_。断链销毁后 N2->next 与 sentinel_.prev 相互指向,erase 返回 end()。
51.5 splice
splice 的语义是节点所有权转移:把源链表的半开区间 [first, last) 整段摘下并接入目标位置 pos 之前(last 可为源链表哨兵,尾节点是 last->prev)。被移动元素的 iterator 与 reference 仍指向同一对象,仅容器归属切换至目标链表。
static void transfer_before(
list_node_base* pos,
list_node_base* first,
list_node_base* last
) noexcept {
if (first == last) {
return;
}
list_node_base* before_first = first->prev;
list_node_base* last_node = last->prev;
list_node_base* before_pos = pos->prev;
before_first->next = last;
last->prev = before_first;
before_pos->next = first;
first->prev = before_pos;
last_node->next = pos;
pos->prev = last_node;
}
transfer_before 以六次指针写入完成迁移,全程不触碰持有资源的 T 对象(无拷贝、移动或析构),适合任务队列合并与 LRU 链表重排:
- 闭合源链缺口:
before_first->next = last、last->prev = before_first。 - 接入目标前驱:
before_pos->next = first、first->prev = before_pos。 - 连接区间尾部:
last_node->next = pos、pos->prev = last_node。
虽然指针重连恒为 O(1),但 size_ 维护成本随转移范围与容器关系而异:
splice 场景 | 指针重连成本 | size_ 更新策略 | 关键检查项 |
|---|---|---|---|
| 单节点转移 | O(1)(6 次写入) | O(1)(两端各增减 1) | 跨容器时校验 allocator 相等 |
跨容器区间 [first, last) | O(1)(6 次写入) | 按 size_ 策略决定(若维护 O(1) 长度则需线性计数 O(k)) | 校验 allocator 相等且 [first, last) 合法 |
同容器区间 [first, last) | O(1)(6 次写入) | O(1)(总节点数不变,无需计数) | pos 不落于 [first, last) 内,过滤自移动空操作 |
边界与误区
- 区间合法:
[first, last)必须是有效半开区间,且目标位置pos不得落入[first, last)内部。 - allocator 配对:跨容器
splice必须满足get_allocator() == other.get_allocator(),不相等时应断言或报错,防止目标容器错用释放器。 - 同容器空操作:自移动必须显式处理
pos == first、pos == last与first == last等无效果分支。
贯穿材料中,若 b 为 20, 30, 40,将 [20, 40) 接入 a 的 2 前会迁移 20、30 两个节点。操作后 a 为 1, 10, 20, 30, 2,b 仅剩 40,原指向 20 的 iterator 仍可解引用并沿 a 的链接遍历。
51.6 clear
clear 负责销毁全部普通节点并把哨兵恢复为空表自环状态,使 MiniList 回到 begin() == end() 且可继续插入。循环必须在调用 destroy_node 前暂存 current->next,防止节点释放后访问已结束生命周期的字段:
void clear() noexcept {
list_node_base* current = sentinel_.next;
while (current != &sentinel_) {
list_node_base* next = current->next;
destroy_node(static_cast<list_node*>(current));
current = next;
}
sentinel_.next = &sentinel_;
sentinel_.prev = &sentinel_;
size_ = 0;
}
核心判断
clear() 无需逐个调用 erase():直接暂存后继并销毁节点、最后重置哨兵与 size_ 可省去冗余断链写入(仅调试单步不变量时才逐个断链)。容器析构函数复用 clear() 收尾,只释放普通节点,绝不释放成员 sentinel_。
贯穿材料中,a.clear() 依次销毁 1, 10, 20, 30, 2 对应节点后将 a 重置为空表。由于跨容器 splice 已转移归属,原由 b 分配的 20、30 由 a.clear() 清理,b 仍保留自己的 40 节点。
51.7 allocator 参与
MiniList 接收元素类型 T 的 allocator Alloc,但实际分配单位是 list_node。自 C++11 起,容器通过 std::allocator_traits<Alloc>::template rebind_alloc<list_node> 重新绑定节点分配器,将内存管理与对象生命周期拆为“分配存储 → 构造节点 → 链接入表 → 销毁释放”四阶段:
void destroy_node(list_node* p) noexcept {
node_traits::destroy(node_alloc_, p);
node_traits::deallocate(node_alloc_, p, 1);
}
create_node 与 destroy_node 严格成对,构造失败路径不得错误触发 destroy:
| 生命周期路径 | 执行步骤 | 异常或收尾行为 | 配对约束 |
|---|---|---|---|
create_node(正常) | allocate → construct → 返回节点 | 入链后交由容器统一管理 | 与 destroy_node 使用同一 node_alloc_ |
create_node(构造异常) | allocate → construct 抛出 → deallocate → throw | 仅释放原始存储,不调用 destroy | 避免析构未构造对象,维持强异常安全 |
destroy_node | destroy → deallocate | 先结束 list_node 与 T 生命周期,再归还内存 | 跨容器 splice 后要求目标 allocator 与源端相等 |
完整拷贝、移动与交换还受 allocator 传播规则约束;审查 MiniList 核心实现按以下顺序核对:
排查顺序
- 哨兵不变量:空表自环、非空双向闭合与
end()不可解引用边界是否全程成立。 - iterator 模型:iterator 是否仅保存
list_node_base*,局部插入不移动已有节点地址。 - 修改提交点:
insert/emplace是否先构造后入链,erase/clear是否先存后继断链再销毁。 - allocator 配对:是否使用
rebind_alloc<list_node>,构造失败只deallocate,跨容器splice校验 allocator 相容。
最小自检任务
阅读下面的操作序列,判断每一步之后哪些 iterator 仍可用,哪些节点由哪个容器负责清理,并说明 splice 对元素对象执行了哪些构造、移动、析构动作。
MiniList<int> a;
MiniList<int> b;
a.emplace(a.end(), 1);
a.emplace(a.end(), 2);
a.emplace(a.end(), 3);
b.emplace(b.end(), 10);
b.emplace(b.end(), 20);
MiniList<int>::iterator it2 = ++a.begin();
MiniList<int>::iterator it10 = b.begin();
a.emplace(it2, 7);
a.erase(--a.end());
a.splice(it2, b, it10, b.end());
a.clear();
本章知识点总结
- 哨兵与分层
list_node_base仅存prev/next,内嵌哨兵使其与list_node共用一套循环不变量,统一空表与end()边界。 - iterator 状态
仅封装
list_node_base*,支持O(1)双向步进且插删不改变其余节点地址;end()可比较和--end(),不可解引用。 - insert 提交点
按“分配 → 构造 →
link_before→ 递增size_”推进,构造抛异常时仅deallocate即可保强异常安全。 - erase 销毁顺序
先暂存
next并unlink_node断链,再destroy_node销毁释放并返回后继 iterator;erase(end())属于非法调用。 - splice 零拷贝迁移
六次指针写入切换
[first, last)节点归属而不触碰元素对象,跨容器迁移须保证 allocator 相容与pos不落于区间内。 - clear 与析构收束
循环须先存
current->next再销毁节点,最后重置哨兵自环与size_ = 0,析构绝不释放成员sentinel_。 - allocator 节点重绑定
通过
rebind_alloc<list_node>管理节点原始存储与对象生命周期,保证异常清理、销毁与跨容器释放严格配对。