前言std::list是标准库提供的双向链表。每个节点单独分配节点之间用前驱、后继两个指针相连因此任意位置插入删除都是 O(1)代价是不能随机访问遍历时的内存局部性也不如连续容器。常见误解有三个。第一以为「链表插入删除快」就代表所有场景都该用list忽略了定位插入位置本身要 O(n) 遍历而且每个节点一次分配、缓存命中率低。第二把std::sort直接套在list上编译失败——std::sort要求随机访问迭代器list只提供双向迭代器。第三以为unique能去掉所有重复元素实际上它只删除相邻的重复通常要先sort。本文按结构特性、常用操作、专属算法、容器选择四部分讲代码以 C17 为准。一、结构与迭代器特性std::list的每个元素存放在独立节点里节点还保存前后指针。它提供双向迭代器bidirectional iterator支持、--不支持 n、- n、比较。要移动迭代器用std::advance、std::next、std::prev它们对链表是线性走步。C11 起list::size()要求常数时间实现通常在容器里维护一个计数更早的标准允许线性。list不提供operator[]、at()、data()也没有reserve()——它本来就不是连续存储。每个节点除了数据还要存两个指针外加分配器的开销所以同样元素数量下list的内存占用通常明显高于vector。这是「O(1) 插入」的代价。二、构造与基本操作list支持初始化列表构造、区间构造、n个相同值构造以及拷贝/移动构造。常用成员包括push_front、push_back、pop_front、pop_back、emplace_front、emplace_back、insert、emplace、erase、clear、resize、assign。// 适用于 C17#include iostream#include listint main() {std::listint values{1, 2, 3};values.push_front(0);values.emplace_back(4);auto it values.begin();std::advance(it, 2); // 不能写 it 2it values.insert(it, 99); // insert 返回新元素的迭代器std::cout *it \n;it values.erase(it); // 删除 99返回下一个位置std::cout *it \n;for (int v : values) std::cout v ;std::cout \n;}insert不会让其他迭代器失效erase只让被删元素的迭代器失效其余迭代器保持有效。这与vector很不一样vector扩容会让所有迭代器、指针、引用失效。也正因如此遍历中删除元素要写成it lst.erase(it);不能erase之后继续it。emplace系列把参数直接传给元素构造函数少一次临时对象对int看不出差别对自定义类型有意义。assign(count, value)和assign(first, last)会先清空再重新填入适合复用同一个容器对象避免反复构造销毁。resize(n)在变长时插入值初始化的元素变短时删除尾部元素对list来说resize不需要搬移但每个新节点仍是一次独立分配。clear()删除所有元素但保留容器对象本身之后可以继续使用。区间形式的erase(first, last)返回last可以一次删除一段。注意last是开区间端点不删除。对链表来说按区间删除仍然是逐个节点释放复杂度与区间长度成正比不会因为「知道首尾」就变成 O(1)。三、list 专属操作splice、merge、sort、unique这几个成员函数是list相对于其他容器的主要优势它们直接操作节点指针。// 适用于 C17#include iostream#include listint main() {std::listint a{3, 1, 2, 2, 4};a.sort(); // 成员函数排序稳定a.unique(); // 删除相邻重复排序后才等价于全局去重a.remove_if([](int x) { return x % 2 0; });std::listint b{9, 8};a.splice(a.end(), b); // 把 b 的全部节点接到 a 末尾b 变为空for (int x : a) std::cout x ;std::cout \n;}splice有三种形式整条链拼接到位置pos、拼接单个元素、拼接一个区间。它不复制、不移动元素只改指针因此原来指向被拼接元素的迭代器仍然有效只是所属容器变了。整条链的splice是常数时间跨容器拼接一个区间时标准给出的复杂度与区间长度相关使用前最好确认所用标准的措辞。C11 起两个list的分配器不相等时进行splice是 UB容器默认分配器时通常没有问题。merge把另一条已排序的链合并进来稳定且不复制节点。标准要求调用前两条链都有序对无序输入标准不保证结果不要拿它当「任意合并」用。sort是成员函数不是std::sort。它通常是归并实现稳定复杂度 O(n log n)只改指针不移动元素。unique删除相邻重复可以传二元谓词自定义「相等」如果不先排序它只能去掉连续出现的重复。remove(value)和remove_if(pred)会删除所有匹配元素内部也是遍历加 erase复杂度 O(n)。四、什么时候用 list操作std::liststd::vector随机访问不支持O(1)头部插入O(1)O(n)中间插入已有位置O(1)O(n)按值查找O(n)O(n)扩容不适用可能搬移全部元素迭代器失效仅被删元素扩容时全部失效内存局部性差好每元素额外开销两个指针 分配头通常无经验规则是数据量小、以遍历和随机访问为主用vector需要在已知位置频繁插入删除、或需要splice把节点在容器间搬家才考虑list。如果只是「频繁在头部插入」std::deque往往比list更合适因为它的块状存储仍有不错的局部性。在没有实际测量之前不要仅凭复杂度表就断定链表更快节点分配、指针跳转和缓存未命中都可能把 O(1) 的理论优势抵消掉。常见坑点❌lst[0]或lst.at(0)访问元素。✅ 用迭代器*lst.begin()需要下标就换vector/deque。❌it 1移动链表迭代器。✅ 用it、std::next(it)、std::advance(it, n)。❌std::sort(lst.begin(), lst.end())。✅ 用成员函数lst.sort()它稳定且只改指针。❌ 遍历中lst.erase(it); it;迭代器已失效。✅it lst.erase(it);❌ 以为unique会删除所有重复。✅ 先sort再unique或改用set/unordered_set去重。❌ 把未排序的两条链直接merge。✅ 先分别sort再merge或者用splice加统一排序。❌ 认为splice会复制元素、原容器仍保留。✅splice转移节点源容器不再拥有这些元素。❌ 用list存大量小对象并频繁遍历忽略缓存不友好。✅ 评估vector/deque必要时先做性能测量再决定。总结主题结论结构双向链表节点独立分配双向迭代器插入删除已知位置 O(1)定位仍要 O(n)专属操作splice、merge、sort、unique、remove_if迭代器插入不影响删除只影响被删元素适用场景频繁中间增删、节点跨容器转移std::list不是一个「更快的 vector」而是一个「用空间和局部性换节点操作」的容器。真正该用它的场景并不多需要splice在容器间零拷贝搬节点或者迭代器稳定性比遍历速度更重要。其余时候先考虑vector和deque通常能得到更简单也更快的代码。
前言std::list是标准库提供的双向链表。每个节点单独分配节点之间用前驱、后继两个指针相连因此任意位置插入删除都是 O(1)代价是不能随机访问遍历时的内存局部性也不如连续容器。常见误解有三个。第一以为「链表插入删除快」就代表所有场景都该用list忽略了定位插入位置本身要 O(n) 遍历而且每个节点一次分配、缓存命中率低。第二把std::sort直接套在list上编译失败——std::sort要求随机访问迭代器list只提供双向迭代器。第三以为unique能去掉所有重复元素实际上它只删除相邻的重复通常要先sort。本文按结构特性、常用操作、专属算法、容器选择四部分讲代码以 C17 为准。一、结构与迭代器特性std::list的每个元素存放在独立节点里节点还保存前后指针。它提供双向迭代器bidirectional iterator支持、--不支持 n、- n、比较。要移动迭代器用std::advance、std::next、std::prev它们对链表是线性走步。C11 起list::size()要求常数时间实现通常在容器里维护一个计数更早的标准允许线性。list不提供operator[]、at()、data()也没有reserve()——它本来就不是连续存储。每个节点除了数据还要存两个指针外加分配器的开销所以同样元素数量下list的内存占用通常明显高于vector。这是「O(1) 插入」的代价。二、构造与基本操作list支持初始化列表构造、区间构造、n个相同值构造以及拷贝/移动构造。常用成员包括push_front、push_back、pop_front、pop_back、emplace_front、emplace_back、insert、emplace、erase、clear、resize、assign。// 适用于 C17#include iostream#include listint main() {std::listint values{1, 2, 3};values.push_front(0);values.emplace_back(4);auto it values.begin();std::advance(it, 2); // 不能写 it 2it values.insert(it, 99); // insert 返回新元素的迭代器std::cout *it \n;it values.erase(it); // 删除 99返回下一个位置std::cout *it \n;for (int v : values) std::cout v ;std::cout \n;}insert不会让其他迭代器失效erase只让被删元素的迭代器失效其余迭代器保持有效。这与vector很不一样vector扩容会让所有迭代器、指针、引用失效。也正因如此遍历中删除元素要写成it lst.erase(it);不能erase之后继续it。emplace系列把参数直接传给元素构造函数少一次临时对象对int看不出差别对自定义类型有意义。assign(count, value)和assign(first, last)会先清空再重新填入适合复用同一个容器对象避免反复构造销毁。resize(n)在变长时插入值初始化的元素变短时删除尾部元素对list来说resize不需要搬移但每个新节点仍是一次独立分配。clear()删除所有元素但保留容器对象本身之后可以继续使用。区间形式的erase(first, last)返回last可以一次删除一段。注意last是开区间端点不删除。对链表来说按区间删除仍然是逐个节点释放复杂度与区间长度成正比不会因为「知道首尾」就变成 O(1)。三、list 专属操作splice、merge、sort、unique这几个成员函数是list相对于其他容器的主要优势它们直接操作节点指针。// 适用于 C17#include iostream#include listint main() {std::listint a{3, 1, 2, 2, 4};a.sort(); // 成员函数排序稳定a.unique(); // 删除相邻重复排序后才等价于全局去重a.remove_if([](int x) { return x % 2 0; });std::listint b{9, 8};a.splice(a.end(), b); // 把 b 的全部节点接到 a 末尾b 变为空for (int x : a) std::cout x ;std::cout \n;}splice有三种形式整条链拼接到位置pos、拼接单个元素、拼接一个区间。它不复制、不移动元素只改指针因此原来指向被拼接元素的迭代器仍然有效只是所属容器变了。整条链的splice是常数时间跨容器拼接一个区间时标准给出的复杂度与区间长度相关使用前最好确认所用标准的措辞。C11 起两个list的分配器不相等时进行splice是 UB容器默认分配器时通常没有问题。merge把另一条已排序的链合并进来稳定且不复制节点。标准要求调用前两条链都有序对无序输入标准不保证结果不要拿它当「任意合并」用。sort是成员函数不是std::sort。它通常是归并实现稳定复杂度 O(n log n)只改指针不移动元素。unique删除相邻重复可以传二元谓词自定义「相等」如果不先排序它只能去掉连续出现的重复。remove(value)和remove_if(pred)会删除所有匹配元素内部也是遍历加 erase复杂度 O(n)。四、什么时候用 list操作std::liststd::vector随机访问不支持O(1)头部插入O(1)O(n)中间插入已有位置O(1)O(n)按值查找O(n)O(n)扩容不适用可能搬移全部元素迭代器失效仅被删元素扩容时全部失效内存局部性差好每元素额外开销两个指针 分配头通常无经验规则是数据量小、以遍历和随机访问为主用vector需要在已知位置频繁插入删除、或需要splice把节点在容器间搬家才考虑list。如果只是「频繁在头部插入」std::deque往往比list更合适因为它的块状存储仍有不错的局部性。在没有实际测量之前不要仅凭复杂度表就断定链表更快节点分配、指针跳转和缓存未命中都可能把 O(1) 的理论优势抵消掉。常见坑点❌lst[0]或lst.at(0)访问元素。✅ 用迭代器*lst.begin()需要下标就换vector/deque。❌it 1移动链表迭代器。✅ 用it、std::next(it)、std::advance(it, n)。❌std::sort(lst.begin(), lst.end())。✅ 用成员函数lst.sort()它稳定且只改指针。❌ 遍历中lst.erase(it); it;迭代器已失效。✅it lst.erase(it);❌ 以为unique会删除所有重复。✅ 先sort再unique或改用set/unordered_set去重。❌ 把未排序的两条链直接merge。✅ 先分别sort再merge或者用splice加统一排序。❌ 认为splice会复制元素、原容器仍保留。✅splice转移节点源容器不再拥有这些元素。❌ 用list存大量小对象并频繁遍历忽略缓存不友好。✅ 评估vector/deque必要时先做性能测量再决定。总结主题结论结构双向链表节点独立分配双向迭代器插入删除已知位置 O(1)定位仍要 O(n)专属操作splice、merge、sort、unique、remove_if迭代器插入不影响删除只影响被删元素适用场景频繁中间增删、节点跨容器转移std::list不是一个「更快的 vector」而是一个「用空间和局部性换节点操作」的容器。真正该用它的场景并不多需要splice在容器间零拷贝搬节点或者迭代器稳定性比遍历速度更重要。其余时候先考虑vector和deque通常能得到更简单也更快的代码。
