【C++进阶(四)】STL大法--list深度剖析&list迭代器问题探讨

1. 前言

本质重点:

本章重点讲解list的接口函数的熟悉
并且讲解list迭代器失效的特性
最后讲解迭代器的功能分类以及
算法库函数中谁能用谁不能用

STL标准库中的list是一个

带头双向循环链表

和vector不同,list没有支持[ ]访问
以及resize和reserve容量相关的函数

这是因为list不能随机访问数据

并且list的迭代器的底层明显不是指针了

那它的底层到底是啥?

list会和vector一样有迭代器失效问题吗?

带着这些疑问,我们来进入今天的学习分享

2. list的使用

我们还是在网站:cplusplus中查询字典

和vector一样,list也有两个模板参数

但是第二个模板参数是和内存效率相关的

所以现在的学习暂时不用管它(它有缺省值)

list的使用分为以下几个阶段进行:

• list的构造,析构,拷贝构造函数
• list迭代器的使用
• list容量相关的操作
• list的增删查改

2.1 list的构造函数

list的构造函数:

第一个是无参构造,直接跳过
第二个是用n个val初始化list对象
第三个是用一段迭代器区间构造
第四个是用一个初始值构造

看起来平平无奇,来实操一下:

list<int> l1;//无参构造
list<int> l2(10,5);//用10个5初始化链表
vector<int> vv{1,2,3,4,5,6};
list<int> l3(vv.begin(),vv.end());//用迭代器区间初始化
list<char> l4('a');//用一个字符来初始化

list的拷贝构造和析构函数在使用

list时不会显示调用,所以将它们忽略掉

2.2 list迭代器的使用

虽然list的迭代器底层不是指针

但是可以把它理解为指针来使用

这四个函数都是老朋友了,不多介绍了

唯一值得注意的是下图:

begin和rend的指向相同
end和rbegin的指向相同

迭代器遍历链表:

vector<int> vv{1,3,5,7,9,11,13,15};
list<int> l(vv.begin(),vv.end());
auto it = l.begin();
while(it!=l.end())
{
  cout << *it<< " ";
  it++;
}

范围for遍历链表:

vector<int> vv{1,3,5,7,9,11,13,15};
list<int> l(vv.begin(),vv.end());
for(auto x : l)
{
  cout << x<< " ";
}

注:list不支持随机访问,不能用[]

一个小tips:

在写用迭代器遍历容器时,我们往往
会写it!=l.end(),而不是it<l.end()
这是因为在list中,空间并不连续,用小于
符号很大概率会出错,但是在string
和vector中,空间是连续的,用<也没问题

2.3 list容量相关操作

这里最简单,和vector一模一样

只有这四个函数接口比较常用!

2.4 list的增删查改

首先映入眼帘的头插/头删,尾插/尾删

这几个函数的意思很明了,直接跳过

insert插入:

insert函数要输入一个迭代去位置进行插入

可以插入一个数据或插入一段迭代器区间

erase删除:

erase函数可以删除一个迭代器的数据

或者删除一段迭代器区间

clear清空有效元素:

list不像vector一样有size和capacity

list的clear函数是将链表清空

(除头节点外)

增删查改实操:

vector<int> vv{1,5,10,15,20,100,120};
list<int> ll(vv.begin(),vv.end());
auto pos = find(ll.begin(),ll.end(),20);
ll.insert(pos,250);
ll.erase(ll.begin()+2);
ll.clear();

3. list迭代器失效问题探讨

由于list的底层是双向带头循环链表

所以插入操作时,pos指向的节点的

位置始终都是一个位置,它们只改变

链接关系,并不连续,所以插入操作

并不会导致list迭代器失效

list迭代器失效只在erase删除时才会发生

erase删除的位置在空间上是唯一的

这个位置的数据被删除后,只是改变了

数据的链接关系,然而此位置已经不在

原先的链表中了,再次使用会出错!

STL库的erase提供了返回值来解决问题:

会返回被删除位置的下一个位置的迭代器

以后可以这样写代码来避免错误:

list<int> ll{1,2,3,4,5,6,7,8};
auto it=ll.begin();
while(it!=ll.end())
{
  if((*it)%2==0)
  {
    it=erase(it);
  }
  else
  {
    it++;
  }
}

4. 算法库函数和list的关系

首先,迭代器从功能角度可以分类为:

1. 正向迭代器: forward_iterator
2. 双向迭代器: bidirectional_iterator
3. 随机迭代器: random_iterator

它们分别支持且仅支持:

1. 只支持++
2. 支持++和- -
3. 支持++,- -,+和-

常见的容器以及它们的迭代器类型:

4.1 算法库函数的迭代器类型

现在再来看算法库的sort函数:

它的函数模板支持的是随机迭代器

再来看看算法库的reverse函数:

它的函数模板支持的是双向迭代器

我先给出以下的结论:

1. 若函数模板给的随机迭代器
   则只能传有随机迭代器的容器
   
2. 若函数模板给的双向迭代器
   则可以传有随机或者双向迭代器的容器
   
3. 若函数模板给的单向迭代器
   则三种迭代器都可以传进来!
   

可以看出它支持向上兼容!

4.2 list不能使用的算法库函数

可见,list是双向迭代器,而sort函数的

函数模板是随机迭代器

所以库函数中的sort无法排序链表

但是仔细查阅字典可以发现:

list类自己实现了一个不同于算法库的排序

此排序专门用于排序list中的数据!

虽然list有自己的sort函数来排序
但是当数据很多时,list自我实现的
sort的效率低的惊人!甚至还不如
将list的数据导入vector容器
再在vector容器中使用算法库的排序
排完序再导入到list中,这一步骤快!

5. 总结以及拓展

总的来说list的使用和vector大同小异

当然,要掌握list,list的模拟实现是不可少的

list的模拟实现将在下一节分享给大家

本章笔记:

1. 请自行熟悉list接口函数
   
2. list的insert不会导致迭代器失效
   而erase会致使迭代器失效
   
3. 迭代器从功能上可以划分为三种
   它们向上兼容彼此
   
4. list不能使用算法库中的sort
   但list类中实现了专门排序链表的函数
   

拓展阅读:

迭代器相关拓展知识

🔎 下期预告:list的模拟实现以及对比vector的区别 🔍