Chapter 13: List

std::list 的核心判断入口是节点所有权。它把元素放进独立节点，通过前驱和后继指针维持顺序；容器本体保存边界状态，迭代器保存节点位置。公开 C++ 工作草案把 list 定义为支持 bidirectional iterator、能在序列任意位置做常数时间插入和擦除、并自动管理存储的 sequence container；同时说明它没有快速随机访问能力，std::list 草案概览 给出的这些约束正好对应本章要追踪的实现形状。

本章用一个贯穿操作串起 list 的主要边界：先在 std::list<Record> 中插入节点，再用 splice 把某个节点从一个链表移动到另一个链表，随后对链表执行 sort 和 reverse。读完后应能定位一个 list 操作到底改了哪些指针、谁负责元素生命周期、哪些 iterator 仍指向同一元素、为什么链表算法能减少元素移动，以及什么时候该放弃 list 转向 vector 或 deque。

标准库没有规定实现必须把 std::list 写成某个固定节点结构。正文中的节点图和代码属于教学简化模型，用来解释常见实现形状和标准语义之间的关系。真实 libstdc++、libc++、MSVC STL 都会引入 allocator traits、调试 iterator、哨兵节点、大小缓存、异常路径封装等实现细节；这些细节不会改变本章建立的判断顺序：先看节点关系，再看生命周期，再看 iterator 有效性，再看算法是否能通过重连节点完成。

贯穿材料如下。Record 代表一个移动成本较高的对象，两个链表代表两个处理队列。我们关心的重点是节点迁移时元素对象是否被拷贝或移动、迭代器是否继续指向原来的元素、操作成本来自指针重连还是来自遍历。

#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 反转链接方向。这个例子覆盖了 list 最有价值的四个观察点：节点式布局、独立分配、局部指针重连、链表级算法。

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

list 的对象布局从顺序关系开始理解。vector 的顺序由连续下标表达，deque 的顺序由分段索引表达，list 的顺序由节点之间的链接表达。每个元素所在节点至少需要保存元素对象、前驱指针和后继指针；容器本体通常保存一个哨兵节点或边界指针，用来表示 begin()、end() 和空链表状态。

一个教学化节点可以写成下面的形状。真实实现会把基类节点、值节点、allocator rebound node type 和调试信息拆开，本模型只保留理解 list 所需的字段。

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() 可以比较和递减，不能解引用。第三，空链表的哨兵节点通常让 sentinel.next == &sentinel 且 sentinel.prev == &sentinel，这样插入和删除不需要把空链表作为特殊分支拆开。

这组不变量解释了 list iterator 的能力边界。iterator 内部通常只保存一个节点指针，++it 走到 node->next，--it 走到 node->prev，所以它自然满足 bidirectional iterator。它无法支持常数时间 it + n，因为从当前节点到第 n 个后继必须逐个跳转。std::list 页面也把 iterator 类型描述为 bidirectional iterator，并明确 list 支持常数时间任意位置插入和删除、缺少快速随机访问，cppreference 的 std::list 总览 与标准草案在这个结论上一致。

插入一个节点时，核心动作是把新节点接入两个相邻节点之间。下面的 Mermaid 图只描述指针关系，不描述 allocator 和构造步骤。

对应的指针重连顺序可以简化为四次赋值。实际实现会先构造节点，再用无抛异常的链接动作提交节点，防止构造失败破坏原链表。

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;
}

这段代码说明 list 的常数时间插入来自局部指针更新。它不需要移动插入点之后的元素，也不需要为已有元素重新分配存储。代价同样清楚：每个元素多出前驱和后继指针；遍历时节点可能分散在堆上，CPU 预取和 cache locality 都弱于连续内存容器。

贯穿例子中的 ready.push_back({3, "decode"}) 可以分解成三步：分配一个节点大小的原始存储，在节点中的 Record 位置构造对象，把节点接到哨兵前面。ready 中已有的节点地址和已有 iterator 不会变化，因为新节点只是接到链表边界。

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

