跳到主要内容 C++ STL list 容器特性与常用接口解析 | 极客日志
C++ 算法
C++ STL list 容器特性与常用接口解析 本文介绍了 C++ STL 中 list 容器的底层结构（双向循环链表）、特性（不支持随机访问、O(1) 插入删除）及常用接口（insert, erase, sort, splice 等）。对比了 list 与 vector 的差异，解释了迭代器类型对算法选择的影响，并通过代码示例演示了正确用法及注意事项。
ServerBase 发布于 2026/3/29 更新于 2026/4/13
list 容器支持自定义内存分配器，底层采用带头双向循环链表结构。与 vector 不同，list 不支持下标访问 operator[]，因为空间不连续。
遍历 list 不能使用下标，应使用迭代器或范围 for 循环。
#include <iostream>
#include <list>
using namespace std;
int main ()
int > lt;
lt.push_back (1 );
lt.push_back (2 );
lt.push_back (3 );
lt.push_back (4 );
list<int >::iterator it = lt.begin ();
while (it != lt.end ())
{
cout << *it << " " ;
it++;
}
cout << endl;
for (auto e : lt)
{
cout << e << " " ;
}
cout << endl;
return 0 ;
}
1. list 的介绍及使用
1.1 list 的介绍
list 是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
list 的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
list 与 forward_list 非常相似：最主要的不同在于 forward_list 是单链表，只能朝前迭代，已让其更简单高效。
微信扫一扫，关注极客日志 微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
Markdown 转 HTML 将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
HTML 转 Markdown 将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
JSON 压缩 通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
与其他的序列式容器相比 (array, vector, deque)，list 通常在任意位置进行插入、移除元素的执行效率更好。
与其他序列式容器相比，list 和 forward_list 最大的缺陷是不支持任意位置的随机访问，比如：要访问 list 的第 6 个元素，必须从已知的位置 (比如头部或者尾部) 迭代到该位置，在这段位置上迭代需要线性的时间开销；list 还需要一些额外的空间，以保存每个节点的相关联信息 (对于存储类型较小元素的大 list 来说这可能是一个重要的因素)
1.2 list 的使用 list 中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为 list 中一些常见的重要接口。list 的头插和头删复杂度都为 O(1)。
从 string 之后，position 都变了，在 string 的部分都是用下标去插入，现在的位置都是迭代器，但是和 vector 还是有点区别的。比如下面的在第五个位置插入数据：
int main ()
int > lt;
lt.push_back (1 );
lt.push_back (2 );
lt.push_back (3 );
lt.push_back (4 );
lt.push_front (10 );
lt.push_front (20 );
auto it = lt.begin ();
for (size_t i = 0 ; i < 5 ; i++)
{
++it;
}
lt.insert (it, 100 );
for (auto e : lt)
{
cout << e << " " ;
}
cout << endl;
return 0 ;
}
这是 vector 和 list 的第一个差别，这种差别是迭代器的差别导致的，list 的插入代价是很低的，把前后位置的指向关系改变一下就可以了，排序都写到算法里面去了。
还有一种插入的场景，就是找到一个值，在它的前面插入一个数据。list 和 vector 都没有提供 find 接口。
对于 vector 来说用小于没有问题，但对于 list 来讲，迭代器中 end() 节点的地址不一定比 begin() 大，end() 的节点是有效数据的下一个位置，也就是哨兵位。
list 中的 insert 接口不存在迭代器失效的问题，比如我要在这个位置插入接点，没有扩容的问题，没有野指针的问题，没有位置改变的问题，因为不需要挪动数据。vector 在这个位置插入之前有两大问题，第一大问题就是扩容，第二大问题就是插入这个数据之后，位置往后挪，它的位置意义都变了。
erase 节点存在迭代器失效的问题，因为节点都没了。
算法中的 find，找到就返回这个节点，找不到就返回 end 节点。
int main ()
int > lt;
lt.push_back (1 );
lt.push_back (2 );
lt.push_back (3 );
lt.push_back (4 );
lt.push_front (10 );
lt.push_front (20 );
auto it = lt.begin ();
it = find (lt.begin (), lt.end (), 3 );
if (it != lt.end ())
{
lt.insert (it, 3 );
*it *= 100 ;
}
for (auto e : lt)
{
cout << e << " " ;
}
cout << endl;
it = find (lt.begin (), lt.end (), 3 );
if (it != lt.end ())
{
lt.insert (it, 30 );
*it *= 100 ;
}
for (auto e : lt)
{
cout << e << " " ;
}
cout << endl;
return 0 ;
}
int main ()
int > lt;
lt.push_back (1 );
lt.push_back (2 );
lt.push_back (3 );
lt.push_back (4 );
lt.push_front (10 );
lt.push_front (20 );
auto it = lt.begin ();
it = find (lt.begin (), lt.end (), 3 );
if (it != lt.end ())
{
lt.insert (it, 3 );
*it *= 100 ;
}
for (auto e : lt)
{
cout << e << " " ;
}
cout << endl;
it = find (lt.begin (), lt.end (), 3 );
if (it != lt.end ())
{
lt.erase (it);
*it *= 100 ;
}
for (auto e : lt)
{
cout << e << " " ;
}
cout << endl;
return 0 ;
}
int main ()
int > lt;
lt.push_back (1 );
lt.push_back (2 );
lt.push_back (3 );
lt.push_back (4 );
lt.push_front (10 );
lt.push_front (20 );
auto it = lt.begin ();
while (it != lt.end ())
{
if (*it % 2 == 0 )
{
it = lt.erase (it);
}
else
{
++it;
}
}
for (auto e : lt)
{
cout << e << " " ;
}
cout << endl;
return 0 ;
}
int main ()
int > lt1;
lt1. push_back (1 );
lt1. push_back (2 );
lt1. push_back (3 );
lt1. push_back (4 );
list<int > lt2;
lt2. push_back (10 );
lt2. push_back (20 );
lt2. push_back (30 );
lt2. push_back (40 );
for (auto e : lt1)
{
cout << e << " " ;
}
cout << endl;
for (auto e : lt2)
{
cout << e << " " ;
}
cout << endl;
lt1. swap (lt2);
for (auto e : lt1)
{
cout << e << " " ;
}
cout << endl;
for (auto e : lt2)
{
cout << e << " " ;
}
cout << endl;
return 0 ;
}
容器都是通过迭代器区间去访问的，比如这有一个容器，想在这一段查找，给这个容器的区间查找这个 val 就可以了。
list 中 sort 的价值大不大，库里面也有一个 sort，list 中也提供了一个 sort，有啥意义呢？编译报错了，有时候掉不调到库里面去了，就看这个库是谁的归属，那就是哪儿出错了，sort 这个库用这个迭代器我们不能用，因为 sort 这个库里面用到一个
，就一个点我们就知道了，sort 是快排，快排不能用这个东西，因为快排要做过参数取中，参数取中选其中一个值的时候，选中间那个值或者选另外一个值的时候，我直接要选那个位置，快排不适合，就是那个链表没办法适应这个场景。
所以大家仔细再看，如果我们单看算法，这些算法的名字有一些差异，他这个是函数模板，但是他在这个名字上面很有讲究，它的名字就暗示了应该传什么迭代器，这里就要迁移出一个知识讲一讲，然后再结合这这个说，迭代器从他的功能的角度是会分类的，从功能上来说，分为单向、双向、随机。功能上是什么呢？单向就只能++，双向可以++也可以--，随机是可以++、--、也可以+，也可以 -。
谁的迭代器就是典型的单向呢？单链表、哈希表。谁是双向迭代器呢？双向链表，其实也就是我们的 list，还有 map、set，也就是树。谁是随机迭代器呢？vector、string、双端队列 deque。它这的名字就暗示了你用哪种算法，reverse 就适合用双向，find 就适合用单向，sort 就适合用随机。这个地方对迭代器是一个隐式的分类，可以认为它是一个性质进行划分，这个性质跟容器的底层结构有关系。
谁可以调用这个 sort 算法呢，这个 sort 底层是快排，决定了他要用这个随机迭代器，随机是可以吊的，链表就不可以调，链表这里调就报错了，用这个算法就要看容器的迭代器到底是哪一种，能不能适应，我怎么知道我的容器是哪一种呢？这里是有说明的，它的迭代器的内容是什么，vector 和 string 可以用这个逆置，随机迭代器可以认为是一个特殊的双向迭代器，随机迭代器满足双向的要求，满足单向的要求，
，如果写这个，单向、双向、随机都可以用，写随机的就随机可以用，写双向的就双向、随机可以用，写单向的就单向、双向、随机都可以用。
set 底层就是更复杂的迭代器，也就是树了，forward_list 是单向迭代器，
排序应该用 vector，不应该用 list，vector 的效率远高于 list，
数据量越大，差距越大一些，list 排序终究还是要慢不少。如果我们真的要数据排序，我们不应该用链表，链表访问数据相比 vector 毕竟还是慢，list 底层用的是归并算法。所以说 list 的 sort 意义不大。
void test_op ()
srand (time (0 ));
const int N = 1000000 ;
vector<int > v;
v.reserve (N);
list<int > lt1;
for (int i = 0 ; i < N; ++i)
{
auto e = rand ();
v.push_back (e);
lt1. push_back (e);
}
int begin1 = clock ();
sort (v.begin (), v.end ());
int end1 = clock ();
int begin2 = clock ();
lt1. sort ();
int end2 = clock ();
printf ("vector sort:%d\\n" , end1 - begin1);
printf ("list sort:%d\\n" , end2 - begin2);
}
int main ()
test_op ();
return 0 ;
}
list 的作用是当排序值比较小的时候，list 排序才有价值。
void test_op ()
srand (time (0 ));
const int N = 100000 ;
vector<int > v;
v.reserve (N);
list<int > lt1;
list<int > lt2;
for (int i = 0 ; i < N; ++i)
{
auto e = rand ();
lt2. push_back (e);
lt1. push_back (e);
}
int begin1 = clock ();
for (auto e : lt1)
{
v.push_back (e);
}
sort (v.begin (), v.end ());
size_t i = 0 ;
for (auto & e : lt1)
{
e = v[i++];
}
int end1 = clock ();
int begin2 = clock ();
lt2. sort ();
int end2 = clock ();
printf ("vector sort:%d\\n" , end1 - begin1);
printf ("list sort:%d\\n" , end2 - begin2);
}
int main ()
test_op ();
return 0 ;
}
我们可以区分迭代器的类型，区分迭代器的类型有点复杂，叫做迭代器的萃取，就可以分辨出迭代器的类型。
merge 就是连个链表可以直接进行归并，归并有一个前提就是先有序，两个链表要先 sort 再 merge，这里还有另外一个东西叫仿函数，比较的仿函数的概念，仿函数在优先级队列再讲。
这个接口的本质是去重，去重也是有前提的，也是要先排序，如果不排序去重的话效率是很低的。
remove 就是 find 加 erase，remove 就是直接可以删。remove 唯一要注意的是如果这个值不存在会不会报错？
void text_x ()
int myints[] = { 17 ,89 ,7 ,14 };
std::list<int > mylist (myints, myints + 4 ) ;
mylist.remove (890 );
for (auto e : mylist)
{
cout << e << " " ;
}
cout << endl;
}
int main ()
text_x ();
return 0 ;
}
相当于 find，如果找到就删除了，没找到就啥也不干。
这个接口可以把一个链表的内容转移到另一个，它的转移是直接把节点拿走，就比如说有一个 a 链表，有一个 b 链表，直接把 a 链表的节点取下来直接插入到 b 链表，相当于 a 链表删除了数据，b 链表插入了数据，严格来说就是发生了转移。也可以转移到自己身上，但是别把范围区间重叠了。
int main ()
int myints[] = { 17 ,89 ,7 ,14 };
std::list<int > mylist1, mylist2;
std::list<int >::iterator it;
for (int i = 1 ; i <= 4 ; ++i)
mylist1. push_back (i);
for (int i = 1 ; i <= 3 ; ++i)
mylist2. push_back (i * 10 );
for (auto e : mylist1)
{
cout << e << " " ;
}
cout << endl;
for (auto e : mylist2)
{
cout << e << " " ;
}
cout << endl << endl;
it = mylist1. begin ();
++it;
mylist1. splice (mylist1. begin (), mylist1, ++mylist1. begin (), mylist1. end ());
for (auto e : mylist1)
{
cout << e << " " ;
}
cout << endl;
for (auto e : mylist2)
{
cout << e << " " ;
}
cout << endl;
return 0 ;
}
