Skip to main content

Chapter 13: List

核心问题与阅读主线

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

std::list 把元素存入独立节点并以 prev / next 指针串联顺序,在任意已知位置提供常数时间插删与稳定的双向迭代器,代价是放弃随机访问并引入逐节点分配与缓存开销(见 std::list 草案概览)。工程上判断一个 list 操作,核心聚焦四点:修改了哪些指针、谁持有元素生命周期、哪些迭代器继续有效,以及指针重连是否真能抵消遍历成本。

全章共用代码样本(下文各节持续拆解)

贯穿材料核心代码

本章贯穿一个双队列样本:std::list<Record> 中的 Record 代表高移动成本对象,依次演示尾插、跨链表 splice 迁移、链表 sort 与 reverse,借此追踪节点所有权、指针重连与迭代器归属变化。

#include <list>
#include <string>

struct Record {
int id{};
std::string payload;

bool operator<(const Record& other) const {
return id < other.id;
}
};

void pipeline() {
std::list<Record> ready;
std::list<Record> delayed;

ready.push_back({3, "decode"});
ready.push_back({1, "parse"});
ready.push_back({2, "index"});

auto it = std::next(ready.begin());
delayed.splice(delayed.begin(), ready, it);

ready.sort();
ready.reverse();
}

其中 push_back 分配并挂接新节点,splice 直接转移已有节点归属,sort 与 reverse 则通过重写指针完成重排而不搬移 Record 本体。

13.1 双向链表、节点结构与 prev / next 指针​

与 vector(连续下标)和 deque(分段索引)不同,std::list 靠节点间链接表达顺序。每个节点保存元素值与 prev / next 指针,容器本体维护哨兵节点(sentinel)以统一 begin()、end() 与空状态(真实 STL 会把基类节点、allocator rebind 与调试状态拆开,下例仅保留核心字段):

template<class T>
struct list_node {
list_node* prev;
list_node* next;
T value;
};

关键事实

双向链表的三条核心不变量:

  • 双向自洽:任意有效节点 n 均满足 n->next->prev == n 且 n->prev->next == n。
  • 半开边界:begin() 指向首节点,end() 指向哨兵位置;end() 可比较和 --it 递减,严禁解引用。
  • 空表闭环:空链表令 sentinel.next == &sentinel 且 sentinel.prev == &sentinel,使空表与非空表的插删走同一套重连路径。

迭代器内部通常只保存一个节点指针,++it 跳向 node->next,--it 跳向 node->prev,天然满足 bidirectional iterator;因跨节点必须逐跳追踪指针,它不支持常数时间 it + n(见 cppreference 的 std::list 总览)。

在 position 前插入节点时,必须先构造节点,再以无抛异常的四次指针赋值接入链表(虚线为插入后的新链接):

void link_before(list_node<int>* position, list_node<int>* node) {
list_node<int>* before = position->prev;

node->prev = before;
node->next = position;
before->next = node;
position->prev = node;
}

局部重连使任意已知位置的插入达到常数时间,无需搬移后续元素或重分配存储;代价是每节点多出两个指针,且堆节点离散分布削弱了 CPU 预取与 cache locality。贯穿样本中的 ready.push_back({3, "decode"}) 即在哨兵前接入新节点,已有节点地址与既有迭代器均不变。

13.2 节点分配、allocator 参与与元素所有权​

与 vector 批量分配连续数组不同,std::list 通常为每个元素单独申请节点存储。容器虽写为 std::list<T, Allocator>,内部仍需通过 allocator_traits<Allocator>::rebind_alloc 转为分配节点类型(近似 list_node<T>)。

节点所有权归容器所有,用户持有的引用、指针与迭代器均不拥有节点。三类操作的生命周期分工明确:

  • 插入(insert / emplace / push_*):分配并构造新节点,接管所有权。
  • 擦除(erase / pop_* / clear):摘除节点、析构 T 并释放存储。
  • 迁移(splice):仅重连已有节点,将所有权从源链表转移至目标链表,不构造也不析构 T。

下面的简化逻辑展示 emplace 如何靠提交顺序保证异常安全:

template<class T, class Allocator, class... Args>
auto emplace_before(node_base* position, Allocator& alloc, Args&&... args) -> node_base* {
using node = list_node<T>;
using node_alloc = typename std::allocator_traits<Allocator>
::template rebind_alloc<node>;

node_alloc na(alloc);
node* p = std::allocator_traits<node_alloc>::allocate(na, 1);

try {
std::allocator_traits<node_alloc>::construct(
na,
std::addressof(p->value),
std::forward<Args>(args)...
);
} catch (...) {
std::allocator_traits<node_alloc>::deallocate(na, p, 1);
throw;
}

link_before(position, p);
return p;
}

