list：节点稳定、splice 与局部性

常数时间的前提是已经找到位置

list 提供双向迭代器，没有随机访问下标。已知迭代器时，插入一个元素和删除该元素是常数时间；但从开头走到第 k 个位置仍需要线性步数。因此“链表中间删除快”省略了查找位置的成本，不能直接用于评估完整业务操作。

插入不使既有元素的迭代器和引用失效，删除只使被删除元素的句柄失效。常见实现以独立节点和前后链接组成链表，扫描时的指针追踪、节点分配及较差局部性可能超过移动小对象的成本。标准给出操作语义和复杂度，并不指定节点布局或某处理器上的缓存表现。

splice 转移的是元素身份

dst.splice(pos, src, it) 把一个元素放到目标位置之前，不复制或移动该元素对象。其引用和迭代器继续指向同一个对象，只是归属目标列表。这个性质适合维护已持有节点句柄的待办队列、分组或最近使用顺序，尤其适合不希望重新构造对象的场景。

整个列表转移与单元素转移是常数时间；范围转移在同一个列表内是常数时间，跨两个列表则是线性时间，不能因“只改几个链接”忽略标准复杂度。分配器必须比较相等。整表重载不能把自己作为来源；范围重载要求目标位置不在被转移范围内。

使用能利用节点结构的成员操作

std::sort 要求随机访问迭代器，不能用于 list；使用 list::sort，它提供稳定排序并保留元素迭代器。list::remove_if 真正删除节点，而通用 std::remove_if 只是通过移动赋值压紧逻辑范围，不会改变容器大小，也不利用链表节点的优势。

示例把待处理列表中的一项转入运行列表，验证地址、内容与两个列表的可见顺序。转移后不要再把该迭代器交给来源列表的 erase；其归属已经改变。若应用只是读入一批数字再排序，vector 往往是更简单的默认选择，只有节点稳定性或频繁拼接确实需要时再选择 list。

最低标准 C++11 · 完整程序 · 下载 .cpp

#include <cassert>
#include <iostream>
#include <iterator>
#include <list>
#include <string>

int main() {
    std::list<std::string> pending{"parse", "compile", "link"};
    std::list<std::string> running{"fetch"};
    auto job = std::next(pending.begin());
    const std::string* address = &*job;
    running.splice(running.end(), pending, job);
    assert(&*job == address && *job == "compile");
    assert((pending == std::list<std::string>{"parse", "link"}));
    assert((running == std::list<std::string>{"fetch", "compile"}));
    running.splice(running.begin(), running, job);
    assert(running.front() == "compile");
    auto next = running.erase(job);
    assert(next != running.end() && *next == "fetch");
    std::cout << pending.size() << ' ' << running.front() << '\n';
}

在本地编译

g++ -std=c++11 -Wall -Wextra -Wpedantic -pthread stl-list.cpp -o example && ./example

预期结果

2 fetch

CHECK YOUR UNDERSTANDING

合上答案，试着解释。

已持有 list 中某元素的迭代器 hit，需要将它变成首元素，同时保持外部引用有效。给出操作并说明成本。

继续查证

• 标准草案 [list.ops]：splice、remove、sort

标准草案链接会随工作草案更新；本文版本标记对应示例最低要求，不表示草案中的所有新规则都适用于旧标准。