【C++】 初阶篇 STL list的使用

前言

这篇笔记是我的实践记录:从节点、迭代器到容器接口,一步步还原list的核心逻辑,把 “用容器” 变成 “懂容器”。

一、list的介绍

list是 STL 中支持在任意位置高效(常数时间)插入、删除的双向迭代序列式容器,底层基于带头双向链表实现 —— 每个元素存于独立节点,通过指针连接前后元素;它和forward_list类似但后者是单链表、仅支持前向迭代;和array、vector、deque相比,list的插入删除效率更优,但缺点是不支持随机访问(访问第 n 个元素需线性遍历),且每个节点的指针会占用额外空间(对存储小元素的大list影响较明显)。

二、list的常用接口及其使用

2.1 构造函数

构造函数 (constructor)接口说明
list (size_type n, const value_type& val = value_type())构造的 list 中包含 n 个值为 val 的元素
list()构造空的 list
list (const list& x)拷贝构造函数
list (InputIterator first, InputIterator last)用迭代器区间构造 list

2.2 增删查改

函数声明接口说明
push_front在 list 首元素前插入值为 val 的元素
pop_front删除 list 中第一个元素
push_back在 list 尾部插入值为 val 的元素
pop_back删除 list 中最后一个元素
insert在 list position 位置中插入值为 val 的元素
erase删除 list position 位置的元素
swap交换两个 list 中的元素
clear清空 list 中的有效元素
//尾插l1.push_back(0);l1.push_back(1);l1.push_back(2);for(autov:l1){cout<<v<<" ";}cout<<endl;//头插l1.push_front(-1);for(autov:l1){cout<<v<<" ";}cout<<endl;//头删l1.pop_front();for(autov:l1){cout<<v<<" ";}cout<<endl;//在pos处插入//先来一个迭代器后面我们具体讲list<int>::iterator it1=l1.begin();//++it就可以在开始的下一个位置插入l1.insert(++it1,999);for(autov:l1){cout<<v<<" ";}cout<<endl;l1.erase(--it1);for(autov:l1){cout<<v<<" ";}cout<<endl;for(autov:l2){cout<<v;}cout<<endl;l1.swap(l2);for(autov:l1){cout<<v<<" ";}cout<<endl;for(autov:l2){cout<<v<<" ";}cout<<endl;l1.clear();for(autov:l1){cout<<v<<" ";}cout<<endl;

  • swap接口,为了避免因使用std::swap交换效率低下(需要拷贝),list重载了swap,这个重载的底层是交换两个链表的指针。
  • list没有重载find,需要调用std::find。

2.3list特殊接口

除了上述 STL 容器基本都有的一般接口外,list还提供一些独有的特殊操作接口,如下:

函数声明接口说明
splice将 list1 中的元素转移到 list2 中
remove移除 list 中的指定元素
unique链表去重
merge合并两个链表
sort链表排序
reverse链表逆置

2.3.1 splice 接口

有两种使用方式:

  1. 从一个list剪切到另外一个list的一个位置前面
cout<<"l1:";for(autov:l1){cout<<v;}cout<<endl;cout<<"l2:";for(autov:l2){cout<<v;}cout<<endl;l1.splice(l1.begin(),l2);cout<<"l1:";for(autov:l1){cout<<v;}cout<<endl;cout<<"l2:";for(autov:l2){cout<<v;}cout<<endl;

  1. 从自身的某个位置开始剪切到自身的某个位置前面。
// splice( 插入位置, 源链表, 源区间起点, 源区间终点 )lt.splice(pos,source,first,last);

2.3.2 remove 接口

通过元素的值来移除元素。

for(autov:l2){cout<<v;}cout<<endl;l2.remove(6);for(autov:l2){cout<<v;}cout<<endl;

2.3.3 unique 接口

去重要求链表有序,原因是底层是默认相同的数据被放在一起。

for(autov:l2){cout<<v;}cout<<endl;l2.unique();for(autov:l2){cout<<v;}cout<<endl;

2.3.4 merge 接口

合并链表,需要两个链表有序,底层有点类似于归并排序的逻辑,双指针遍历两个链表找小插入再返回拷贝。被合并的list会变空。

list<int>l1;list<int>l2;l1.push_back(1);l1.push_back(3);l1.push_back(5);l1.push_back(7);l2.push_back(0);l2.push_back(2);l2.push_back(4);l2.push_back(6);l2.push_back(8);cout<<"l1:";for(autov:l1){cout<<" "<<v;}cout<<endl;cout<<"l2:";for(autov:l2){cout<<" "<<v;}cout<<endl;l1.merge(l2);cout<<"l1:";for(autov:l1){cout<<" "<<v;}cout<<endl;cout<<"l2:";for(autov:l2){cout<<" "<<v;}cout<<endl;