提交点在末尾的 link_before:分配失败不会改动链表;构造 T 抛异常时立即 deallocate 回收原始内存;只有对象就绪后才接入链表(与 list.modifiers 草案条目 中单元素常数时间插入、异常无效果的语义一致)。

擦除路径严格反向:erase(pos) 先调用无异常的 unlink 摘链,再析构节点内的 T(标准容器要求析构不抛异常),最后释放节点内存,且仅使被删元素对应的迭代器与引用失效:

void unlink(list_node<int>* node) noexcept {
node->prev->next = node->next;
node->next->prev = node->prev;
}

回到贯穿样本:ready.push_back 为每个 Record 创建独立节点(Record::payload 的堆缓冲仍归 Record 自身管理),而 it = std::next(ready.begin()) 仅记录节点位置,直到对应节点被 erase 才失效。

边界与误区

注意

“先备节点、再提交”保证了强异常安全,但也意味着每次插入通常触发一次独立的堆分配。对大量小对象而言,分配器元数据与双指针开销会迅速放大;若确需节点稳定性,应评估内存池或 std::pmr::list;若以连续扫描为主,独立分配的 cache 成本将盖过常数时间插入收益。

13.3 insert、erase 与 splice 的指针重连路径​

insert、erase 与 splice 都只修改局部指针,但对节点与元素生命周期的影响截然不同:

操作节点与元素动作迭代器与引用有效性复杂度与关键边界
insert / emplace分配新节点,构造元素已有位置全部有效;返回新节点迭代器单个常数时间;先构造后链接,异常时无效果
erase摘链、析构元素并释放节点仅被删元素的迭代器/指针/引用失效,其余有效单个常数时间;返回后继迭代器供循环安全推进
splice不构造也不析构元素,仅迁移节点原位置均有效,但归属切换至目标链表单节点/整表常数时间;跨表区间通常线性时间

循环擦除时,安全推进的关键是接住 erase 返回的后继迭代器;旧 it 在节点释放后立即失效,绝不能再解引用或 ++it:

for (auto it = ready.begin(); it != ready.end(); ) {
if (it->id < 0) {
it = ready.erase(it);
} else {
++it;
}
}

splice 是 list 区别于连续容器的核心能力——它执行节点级的转移语义(destructive move):元素留在原节点地址,只改写节点归属(参见 list.ops 的 splice 条目)。贯穿样本中的 delayed.splice(delayed.begin(), ready, it) 把 ready 第二个节点摘下并接入 delayed 头部:ready.size() 减 1、delayed.size() 加 1,Record 与 payload 均无拷贝或移动,it 仍指向同一对象,只是从此属于 delayed。

void splice_one(node_base* position, node_base* node) noexcept {
node->prev->next = node->next;
node->next->prev = node->prev;

node_base* before = position->prev;
node->prev = before;
node->next = position;
before->next = node;
position->prev = node;
}

边界与误区

注意

使用 splice 必须守住三条硬边界:

  • allocator 必须相等:跨链表 splice 要求两容器 allocator 比较相等(否则目标链表日后无法正确释放源链表分配的节点),不等属于未定义行为。
  • 区间禁止自重叠:区间 splice 的目标位置不能落在被移动区间 [first, last) 内部;同链表内将单节点插到自身或下一位置前为空操作。
  • 跨表区间的复杂度陷阱:单节点与整表 splice 为常数时间,但跨链表区间 splice 通常退化为线性时间——标准要求维护 size(),实现必须遍历统计区间节点数。

13.4 merge、sort 与 reverse 的链表级算法​

通用 <algorithm> 依赖赋值或随机访问(如 std::sort 要求 random access iterator),无法发挥链表指针重连的优势。std::list 因此提供成员级 merge、sort 与 reverse,直接改写节点链接以消除元素拷贝与移动:

成员算法前置条件复杂度与稳定性元素移动与迭代器影响
merge(x)两链表均按同一比较器有序,且 allocator 相等最多 size() + x.size() - 1 次比较;稳定零元素拷贝;x 变空,迁入元素的迭代器归属目标链表
sort(comp)比较器满足严格弱序约 N log N 次比较(归并思路);稳定仅重连节点,已有迭代器与引用仍指向原对象,但相对顺序改变
reverse()无线性时间,零次比较翻转各节点 prev / next;所有迭代器与引用保持有效,顺序反转

merge 的核心是双游标归并:每次比较两链表游标指向的值,将较小前缀节点范围直接接入目标位置,不触碰元素构造(见 merge 草案条目):

std::list<Record> a = {{1, "a1"}, {3, "a3"}};
std::list<Record> b = {{2, "b2"}, {4, "b4"}};

a.merge(b);

