东莞正规的免费网站优化,杭州网络公司网站建设,腾讯企业qq注册中心,网站多语言切换#x1f493;博主CSDN主页:杭电码农-NEO#x1f493; ⏩专栏分类:C从入门到精通⏪ #x1f69a;代码仓库:NEO的学习日记#x1f69a; #x1f339;关注我#x1faf5;带你学习C #x1f51d;#x1f51d; 链表list 1. 前言2. list的使用2.1 list的构造函… 博主CSDN主页:杭电码农-NEO ⏩专栏分类:C从入门到精通⏪ 代码仓库:NEO的学习日记 关注我带你学习C 链表list 1. 前言2. list的使用2.1 list的构造函数2.2 list迭代器的使用2.3 list容量相关操作2.4 list的增删查改 3. list迭代器失效问题探讨4. 算法库函数和list的关系4.1 算法库函数的迭代器类型4.2 list不能使用的算法库函数 5. 总结以及拓展 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对象 第三个是用一段迭代器区间构造 第四个是用一个初始值构造 看起来平平无奇,来实操一下:
listint l1;//无参构造
listint l2(10,5);//用10个5初始化链表vectorint vv{1,2,3,4,5,6};
listint l3(vv.begin(),vv.end());//用迭代器区间初始化listchar l4(a);//用一个字符来初始化list的拷贝构造和析构函数在使用 list时不会显示调用,所以将它们忽略掉 2.2 list迭代器的使用
虽然list的迭代器底层不是指针 但是可以把它理解为指针来使用 这四个函数都是老朋友了,不多介绍了
唯一值得注意的是下图: begin和rend的指向相同 end和rbegin的指向相同
迭代器遍历链表:
vectorint vv{1,3,5,7,9,11,13,15};
listint l(vv.begin(),vv.end());auto it l.begin();
while(it!l.end())
{cout *it ;it;
}范围for遍历链表:
vectorint vv{1,3,5,7,9,11,13,15};
listint l(vv.begin(),vv.end());
for(auto x : l)
{cout x ;
}注:list不支持随机访问,不能用[]
一个小tips: 在写用迭代器遍历容器时,我们往往 会写it!l.end(),而不是itl.end() 这是因为在list中,空间并不连续,用小于 符号很大概率会出错,但是在string 和vector中,空间是连续的,用也没问题 2.3 list容量相关操作
这里最简单,和vector一模一样 只有这四个函数接口比较常用! 2.4 list的增删查改
首先映入眼帘的头插/头删,尾插/尾删 这几个函数的意思很明了,直接跳过
insert插入: insert函数要输入一个迭代去位置进行插入 可以插入一个数据或插入一段迭代器区间
erase删除: erase函数可以删除一个迭代器的数据 或者删除一段迭代器区间
clear清空有效元素: list不像vector一样有size和capacity list的clear函数是将链表清空 (除头节点外)
增删查改实操:
vectorint vv{1,5,10,15,20,100,120};
listint 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提供了返回值来解决问题: 会返回被删除位置的下一个位置的迭代器 以后可以这样写代码来避免错误:
listint ll{1,2,3,4,5,6,7,8};
auto itll.begin();
while(it!ll.end())
{if((*it)%20){iterase(it);}else{it;}
}4. 算法库函数和list的关系
首先,迭代器从功能角度可以分类为:
正向迭代器: forward_iterator双向迭代器: bidirectional_iterator随机迭代器: random_iterator
它们分别支持且仅支持:
只支持支持和- -支持,- -,和-
常见的容器以及它们的迭代器类型:
容器迭代器功能vector随机迭代器list双向迭代器stack不支持迭代器queue不支持迭代器deque随机迭代器set / multiset双向迭代器map / multimap双向迭代器priority_queue不支持迭代器 4.1 算法库函数的迭代器类型
现在再来看算法库的sort函数: 它的函数模板支持的是随机迭代器 再来看看算法库的reverse函数: 它的函数模板支持的是双向迭代器 我先给出以下的结论: 若函数模板给的随机迭代器 则只能传有随机迭代器的容器 若函数模板给的双向迭代器 则可以传有随机或者双向迭代器的容器 若函数模板给的单向迭代器 则三种迭代器都可以传进来! 可以看出它支持向上兼容! 4.2 list不能使用的算法库函数
可见,list是双向迭代器,而sort函数的 函数模板是随机迭代器 所以库函数中的sort无法排序链表
但是仔细查阅字典可以发现: list类自己实现了一个不同于算法库的排序 此排序专门用于排序list中的数据! 虽然list有自己的sort函数来排序 但是当数据很多时,list自我实现的 sort的效率低的惊人!甚至还不如 将list的数据导入vector容器 再在vector容器中使用算法库的排序 排完序再导入到list中,这一步骤快! 5. 总结以及拓展
总的来说list的使用和vector大同小异 当然,要掌握list,list的模拟实现是不可少的 list的模拟实现将在下一节分享给大家
本章笔记: 请自行熟悉list接口函数 list的insert不会导致迭代器失效 而erase会致使迭代器失效 迭代器从功能上可以划分为三种 它们向上兼容彼此 list不能使用算法库中的sort 但list类中实现了专门排序链表的函数
拓展阅读:
迭代器相关拓展知识 下期预告:list的模拟实现以及对比vector的区别