2.3.5 sort 接口

链表排序只能使用list提供的sort接口,而不能使用 algorithm 提供的sort接口,因为链表物理地址不连续,迭代器为双向迭代器,不支持 + - 操作,而算法库中的sort函数需要支持 + - 的随机迭代器;

list<int>l1;list<int>l2;l1.push_back(1);l1.push_back(3);l1.push_back(5);l1.push_back(7);l1.push_back(0);l1.push_back(2);l1.push_back(4);l1.push_back(6);l1.push_back(8);cout<<"l1:";for(autov:l1){cout<<" "<<v;}cout<<endl;l1.sort();cout<<"l1:";for(autov:l1){cout<<" "<<v;}cout<<endl;

2.3.6 reverse

cout<<"l1:";for(autov:l1){cout<<" "<<v;}cout<<endl;l1.reverse();cout<<"l1:";for(autov:l1){cout<<" "<<v;}cout<<endl;

2.3.7 总结

1、链表排序只能使用list提供的sort接口,而不能使用 algorithm 提供的sort接口,因为链表物理地址不连续,迭代器为双向迭代器,不支持 + - 操作,而算法库中的sort函数需要支持 + - 的随机迭代器;
2、链表去重之前必须保证链表有序,否则去重不完全;
3、两个有序链表合并之后仍然保存有序;

最后,虽然list提供了这些具有特殊功能的接口,它们也确实有一定的作用,但是实际上这些特殊接口使用频率非常低,包括sort接口(链表排序的效率太低)。

2.4list排序的性能分析

虽然链表排序只能使用list提供的sort接口,而不能使用 algorithm 提供的sort接口,但是其使用频率仍然非常低,这是由于链表排序的效率太低了,我们可以通过对比两组测试数据来直观地感受链表排序的效率。

测试一:vector排序与list排序性能对比

srand((size_t)time(0));constintN=1000000;//100万个数据vector<int>v;v.reserve(N);list<int>lt;for(inti=0;i<N;++i){autoe=rand();v.push_back(e);lt.push_back(e);}//vector sortintbegin1=clock();sort(v.begin(),v.end());intend1=clock();//list sortintbegin2=clock();lt.sort();intend2=clock();printf("vector sort:%d\n",end1-begin1);printf("list sort:%d\n",end2-begin2);

测试二:list直接进行排序与将数据拷贝到vector中使用vector排序后再将数据拷回list中性能对比

srand(time(0));constintN=1000000;//100万个数据list<int>lt1;list<int>lt2;for(inti=0;i<N;++i){autoe=rand();lt1.push_back(e);lt2.push_back(e);}//list sort -- lt1intbegin1=clock();lt1.sort();intend1=clock();// 将数据拷贝到vector中排序,排完以后再拷贝回来 -- lt2intbegin2=clock();vector<int>v;v.reserve(N);for(autoe:lt2)//拷贝{v.push_back(e);}sort(v.begin(),v.end());//排序lt2.assign(v.begin(),v.end());//拷贝intend2=clock();printf("list1 sort:%d\n",end1-begin1);printf("list2 sort:%d\n",end2-begin2);

可以看到,list sort的效率远低于vector sort,甚至于说,直接使用list sort的效率都不如先将数据拷贝到vector中,然后使用vector sort,排序之后再将数据拷贝回list中快;至此,我们也能明白为什么list sort接口使用得非常少了。

注:在工程中,在 release 版本下测试软件或算法性能得到的结果要比在 debug 版本下得到的结果具有参考意义。

三、list迭代器

3.1 迭代器类别

迭代器类别++–+-
Input(只读)✓✗✗✗
Output(只写)✓✗✗✗
Forward(单向)✓✗✗✗
Bidirectional(双向)✓✓✗✗
Random Access(随机)✓✓✓✓

迭代器有很多种类,如上,我们全部列举出来了。vector的迭代器是随机迭代器,支持 ++,–,+,- 多种操作。和vector和string不同,由于结构非连续问题,list的迭代器并非一个原生指针。所以list作为一个双向链表是一个双向迭代器。也就是说,list的迭代器不支持 + 和 - 操作。

由于是双向迭代器,所以list不能采用vector的方式来直接在中间插入数据。

迭代的类型会限制接口的访问:以下我们讲两个例子。首先是标准库的sort,由于sort的底层需要operator[]大量访问数据,所以只支持随机迭代器。

我们看看sort的底层代码:如你所见,使用了 - 操作符,自然不支持。

reverse:reverse的底层有使用 – 操作,所以只能支持双向迭代器。但是这里又要讲一个直接支持和间接支持的问题:

