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

    💓博主CSDN主页:杭电码农-NEO💓
     
    ⏩专栏分类:C++从入门到精通⏪
     
    🚚代码仓库:NEO的学习日记🚚
     
    🌹关注我🫵带你学习C++
      🔝🔝

    在这里插入图片描述

    链表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');//用一个字符来初始化

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    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++;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    范围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<< " ";
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

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

    一个小tips:

    在写用迭代器遍历容器时,我们往往
    会写it!=l.end(),而不是it
    这是因为在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();

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    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++;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

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

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

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

    它们分别支持且仅支持:

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

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

    容器迭代器功能
    vector随机迭代器
    list双向迭代器
    stack不支持迭代器
    queue不支持迭代器
    deque随机迭代器
    set / multiset双向迭代器
    map / multimap双向迭代器
    priority_queue不支持迭代器

    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的区别 🔍
  • 相关阅读:
    记录一个iOS沙盒使用的问题
    基于matlab统计Excel文件一列数据中每个数字出现的频次和频率
    IDEA版SSM入门到实战（Maven+MyBatis+Spring+SpringMVC) -为什么使用Maven
    UE4 Sequence添加基础动画效果 （05-蓝图触发Sequence）
    为何红黑树在B/B+树之上仍然占据重要地位？
    golang关于数量的总结
    基于STM32F103的HAL库手动配置FreeRTOS
    1212. 查询球队积分
    数据合并与对比
    经典SQL语句大全
  • 原文地址：https://blog.csdn.net/m0_61982936/article/details/132668022