Skip to main content

Chapter 51: Mini List

核心问题与阅读主线

本章导读7 个核心小节 · 附自检与总结

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_baseMiniList 成员,随容器共存亡否end() 返回 &sentinel_,尾插等价于“插到哨兵前”
普通节点list_nodeallocator 分配,随插删创建销毁是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 链表重排:

  1. 闭合源链缺口:before_first->next = last、last->prev = before_first。
  2. 接入目标前驱:before_pos->next = first、first->prev = before_pos。
  3. 连接区间尾部: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_nodedestroy → deallocate先结束 list_node 与 T 生命周期,再归还内存跨容器 splice 后要求目标 allocator 与源端相等

完整拷贝、移动与交换还受 allocator 传播规则约束;审查 MiniList 核心实现按以下顺序核对:

排查顺序

  1. 哨兵不变量:空表自环、非空双向闭合与 end() 不可解引用边界是否全程成立。
  2. iterator 模型:iterator 是否仅保存 list_node_base*,局部插入不移动已有节点地址。
  3. 修改提交点:insert/emplace 是否先构造后入链,erase/clear 是否先存后继断链再销毁。
  4. 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> 管理节点原始存储与对象生命周期,保证异常清理、销毁与跨容器释放严格配对。