跳到主要内容 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 1 浏览
list 容器支持自定义内存分配器,底层采用带头双向循环链表结构。与 vector 不同,list 不支持下标访问 operator[],因为空间不连续。
遍历 list 不能使用下标,应使用迭代器或范围 for 循环。
#include <iostream>
#include <list>
using namespace std;
int main ()
{
list<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 ()
{
list<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 ()
{
list<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 ()
{
list<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 ()
{
list<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 ()
{
list<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 ;
}