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

前言

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

一、list的介绍

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

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

2.1 构造函数

2.2 增删查改

//尾插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还提供一些独有的特殊操作接口，如下：

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;

2. 从自身的某个位置开始剪切到自身的某个位置前面。

// 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 迭代器类别

迭代器有很多种类，如上，我们全部列举出来了。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即可）。