list 的 allocator 参与点比 vector 更细。vector 通常一次分配一段能容纳多个元素的连续存储；list 的常见实现为每个元素节点单独申请存储。allocator 在这里不只管理 T 的存储，还要被 traits 转换成能分配内部节点类型的 allocator。标准接口写的是 std::list<T, Allocator>，但实现分配的常见对象更接近 list_node<T>。

节点所有权由容器持有。用户拿到的是元素引用、指针或 iterator，它们都不拥有节点。insert、emplace、push_front、push_back 创建新节点；erase、pop_front、pop_back、clear 销毁节点中的元素并释放节点存储；splice 在链表之间迁移已有节点，所有权从源链表转移到目标链表。这个区分决定了异常安全和 iterator 行为。

下面的简化伪代码把 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 失败时释放原始存储；只有构造成功后才接入链表。标准草案对 list 插入给出的复杂度是单元素常数时间，并且一次构造 T；还说明插入不影响 iterator 和引用的有效性，异常抛出时没有效果，list.modifiers 草案条目 支撑的正是这条实现路径。

擦除路径与插入路径反向。erase(pos) 先把节点从链中摘除，再析构节点里的 T，最后释放节点存储。摘链动作本身不抛异常，T 的析构函数在标准库容器语境下应保持不抛异常的工程约定；节点释放由 allocator 完成。标准草案说明单个元素擦除是常数时间，会调用一次 T 的析构函数，并且只让被擦除元素对应的 iterator 和引用失效。

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

因此，list 的异常安全来自“先准备节点，再提交链接”的顺序。它的分配成本也来自这里：每插入一个元素通常触发一次节点分配。对于大量小对象，allocator 的选择、内存池、std::pmr::list 这类资源策略会显著改变分配开销；对于连续扫描密集的工作负载，节点独立分配带来的空间和 cache 成本会盖过常数时间插入的收益。

贯穿例子中的 ready.push_back 每次创建独立节点。Record::payload 的字符串资源由 Record 自己管理，节点存储由 ready 的 allocator 管理。用户保存 auto it = std::next(ready.begin()) 时，it 指向的是某个节点位置；它不持有节点所有权，节点被 erase 后这个 iterator 才失效。

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

insert、erase 和 splice 的共同点是局部修改链表链接；它们的差别在于是否创建或销毁元素。insert 创建新节点并接入链表，erase 摘除节点并销毁元素，splice 把已有节点从一个链表摘下再接入另一个链表。这个差别决定了 splice 的价值：它能改变元素所属容器和顺序关系，同时保留元素对象本身。

先看 insert。在 position 前插入元素时，已有节点的位置对象不需要更新。position 仍指向原来的节点，之前指向前驱节点的 iterator 也仍指向原来的节点。新返回的 iterator 指向新节点。标准草案对 list 插入的备注是“不影响 iterator 和引用有效性”，这不是额外优化，而是节点式布局自然带来的结果。

再看 erase。擦除一个节点时，只有指向该节点的 iterator、引用和指针失效；其他节点地址没有变化。erase 返回被删位置之后的 iterator，这个返回值用于在循环中安全推进。

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

这个循环的安全点是只在 erase 返回后继续使用新 iterator。被删除的旧 it 已经指向被销毁元素，继续解引用或递增都会进入无效位置。其他 iterator 仍可使用，但被删元素对应的引用、指针和 iterator 必须全部视为失效。

splice 是 list 区别于连续容器的核心操作。它的语义是 destructive move：节点从源链表离开，接入目标链表；元素对象本身保持在原节点中。标准草案明确说 splice 会把元素从一个 list 移到另一个 list，被移动元素的指针、引用和 iterator 继续指向同一元素，只是现在表现为目标链表中的 iterator；同时，splice 在跨容器时要求 allocator 比较相等，list.ops 的 splice 条目 给出了这些前置条件和效果。

贯穿例子中这行代码执行的是单节点迁移：

delayed.splice(delayed.begin(), ready, it);

执行前，it 指向 ready 中的第二个节点。执行后，那个节点成为 delayed 的第一个元素。it 仍指向同一个 Record，但它现在属于 delayed。ready 的大小减少，delayed 的大小增加。这个过程不构造新的 Record，也不析构旧的 Record，所以 payload 中的字符串资源没有被拷贝或移动。

