营销型网站和普通网站的区别,网络教育做的好的网站,网站建设 项目经验,网站系统安全性父母就像迭代器#xff0c;封装了他们的脆弱...... 手撕list目录#xff1a;
一、list的常用接口及其使用
1.1list 构造函数与增删查改
1.2list 特殊接口
1.3list 排序性能分析
二、list 迭代器实现#xff08;重点难点#xff09;
关于迭代器的引入知识#xff1a…父母就像迭代器封装了他们的脆弱...... 手撕list目录
一、list的常用接口及其使用
1.1list 构造函数与增删查改
1.2list 特殊接口
1.3list 排序性能分析
二、list 迭代器实现重点难点
关于迭代器的引入知识
2.1迭代器的分类
2.2 list 迭代器失效问题和vector有差异
2.3list 迭代器源码模板
2.4list 整体基本框架
三、手撕list迭代器
3.1重载operator*()
3.2重载、–、
3.3 利用类模板优化
四、增删查改
4.1 insert参数必须加引用担心非内置类型和erase
4.2 push_back和push_front
4.3 pop_back和pop_front
五、list 构造赋值重载
5.1默认构造迭代器区间构造拷贝构造
5.2 赋值重载现代写法
5.3 类名和类型的问题C的一个坑
六、list和vector的对比重点
七、源码合集 一、list的常用接口及其使用
1.1list 构造函数与增删查改
list 是可以在常数范围内在任意位置进行插入和删除的序列式容器其底层是带头双向循环链表list 常用接口的使用和 string、vector 系列容器的接口使用一样这里我不详细介绍请看我们的老朋友cplusplus.com - The C Resources Network 构造函数
构造函数constructor接口说明list (size_type n, const value_type val value_type())构造的 list 中包含n个值为val的元素list()构造空的 list构造空的 list拷贝构造函数list (InputIterator first, InputIterator last)用 [first, last) 区间中的元素构造 list 增删查改
函数说明接口说明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中的有效元素
注意 1、由于 list 的物理结构是非连续的 – 前一个节点地址和后一个节点地址的位置关系是随机的所以 list 不支持随机访问自然也就不支持 [ ] 操作 2、list 不支持reserve操作因为 list 的节点是使用时开辟使用完销毁不能预留空间 从这个特点也容易看出来如果需要一直插入删除元素利用list更好 1.2list 特殊接口
除了上述 STL 容器基本都有的一般接口外list 还提供一些独有的特殊操作接口如下
函数声明接口说明splice将 list1 中的元素转移到 list2 中remove移除 list 中的指定元素unique链表去重sort之后才可以用merge合并两个链表sort链表排序探究为什么list自己写sortreverse链表逆置
题外话 为什么list需要自己实现sort接口难道说库中的封装性不好效率不高 我们先使用库中自己的sort函数 我们使用算法库中的sort函数
void test_sort()
{listint l1{ 5,6,4,8,9,2,7 };//C 11写法sort(l1.begin(),l1.end());for(auto l : l1){cout l ;}cout endl;
} 报错了意外之中如果不报错我还写这个知识点干啥 doge 报错原因说没有-迭代器
让我们看看sort源码~ 这一切的一切都是因为sort的迭代器引起的
注意 1、链表排序只能使用 list 提供的 sort 接口而不能使用 algorithm 提供的 sort 接口因为链表物理地址不连续迭代器为双向迭代器不支持 - 操作而算法库中的 sort 函数需要支持 - 的随机迭代器 2、链表去重之前必须保证链表有序否则去重不完全 3、两个有序链表合并之后仍然保存有序 最后虽然 list 提供了这些具有特殊功能的接口它们也确实有一定的作用但是实际上这些特殊接口使用频率非常低包括 sort 接口 (链表排序的效率太低)。
1.3list 排序性能分析
虽然链表排序只能使用 list 提供的 sort 接口而不能使用 algorithm 提供的 sort 接口但是其使用频率仍然非常低这是由于链表排序的效率太低了我们可以通过对比两组测试数据来直观的感受链表排序的效率。
测试一vector 排序与 list 排序性能对比
//vector sort 和 list sort 性能对比 -- release 版本下
void test_op1() {srand((size_t)time(0));const int N 1000000; //100万个数据vectorint v;v.reserve(N);listint lt;for (int i 0; i N; i){auto e rand();v.push_back(e);lt.push_back(e);}//vector sortint begin1 clock();sort(v.begin(), v.end());int end1 clock();//list sortint begin2 clock();lt.sort();int end2 clock();printf(vector sort:%d\n, end1 - begin1);printf(list sort:%d\n, end2 - begin2);
}测试二list 直接进行排序与将数据拷贝到 vector 中使用 vector 排序后再将数据拷回 list 中性能对比
//list sort 与 将数据转移到 vector 中进行排序后拷贝回来性能对比 -- release 版本下
void test_op2()
{srand(time(0));const int N 1000000; //100万个数据listint lt1;listint lt2;for (int i 0; i N; i){auto e rand();lt1.push_back(e);lt2.push_back(e);}//list sort -- lt1int begin1 clock();lt1.sort();int end1 clock();// 将数据拷贝到vector中排序排完以后再拷贝回来 -- lt2int begin2 clock();vectorint v;v.reserve(N);for (auto e : lt2) //拷贝{v.push_back(e);}sort(v.begin(), v.end()); //排序lt2.assign(v.begin(), v.end()); //拷贝int end2 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接口是很挫的 二、list 迭代器实现重点难点
关于迭代器的引入知识
迭代器的价值在于封装底层的实现不具体暴露底层的实现细节提供统一的访问方式
iterator只是代言人真正的牛逼大佬其实是_list_iterator 为什么在 list 中将迭代器搞成指针这招不好用了呢 在数组中*指针就是元素指针就是 sizeof(T) 对象大小没办法谁叫他们物理空间连续结构NB所以对于vector和string类而言物理空间是连续的原生的指针就是迭代器了解引用就是数据了。但是对于这里的list而言空间是不连续的 解决方法 此时如果解引用是拿不到数据的空间不连续更不用说指向下一个结点了。所以对于list的迭代器原生指针已经不符合我们的需求了我们需要去进行特殊处理进行类的封装。我们可以通过类的封装以及运算符重载支持这样就可以实现像内置类型一样的运算符 迭代器的俩个特征 1.解引用2. / -- 运算符重载的大任务 实现解引用operator*和函数 2.1迭代器的分类
按照迭代器的功能迭代器一共可以分为以下三类 单向迭代器 – 迭代器仅仅支持 和解引用操作单链表哈希 双向迭代器 – 迭代器支持 、-- 和解引用操作但不支持 、- 操作list 双向链表 随机迭代器 – 迭代器不仅支持 、-- 和解引用操作还支持 、- 操作即迭代器能够随机访问stringvector 这也充分说明vector和string是可以用库中的sort函数的 迭代器还可以分成普通迭代器和const迭代器俩类 //1.const T* p1
listint::const_iterator cit lt.begin();
//2.T* const p2
const listint::iterator cit lt.begin();
//不符合const迭代器的行为因为保护迭代器本身不能修改那么我们也就不能迭代器灵魂拷问const迭代器是p1还是p2p1
const迭代器类似p1的行为保护指向的对象不被修改迭代器本身可以修改 2.2 list 迭代器失效问题和vector有差异
vector迭代器失效insert扩容erase的时候会失效
和 vector 不同list 进行 insert 操作后并不会产生迭代器失效问题因为 list 插入的新节点是动态开辟的同时由于 list 每个节点的物理地址是不相关的所以插入的新节点并不会影响原来其他节点的地址
但是 list erase 之后会发生迭代器失效因为 list 删除节点会直接将该节点释放掉此时我们再访问该节点就会造成越界访问
2.3list 迭代器源码模板
我们知道迭代器是类似于指针一样的东西即迭代器要能够实现指针相关的全部或部分操作 – 、–、*、、-对我们之前 string 和 vector 的迭代器来说迭代器就是原生指针所以它天然的就支持上述操作
但是对于 list 来说list 的节点是一个结构体同时 list 每个节点的物理地址是不连续的如果此时我们还简单将节点的指针 typedef 为迭代器的话那么显然它是不能够实现解引用、 等操作的所以我们需要用结构体/类来对迭代器进行封装再配合运算符重载等操作让迭代器能够实现解引用、、-- 等操作
框架代码如下 //节点定义
template class T
struct __list_node {typedef void* void_pointer;void_pointer next;void_pointer prev;T data;
};//迭代器定义
typedef __list_iteratorT, T, T* iterator;
typedef __list_iteratorT, const T, const T* const_iterator;//迭代器类
templateclass T, class Ref, class Ptr
struct __list_iterator {typedef __list_iteratorT, Ref, Ptr self;typedef __list_nodeT* link_type; //节点的指针link_type node; //类成员变量__list_iterator(link_type x) : node(x) {} //将节点指针构造为类对象//... 使用运算符重载支持迭代器的各种行为self operator() {...}self operator--() {...}Ref operator*() const {...}
};2.4list 整体基本框架 namespace lzy
{//结点templateclass Tstruct list_node{list_node* _next;list_node* _prev;T _data;list_node(const T x)//节点的构造函数及初始化列表:_next(nullptr), _prev(nullptr), _data(x){}};templateclass Tclass list{typedef list_nodeT node;public://迭代器typedef __list_iteratorT iterator;typedef __list_const_iteratorT const_iterator;//构造list(){_head new node(T());_head-_next _head;_head-_prev _head;}private:node* _head;size_t _size;};
}三、手撕list迭代器
迭代器的实现我们需要去考虑普通迭代器和const迭代器。这两种迭代器的不同也会带来不同的接口。我们可以分别单独去进行实现我们先来看一看简单的构造迭代器只需要提供一个结点即可,看一看实现的基本框架 templateclass Tstruct __list_iterator{typedef list_nodeT node;node* _pnode;__list_iterator(node* p):_pnode(p){}}为什么迭代器不写拷贝构造函数浅拷贝真的可以吗
对于迭代器的拷贝构造和赋值重载我们并不需要自己去手动实现编译器默认生成的就是浅拷贝而我们需要的就是浅拷贝这也说明了并不是说如果有指针就需要我们去实现深拷贝而且迭代器不需要写析构函数所以说不需要深拷贝
为什么聊这个问题因为listint::iterator itv.begin() 这就是一个拷贝构造
3.1重载operator*()
这个比较简单就是要获取迭代器指向的数据并且返回数据的引用 T operator*()
{return _pnode-_data;
}3.2重载、–、 __list_iteratorT operator(){_pnode _pnode-_next;return *this;}__list_iteratorT operator--(){_pnode _pnode-_prev;return *this;}bool operator!(const __list_iteratorT it){return _pnode ! it._pnode;}如果按照上面的做法我们在来看看此时普通迭代器和const迭代器的区别
//typedef __list_iteratorT iterator;
//typedef __list_const_iteratorT const_iterator;templateclass Tstruct __list_iterator{typedef list_nodeT node;node* _pnode;__list_iterator(node* p):_pnode(p){}T operator*(){return _pnode-_data;}__list_iteratorT operator(){_pnode _pnode-_next;return *this;}__list_iteratorT operator--(){_pnode _pnode-_prev;return *this;}bool operator!(const __list_iteratorT it){return _pnode ! it._pnode;}};//跟普通迭代器的区别遍历不能用*it修改数据templateclass Tstruct __list_const_iterator{typedef list_nodeT node;node* _pnode;__list_const_iterator(node* p):_pnode(p){}const T operator*(){return _pnode-_data;}__list_const_iteratorT operator(){_pnode _pnode-_next;return *this;}__list_const_iteratorT operator--(){_pnode _pnode-_prev;return *this;}bool operator!(const __list_const_iteratorT it){return _pnode ! it._pnode;}};代码冗余代码冗余代码冗余
如果是这样子去实现的话我们就会发现这两个迭代器的实现并没有多大的区别唯一的区别就在于operator*的不同。const迭代器和普通迭代器的唯一区别就是普通迭代器返回T可读可写const迭代器返回const T,可读不可写。我们可以参考源码的实现类模板参数解决这个问题这也是迭代器的强大之处
3.3 利用类模板优化
template class T,class Ref,class Ptr
//typedef __list_iteratorT, T, T* iterator;
//typedef __list_iteratorT, const T, const T* const_iterator;利用类模板参数修正之后的代码 // typedef __list_iteratorT, T, T* iterator;// typedef __list_iteratorT, const T, const T* const_iterator;templateclass T, class Ref, class Ptrstruct __list_iterator{typedef list_nodeT node;typedef __list_iteratorT, Ref, Ptr Self;node* _pnode;__list_iterator(node*p):_pnode(p){}//返回数据的指针Ptr operator-(){return _pnode-_data;}//模板参数做返回值Ref operator *(){return _pnode-_data;}//itSelf operator (){_pnode _pnode-_next;return *this;}//itSelf operator (int){Self tmp(*this);_pnode _pnode-_next;return tmp;}Self operator--(){_pnode _pnode-_prev;return *this;}Self operator--(int){Self tmp(*this);_pnode _pnode-_prev;return tmp;}bool operator !(const Self it)const{return _pnode ! it._pnode;}bool operator (const Self it)const{return _pnode it._pnode;}};同一个类模板此时我们传递不同的参数实例化成不同的迭代器了这解决了我们刚刚所说的代码冗余问题 四、增删查改
4.1 insert参数必须加引用担心非内置类型和erase
insert在pos位置上一个插入返回插入位置的迭代器对于list的insert迭代器不会失效vector失效是因为扩容导致pos位置造成野指针问题 iterator insert(iterator pos,const T x){node* newnode new node(x);node* cur pos._pnode;node* prev cur-_prev;newnode-_prev prev;prev-_next newnode;newnode-_next cur;cur-_prev newnode;_size;return iterator(newnode);}erase:这里的带头哨兵位头结点不可删除返回值是删除位置的下一个对于list的erase迭代器是失效的 iterator erase(iterator pos){assert(pos ! end());node* prev pos._pnode-_prev;node* next pos._pnode-_next;prev-_next next;next-_prev prev;delete pos._pnode;--_size;return iterator(next);}4.2 push_back和push_front void push_back(const T x){insert(end(), x);}void push_front(const T x){insert(begin(), x);}注意list的begin和end的位置 同时这个问题还可以延伸出另一个问题为什么迭代器访问元素的时候要这样写 在vector中物理地址是连续的这么写还情有可原分析过list的begin和end之后你还敢这么写吗 直接就报错了所以正确的应该是而不是
void test3()
{vectorint vv{1,5,7,8,9,3,4};listint l{1,5,6,7};vectorint::iterator it1vv.begin();listint::iterator it2l.begin();while(it1 vv.end()){cout *it1 ;it1;}cout endl;// while(it2 l.end())// {// cout *it2 ;// it2;// }while(it2 ! l.end()){cout *it2 ;it2;}cout endl;
}
4.3 pop_back和pop_front
尾删和头删复用erase即可 void pop_front(){erase(begin());}void pop_back(){erase(--end());}这里的尾删刚好用上了我们的重载 五、list 构造赋值重载
5.1默认构造迭代器区间构造拷贝构造
默认构造
list()
{_head new node(T());_head-_next _head;_head-_prev _head;_size 0;
}我们可以用empty_initialize()来封装初始化方便复用不用每次都写
void empty_initialize()
{_head new node(T());_head-_next _head;_head-_prev _head;_size 0;
}迭代器区间构造 //迭代器区间构造template class InputIteratorlist(InputIterator first, InputIterator last){empty_initialize();while (first ! last){push_back(*first);first;}}拷贝构造 传统 list(const listT lt){empty_initialize();for (const auto e : lt){push_back(e);}}用范围for进行尾插但是要注意要加上范围for是*it赋值给给e又是一个拷贝e是T类型对象依次取得容器中的数据T如果是string类型不断拷贝push_back之后又销毁
现代 void swap(listT lt){std::swap(_head, lt._head);std::swap(_size, lt._size);} list(const listT lt){empty_initialize();listT tmp(lt.begin(), lt.end());swap(tmp);}5.2 赋值重载现代写法 listT operator(listT lt){swap(lt);return *this;}5.3 类名和类型的问题C的一个坑
查看官方文档我们可以看到list没有类型 listT operator(listT lt) list operator(list lt) 对于普通类类名等价于类型 对于类模板类名不等价于类型如list模板类名list 类型list 类模板里面可以用类名代表类型但是并不建议在类外面则必须要带模板参数list 六、list和vector的对比重点
vectorlist底层结构动态顺序表一段连续空间带头结点的双向循环链表随机访问支持随机访问访问某个元素效率 O(1)不支持随机访问插入和删除任意位置插入和删除效率低需要搬移元素时间复杂度为 O(N)插入时有可能需要增容增容开辟新空间拷贝元素释放旧空间导致效率更低任意位置插入和删除效率高不需要搬移元素时间复杂度为 O(1)空间利用率底层为连续空间不容易造成内存碎片空间利用率高缓存利用率高底层节点动态开辟小节点容易造成内存碎片空间利用率低缓存利用率低迭代器原生态指针对原生态指针 (节点指针) 进行封装迭代器失效在插入元素时要给所有的迭代器重新赋值因为插入元素有可能会导致重新扩容致使原来迭代器失效删除时当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效删除元素时只会导致当前迭代器失效其他迭代器不受影响使用场景在插入元素时要给所有的迭代器重新赋值因为插入元素有可能会导致重新扩容致使原来迭代器失效删除时当前迭代器需要重新赋值否则会失效大量插入和删除操作不关心随机访问
七、源码合集
#pragma once#include iostream
#include assert.h
#include algorithmnamespace lzy {templateclass Tstruct list_node //list 节点结构定义{list_nodeT* _next;//不加T也没错但是写上好一些list_nodeT* _prev;T _data;list_node(const T x)//构造:_next(nullptr), _prev(nullptr), _data(x){}};//迭代器最终版//const 迭代器 -- 增加模板参数解决 operator*() 返回值与 operator-() 返回值问题//typedef __list_iteratorT, T, T* iterator;//typedef __list_iteratorT, const T, const T* const_iterator;//STL源码中大佬的写法利用多个模板参数来避免副本造成的代码冗余问题templateclass T, class Ref, class Ptrstruct __list_iterator //迭代器类{typedef list_nodeT node; //重命名list节点typedef __list_iteratorT, Ref, Ptr Self; //这里进行重命名是为了后续再添加模板参数时只用修改这一个地方node* _pnode; //节点指针作为类的唯一成员变量__list_iterator(node* p):_pnode(p){}Ref operator*() //解引用{return _pnode-_data;}Ptr operator-() //-{return _pnode-_data;}Self operator() //前置{_pnode _pnode-_next;return *this;}Self operator(int) //后置{Self it(*this);_pnode _pnode-_next;return it;}Self operator--() //前置--{_pnode _pnode-_prev;return *this;}Self operator--(int) //后置--{Self it(*this);_pnode _pnode-_prev;return it;}bool operator!(const Self it) const //!{return _pnode ! it._pnode;}bool operator(const Self it) const //{return _pnode it._pnode;}};//list 类templateclass Tclass list{typedef list_nodeT node; //list 的节点public:typedef __list_iteratorT, T, T* iterator; //迭代器typedef __list_iteratorT, const T, const T* const_iterator; //const 迭代器//迭代器iterator begin() {return iterator(_head-_next);}iterator end() {//iterator it(_head);//return it;//直接利用匿名对象更为便捷return iterator(_head);}const_iterator begin() const {return const_iterator(_head-_next);}const_iterator end() const {return const_iterator(_head);}void empty_initialize() { //初始化 -- 哨兵位头结点_head new node(T());_head-_next _head;_head-_prev _head;_size 0; //空间换时间用于标记节点个数}list() { //构造不是listT的原因构造函数函数名和类名相同而listT是类型empty_initialize();}//迭代器区间构造template class InputIteratorlist(InputIterator first, InputIterator last) {empty_initialize();while (first ! last){push_back(*first);first;//first;}}//拷贝构造传统写法//list(const listT lt) {// empty_initialize();// for (const auto e : lt)// {// push_back(e);// }//}// 拷贝构造的现代写法//list(const list lt) 官方库是这样写的这是由于在类内类名等价于类型但不建议自己这样写list(const listT lt) {empty_initialize(); //初始化头结点防止交换后tmp野指针不能正常的调用析构listT tmp(lt.begin(), lt.end());swap(tmp);}//赋值重载传统写法//listT operator(const listT lt) {// if (this ! lt)// {// clear();// for (const auto e : lt)// {// push_back(e);// }// }// return *this;//}//赋值重载现代写法//list operator(list lt)listT operator(listT lt) { //不能加引用lt是调用拷贝构造生成的swap(lt);return *this;}~list() { //析构clear();delete _head;_head nullptr;}void swap(listT lt) { //交换两个链表本质上是交换两个链表的头结点std::swap(_head, lt._head);std::swap(_size, lt._size);}size_t size() const { //增加一个计数的成员以空间换时间return _size;}bool empty() { //判空return _size 0;}void clear() {iterator it begin();while (it ! end()) {it erase(it);}_size 0;}void push_back(const T x) {//node* newnode new node(x);//node* tail _head-_prev;//tail-_next newnode;//newnode-_prev tail;//newnode-_next _head;//_head-_prev newnode;insert(end(), x); //复用}void push_front(const T x) {insert(begin(), x); //复用}void pop_front() {erase(begin());}void pop_back() {erase(--end());}iterator insert(iterator pos, const T x) {node* newnode new node(x);node* cur pos._pnode;node* prev cur-_prev;prev-_next newnode;newnode-_prev prev;cur-_prev newnode;newnode-_next cur;_size;return iterator(pos);}iterator erase(iterator pos) {assert(pos ! end());node* prev pos._pnode-_prev;node* next pos._pnode-_next;prev-_next next;next-_prev prev;delete pos._pnode;--_size;return iterator(next);}private:node* _head;size_t _size;};
}完结撒花~