直接支持:如下,reverse直接支持双向迭代器。间接支持:随机迭代器可以用 --,所以reverse也支持随机迭代器的使用。

实际上可以理解为一种包含的关系,双向是一种特殊的单向。随机是一种特殊的双向/单向。

这也可被认为是一种继承 —— 子类是一种特殊的父类。(没有对应的直接类型,但是可以传递其以上任意父类)

3.2list迭代器失效问题

和vector不同,list进行insert操作后并不会产生迭代器失效问题,因为list插入的新节点是动态开辟的,同时由于list每个节点的物理地址是不相关的,所以插入的新节点并不会影响原来其他节点的地址;

但是list在erase之后会发生迭代器失效,因为list删除节点会直接将该节点释放掉,此时我们再访问该节点就会造成越界访问。

3.3list迭代器源码分析

  • list的迭代器底层不是原生指针,而是一个封装指针。原因是结构不连续,无法通过 C/C++ 内置的指针算术进行操作。这个封装指针的解引用、operator++、operator!=等等操作都需修改。

  • 此外,迭代器需要构造函数,因为在调用的时候不能再以一个指针的形态来简单调用了,得构造一个迭代器才能使用。(迭代器本身就是一个封装指针,所以不需要拷贝构造,浅拷贝够用)

//节点定义template<classT>struct__list_node{typedefvoid*void_pointer;void_pointer next;void_pointer prev;T data;};//迭代器定义typedef__list_iterator<T,T&,T*>iterator;typedef__list_iterator<T,constT&,constT*>const_iterator;//迭代器类template<classT,classRef,classPtr>struct__list_iterator{typedef__list_iterator<T,Ref,Ptr>self;typedef__list_node<T>*link_type;//节点的指针link_type node;//类成员变量__list_iterator(link_type x):node(x){}//将节点指针构造为类对象//... 使用运算符重载支持迭代器的各种行为self&operator++(){...}self&operator--(){...}Refoperator*()const{...}};

如上,我们为迭代器专门设计了一个__list_iterator类,然后在类内配合运算符重载、模板等操作使得迭代器支持指针的各种行为(至于这里为什么__list_iterator会有三个模板参数,我们会在后面模拟实现中具体解释,当前我们只需要理解其第一个模板参数T即可)。

相关新闻

车间班组标准化作业提质体系

车间班组标准化作业提质体系

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/11/19 5:38:20 阅读更多 →
ACORN算法的各种密码分析方法全面盘点

ACORN算法的各种密码分析方法全面盘点

ACORN算法的各种密码分析方法全面盘点ACORN算法作为CAESAR竞赛的最终入选算法之一&#xff0c;自提出以来受到了广泛的密码分析。目前针对它的密码分析方法已相当全面&#xff0c;涵盖了从数学结构到物理实现的多个层面。需要说明的是&#xff0c;现有攻击主要针对简化轮数的AC…

2026/11/15 22:04:25 阅读更多 →
超低功耗物联网芯片:从亚阈值电路到能量采集的全栈实现

超低功耗物联网芯片:从亚阈值电路到能量采集的全栈实现

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/11/18 3:56:26 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年&#xff0c;我大部分时间都在跟浏览器标签页打交道&#xff0c;直到第一次把桌面应用跑起来&#xff0c;才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词&#xff0c;最开始是在某段时间频繁出现在同事的讨论里&#xff0c;一个用HTML…

2026/11/18 13:59:04 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介&#xff1a;亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档&#xff0c;主要面向智能锁安装人员、终端用户及售后维护者&#xff0c;帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件&#xff0c;大小4.37MB&#xff0c;内容结构清晰&#xff…

2026/11/18 15:33:23 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统&#xff0c;整车要求空载跑到8m/s&#xff0c;电机转速已经拉到额定点&#xff0c;驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令&#xff0c;转速纹丝不动&#xff0c;三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/18 17:05:28 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年&#xff0c;用它写过嵌入式驱动、做过游戏服务端&#xff0c;也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词&#xff0c;我其实挺感慨的——这门语言的难点从来不是语法多&#xff0c;而是知识点之间的耦合太深…

2026/11/18 14:33:19 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介&#xff1a;亚太天能T109滑盖智能锁产品说明书以PDF格式发布&#xff0c;适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开&#xff0c;先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能&#xff0c;再给出完整安装步骤&…

2026/11/18 17:05:28 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历&#xff1a;翻开源码注释、论文摘要或者一份专业报告&#xff0c;每个字都认识&#xff0c;连在一起却像天书。想找人聊聊&#xff0c;身边要么没人懂&#xff0c;要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型&#xff0c;几秒钟之后&a…

2026/11/18 14:13:08 阅读更多 →

日新闻

周新闻

月新闻