单节点 splice 的指针路径可以写成两段。第一段从源链表摘除节点，第二段插入目标位置前。

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 需要比较相等；否则节点由哪个 allocator 分配、未来由哪个 allocator 释放会失去一致性，标准把这类情况放入未定义行为边界。第二，区间 splice 不能把目标位置放进被移动区间内部；这种重叠会破坏“摘下再接入”的节点范围语义。第三，同一链表内部移动单个节点时，目标位置等于当前节点或当前节点的下一个位置，结果保持原样。

splice 的复杂度也和重连范围有关。整个链表或单个节点迁移可以常数时间完成；跨链表区间迁移通常需要线性时间，因为实现需要计算被移动区间的元素数量来维护 size()。同一链表内的区间重排可以只改边界指针，但真实实现还要满足标准要求和自身大小缓存策略。

这一节的判断顺序可以固定下来：看到 insert，检查是否创建节点和构造元素；看到 erase，检查哪个节点被销毁；看到 splice，检查 allocator 是否相等、位置是否有效、iterator 后续归属哪个链表。这样读源码时不会把节点迁移误判成元素移动。

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

list 提供成员级 merge、sort、reverse，原因在于普通 <algorithm> 版本无法充分利用链表节点重连。std::sort 需要 random access iterator，list 只有 bidirectional iterator；即使使用能处理前向或双向范围的算法，也通常会围绕元素赋值或外部缓冲展开。list 的成员算法可以直接移动节点链接，在重排顺序时减少 T 的移动、拷贝和赋值。

merge 的前提是两个输入链表都已经按照同一个比较器排序。它把两个有序链表合成一个有序链表，节点从源链表迁入目标链表，源链表最终为空。标准草案说明 merge 要求两个链表对比较器有序，并且 allocator 比较相等；移动过来的元素保持原对象，相关 iterator 后续表现为目标链表中的 iterator；比较次数最多为 size() + x.size() - 1，操作稳定，且没有元素被拷贝，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 中原来指向 2 或 4 的 iterator 仍指向对应 Record，但这些 iterator 现在属于 a 的序列语境。Record 的 payload 没有通过拷贝构造或移动构造转移；链表只是改变节点之间的关系。

sort 是 list 的另一个典型链表算法。标准规定它按 operator< 或比较器排序，比较次数约为 N log N，稳定，并且不影响 iterator 和引用有效性；如果比较器抛异常，容器中的元素顺序处于未指定状态，但元素仍由容器管理。常见实现会使用归并排序思路，因为归并天然适合链表：拆分链表、递归或迭代合并、通过重连节点产生有序结果。

贯穿例子中的 ready.sort() 会重排节点顺序，让 id 小的记录排在前面。由于排序通过节点重连完成，保存到元素的引用仍指向同一个 Record。不过 iterator 的“相对遍历顺序”会变化：原来 ++it 走到哪个节点，排序后可能走向另一个节点。这里要区分“iterator 是否仍有效”和“iterator 在新顺序中相邻关系是否保持”。

reverse 更直接。它不比较元素，也不构造或销毁元素，只需要把每个节点的 prev 和 next 交换，然后调整哨兵方向。标准草案说明 reverse 线性时间执行，并且不影响 iterator 和引用有效性。贯穿例子中的 ready.reverse() 执行后，每个 iterator 仍指向原节点，但从 begin() 开始遍历看到的顺序已经完全反过来。

链表级算法的工程结论是：当对象移动成本高、需要频繁稳定地重排已有节点、并且算法可以通过比较和链接完成时，list 的成员算法有意义。当主要工作是按下标访问、批量连续扫描、排序后只关心值序列，连续容器往往更合适。list::sort 减少元素移动，不等于总性能稳定优于 std::sort(vector)；连续内存带来的 cache locality、分支预测和更少分配，常常让 vector 在真实负载中胜出。

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

list 的性能边界来自节点式布局。它把局部插入和删除成本压缩到指针重连，却把遍历成本、空间成本和分配成本摊到每个元素上。判断是否使用 list 时，应先看工作负载是否真的围绕“已知位置的节点级修改”展开；如果位置仍要从头遍历查找，常数时间插入无法抵消线性定位成本。