执行后 a 变为 1, 2, 3, 4,b 为空;原属 b 的节点迭代器仍指向对应 Record,只是归属切换为 a 的序列语境。同样,贯穿样本中的 ready.sort() 与 ready.reverse() 分别通过链表归并与翻转 prev/next 完成重排,已有引用和迭代器继续有效。

边界与误区

注意

使用链表级算法时需注意三条常见边界:

  • 迭代器有效 ≠ 遍历顺序不变:sort 与 reverse 不会使任何迭代器失效,但重排后原有的 ++it 会步入新的后继节点。
  • 比较器抛异常的语义:若 list::sort 中比较器抛异常,所有节点仍安全归属容器且不泄漏,但链表元素处于未指定顺序。
  • 零移动不等于总性能胜出:list::sort 虽减少元素移动,却全程伴随离散指针跳转;除非元素移动成本极高,否则 std::sort 作用于连续 vector 上通常因 cache locality 更快。

13.5 随机访问缺失、cache miss 与容器对比​

list 把局部插删压缩为指针重连,却将遍历、空间与分配成本摊到每个元素。它不提供 operator[] 与 at(),即便调用标准算法辅助定位,底层仍绕不开线性跳指针:

auto nth = std::next(ready.begin(), 1000); // 对 list 是线性推进

更隐蔽的瓶颈是 cache miss:节点散落在堆上导致硬件预取失效,且 64 位平台每个节点固定附带 16 字节的 prev / next 指针与分配器元数据,小对象场景的空间开销往往高于数据本身。

从所有权、访问局部性与迭代器稳定性统一对比四个顺序容器:

容器内存布局随机访问与局部性插删强项与代价迭代器稳定性适用场景
std::vector单块连续数组O(1) 下标;cache 局部性最佳尾插均摊 O(1);中间插删搬移后续元素扩容全部失效;中间插删使后续失效默认首选:高频扫描、下标访问、排序
std::deque分段定长块 + map 控制表O(1) 下标(两级寻址);局部性中等首尾插删 O(1);中间插删仍搬移元素首尾插删使迭代器失效(引用稳定);中间全面失效双端入出队、避免大块整体重分配
std::list双向独立节点无随机访问(线性推进);易 cache miss已知位置插删/跨表 splice 为 O(1);逐节点堆分配除被删节点外永久有效(含 splice/sort)外部长期持有迭代器、高频迁移重对象
std::forward_list单向独立节点(无 size())仅前向遍历;无随机访问单指针空间更省;仅支持 before_begin 配合 insert_after/erase_after除被删节点外永久有效极致压缩单节点体积的单向链式结构

核心判断

工程选型按四步过滤,全部通过再考虑 std::list:

  1. 访问模式:是否需要下标访问或高吞吐顺序扫描?需要则首选 vector 或 deque。
  2. 定位方式:插删位置是否已被迭代器直接持有?若每次仍需从头遍历查找,常数时间重连无法抵消线性定位成本。
  3. 元素与分配开销:元素移动成本是否高到足以掩盖逐节点堆分配与每节点双指针的体积膨胀?
  4. 稳定性契约:外部是否长期缓存迭代器并要求跨插删、splice 与重排不失效?只有稳定性成为硬契约,list 才胜出。

13.6 intrusive list 思想与 mini list 实现​

标准 std::list<T> 是非侵入式容器,而内核、游戏引擎与对象池中常见侵入式链表(intrusive list)。两者的核心分界在于节点包装与对象生命周期由谁管理:

对比维度非侵入式(std::list<T>)侵入式链表(Intrusive List)
链接字段位置容器分配独立节点包裹 Tprev / next 直接嵌入业务对象内部
生命周期归属容器拥有 T,erase 即析构并释放外部拥有对象,摘链不等于销毁对象
契约与风险符合 STL 值语义与 allocator 模型零额外节点分配,但业务方须严防重复入链与悬空销毁

下面的 mini_list 演示非侵入式双向链表的最小骨架(哨兵节点、双向迭代器、emplace、push_back、erase 与 clear):

#include <cstddef>
#include <iterator>
#include <memory>
#include <utility>