随机访问缺失是最直观的边界。list 没有 operator[] 和 at，标准草案也把这两个接口列为 list 没有提供的随机访问成员。std::next(list.begin(), n) 可以到达第 n 个元素，但它需要执行 n 次递增。代码写成 std::next 后语法看起来简洁，成本仍是链式跳转。

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

cache miss 是更隐蔽的边界。连续容器把相邻元素放在相邻地址，顺序遍历时 CPU 能更有效地预取后续 cache line。list 的节点可能分散在堆上，每次 node->next 都可能跳到不相邻地址。每个节点还带着两个指针，64 位平台上前驱和后继通常就是 16 字节额外开销；如果 T 很小，指针和分配器元数据可能比元素本身更重。

和 vector 比较时，同一组维度应保持一致：所有权、修改位置、访问模式、iterator 稳定性、内存局部性、异常安全。vector 拥有连续存储，随机访问和顺序扫描优秀；中间插入会移动后续元素，扩容会搬迁整段存储并让 iterator 大面积失效。list 拥有独立节点，已知位置插入和删除稳定；它缺少随机访问，遍历需要逐节点跳转，节点分配频繁。

和 deque 比较时，关键差异是分段连续与节点独立。deque 支持随机访问和两端扩展，内部通过块和 map 控制结构定位元素；中间插入删除仍会牵涉元素移动和复杂失效规则。list 支持任意位置稳定插入删除，但没有常数时间下标定位。一个任务如果主要在两端入队出队，deque 通常更直接；如果主要把已定位节点从任意位置摘出、插入、合并，list 才进入候选。

和 forward_list 比较时，list 用一个额外前驱指针换来双向遍历、尾部操作和当前位置前插入能力。forward_list 每个节点通常只保存后继指针，空间更紧，但很多修改必须持有前驱位置，接口围绕 before_begin、insert_after、erase_after 展开。需要双向遍历或成员 splice 的自然语义时，list 更顺手；只做单向扫描和低空间链式结构时，forward_list 更接近最小模型。

工程选型可以使用下面的顺序。先确认是否需要按下标访问或高吞吐连续扫描；需要时优先考虑 vector 或 deque。再确认插入删除的位置是否已经由 iterator 持有；如果仍要线性查找，list 的局部修改优势会被定位成本抵消。接着确认元素是否昂贵到值得通过节点重连减少移动；如果元素很小，节点开销会更明显。最后确认 iterator 稳定性是否是接口契约的一部分；如果外部长期保存元素位置，list 的稳定性才成为硬收益。

13.6 intrusive list 思想与 mini list 实现

intrusive list 的思想是把链接字段放进业务对象本身，由对象携带 prev 和 next。标准 std::list<T> 是非侵入式容器：节点由容器分配，T 存在节点内部，业务类型不需要知道链表结构。侵入式链表则让对象直接成为链表节点的一部分，常见于内核、游戏引擎、缓存淘汰队列和对象池等场景。

两种设计的所有权边界不同。非侵入式 std::list<T> 拥有元素对象，擦除节点时销毁 T。侵入式链表通常只组织已经存在的对象，摘链不等于销毁对象；对象生命周期由外部系统管理。这个边界能解释为什么标准库选择非侵入式 list：它符合 STL 容器的值语义、allocator 模型和元素所有权规则。侵入式链表适合更底层的资源管理场景，但它把链接状态暴露进业务对象，要求调用者严格管理对象是否已经入链、何时出链和销毁顺序。

下面的 mini list 展示非侵入式链表的最小实现路径。它有哨兵节点、双向 iterator、push_back、insert、erase 和析构清理。为了突出节点关系，它使用 new / delete，没有实现 allocator、异常安全 guard、拷贝控制和完整 const iterator；因此它是教学代码，不能替代生产容器。

#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_ 开始。它让空链表和非空链表共享同一套插入、删除逻辑。begin() 返回哨兵后继，end() 返回哨兵本身。iterator 只保存 node_base*，解引用时向下转型到 node* 并访问 value。emplace 先用 new node(...) 构造节点和元素，再调用 link_before 提交链接。erase 先保存后继节点，再摘链、删除节点、返回后继 iterator。

mini list 也暴露了真实 std::list 必须补齐的工程点。它缺少 allocator traits，因此不能表达用户定制内存策略；它缺少拷贝构造、移动构造和赋值，因此没有完整值语义；它没有异常安全 guard，如果 link_before 前的构造成功而后续扩展逻辑抛异常，就需要专门清理；它没有 const iterator 和 size 缓存，接口覆盖范围有限。这些缺口正好对应标准库源码中看起来繁琐的部分：标准容器要把节点模型、对象生命周期、allocator、异常安全和 iterator 语义全部组合起来。

把 std::list、侵入式链表和 mini list 放在一起看，可以得到一个稳定判断：链表结构的核心不是 API 名称，而是节点链接和对象生命周期的所有权边界。std::list 把链接字段藏在容器节点里，提供 STL 容器语义；侵入式链表把链接字段放进对象，换取更底层的控制；mini list 展示了 prev / next、哨兵和 iterator 如何组成最小可运行模型。

最小自检任务

阅读下面代码，判断四个问题：it_ready 和 it_delayed 在每一步后是否仍有效；Record 对象在哪些操作中被构造、移动、拷贝或析构；delayed.splice 之后 it_ready 属于哪个链表语境；最后应该选择 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();

答案要点

it_ready 初始指向 ready 中 id == 1 的节点。splice 后该节点迁移到 delayed 的末尾，it_ready 仍指向同一个 Record，但它现在表现为 delayed 的 iterator。这个迁移不构造、不移动、不拷贝、不析构 Record，核心动作是从 ready 摘下节点并接到 delayed.end() 前。

it_delayed 初始指向 delayed 中 id == 9 的节点。splice 不影响这个节点的地址和有效性。随后 ready.sort() 只重排 ready 的节点，和 delayed 中的 it_delayed 无关。delayed.erase(it_delayed) 销毁 id == 9 的 Record，释放对应节点，并让 it_delayed 失效。delayed.reverse() 不影响剩余元素 iterator 和引用有效性，但已经失效的 it_delayed 仍不可使用。

这段逻辑适合用 list 的前提是外部已经持有要迁移的 iterator，并且业务价值来自节点级迁移和 iterator 稳定性。如果实际流程需要频繁按下标访问、排序大量小对象、连续扫描为主，vector 往往更合适；即使中间插入删除看起来方便，也要把定位成本、节点分配、cache miss 和额外指针开销计入判断。

本章知识点总结

• 节点顺序：list 的元素顺序由节点之间的 prev / next 链接表达，容器通常通过哨兵节点统一空链表和边界状态。
• 迭代器能力：list iterator 通常保存节点指针，支持双向移动，但下标式随机访问需要线性推进。
• 插入路径：单元素插入先分配并构造新节点，再把节点接入目标位置前，提交点是指针链接。
• 擦除路径：单元素擦除摘除节点、析构元素并释放节点存储，只让被擦除元素对应的位置对象失效。
• allocator 边界：list 的 allocator 需要服务内部节点分配，跨链表 splice 和 merge 要求相关 allocator 比较相等。
• splice 语义：splice 迁移已有节点，保留元素对象本身，相关引用、指针和 iterator 继续指向同一元素但归属目标链表语境。
• 算法重连：merge、sort 和 reverse 能通过节点重连调整顺序，减少元素移动，并保持未擦除元素的位置对象有效。
• 排序边界：list::sort 稳定并使用约 N log N 次比较，但比较器抛异常时元素顺序处于未指定状态。
• 性能代价：list 用局部修改稳定性换取额外指针、频繁节点分配、线性定位和较弱内存局部性。
• 容器选型：需要随机访问和连续扫描时优先考虑 vector 或 deque；需要已定位节点的稳定摘链、插链和合并时再考虑 list。
• 侵入式边界：侵入式链表把链接字段放进业务对象并由外部管理生命周期，std::list 把节点和生命周期责任封装进容器。
• mini 实现：最小 list 由哨兵、节点、双向 iterator、插入链接和擦除摘链组成，标准库实现还要补齐 allocator、异常安全和值语义。