template<class T>
class mini_list {
struct node_base {
node_base* prev;
node_base* next;

node_base() noexcept : prev(this), next(this) {}
};

struct node : node_base {
T value;

template<class... Args>
explicit node(Args&&... args) : value(std::forward<Args>(args)...) {}
};

public:
class iterator {
node_base* current = nullptr;

friend class mini_list;
explicit iterator(node_base* p) : current(p) {}

public:
using iterator_category = std::bidirectional_iterator_tag;
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using reference = T&;

reference operator*() const {
return static_cast<node*>(current)->value;
}

pointer operator->() const {
return std::addressof(operator*());
}

iterator& operator++() {
current = current->next;
return *this;
}

iterator operator++(int) {
iterator old = *this;
++(*this);
return old;
}

iterator& operator--() {
current = current->prev;
return *this;
}

iterator operator--(int) {
iterator old = *this;
--(*this);
return old;
}

friend bool operator==(iterator a, iterator b) {
return a.current == b.current;
}

friend bool operator!=(iterator a, iterator b) {
return !(a == b);
}
};

mini_list() = default;

~mini_list() {
clear();
}

bool empty() const {
return sentinel_.next == &sentinel_;
}

iterator begin() {
return iterator(sentinel_.next);
}

iterator end() {
return iterator(&sentinel_);
}

template<class... Args>
iterator emplace(iterator position, Args&&... args) {
node* fresh = new node(std::forward<Args>(args)...);
link_before(position.current, fresh);
return iterator(fresh);
}

void push_back(const T& value) {
emplace(end(), value);
}

iterator erase(iterator position) {
node_base* victim = position.current;
node_base* after = victim->next;
unlink(victim);
delete static_cast<node*>(victim);
return iterator(after);
}

void clear() {
auto it = begin();
while (it != end()) {
it = erase(it);
}
}

private:
node_base sentinel_;

static void link_before(node_base* position, node_base* fresh) {
node_base* before = position->prev;
fresh->prev = before;
fresh->next = position;
before->next = fresh;
position->prev = fresh;
}

static void unlink(node_base* victim) {
victim->prev->next = victim->next;
victim->next->prev = victim->prev;
}
};

阅读 mini_list 可沿三条线索对照标准实现:

  • 哨兵自环:sentinel_ 构造时指向自身,令空表与非空表共享 link_before / unlink;begin() 取 sentinel_.next,end() 取 &sentinel_。
  • 类型擦除与向下转型:iterator 仅持有 node_base*,解引用时向下转型为 node* 读取 value,避免哨兵节点构造多余的 T。
  • 提交与清理顺序:emplace 先 new node 构造元素再 link_before;erase 先保存后继节点,再摘链、delete 并返回后继迭代器。

关键事实

mini_list 刻意用 new / delete 凸显链接骨架;真实 STL 源码中看似繁琐的部分,本质是在补齐三项生产级契约:

  • Allocator 策略:引入 allocator_traits 与 rebind_alloc 支持定制内存资源。
  • 完整值语义与接口:补齐拷贝/移动构造与赋值运算符、const_iterator、splice 及常数时间 size() 缓存。
  • 异常安全 guard:防止构造后或范围操作中途抛异常导致节点泄漏。

最小自检任务​

动手自检先独立判断

阅读下面代码,独立判断四个问题:

  1. it_ready 和 it_delayed 在每一步后是否仍有效?
  2. Record 对象在哪些操作中被构造、移动、拷贝或析构?
  3. delayed.splice 之后 it_ready 属于哪个链表语境?
  4. 这一场景应选择 list 还是 vector?
std::list<Record> ready = {
{3, "decode"},
{1, "parse"},
{2, "index"}
};

std::list<Record> delayed = {
{9, "sleep"}
};

auto it_ready = std::next(ready.begin());
auto it_delayed = delayed.begin();

delayed.splice(delayed.end(), ready, it_ready);
ready.sort();
delayed.erase(it_delayed);
delayed.reverse();

本章知识点总结​

  • 节点布局与哨兵

    std::list 用 prev / next 指针串联独立节点并借哨兵统一边界,迭代器仅封装节点指针,属于无随机访问能力的双向迭代器。

  • 分配与异常安全

    容器持有全部节点所有权,单元素插入先经 rebind_alloc 分配并构造 T,再以无抛异常指针重连作为提交点;擦除则反向摘链、析构并释放,仅使被删位置失效。

  • splice 转移语义

    splice 直接重连已有节点而不触碰元素构造/析构,原迭代器、指针与引用继续指向同一对象并归属目标链表。

  • allocator 与区间边界

    跨链表 splice 与 merge 均要求两侧 allocator 比较相等;跨表区间 splice 通常需线性遍历统计节点数以维护 size()。

  • 链表级算法

    成员 merge、sort(稳定、约 N log N 次比较,比较器抛异常时顺序未指定)与 reverse 均通过重连节点完成重排,不使未删迭代器失效。

  • 性能代价与选型

    list 以逐节点堆分配、每节点双指针开销及弱 cache locality 换取局部稳定性;需随机访问或连续扫描时首选 vector / deque,需已定位节点高频迁移再选 list。

  • 侵入式与最小模型

    非侵入式 std::list 由容器管理节点与生命周期,侵入式链表把指针嵌入业务对象并由外部负责生命周期;mini_list 仅保留核心链接骨架,生产级容器还需补齐 allocator、完整值语义与异常安全 guard。