免费做网站表白,电商网站设计欣赏,微信官方网站,容县建设工程交易中心网站1. list的介绍及使用
1.1 list的介绍#xff08;双向循环链表#xff09; https://cplusplus.com/reference/list/list/?kwlist#xff08;list文档介绍#xff09; 1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器#xff0c;并且该容器可以前后双向迭… 1. list的介绍及使用
1.1 list的介绍双向循环链表 https://cplusplus.com/reference/list/list/?kwlistlist文档介绍 1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。 2. list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。 3. list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高效。 4. 与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。 1.2 list的使用可以对照模拟实现看重要的都有后边模拟实现都会讲 list中的接口比较多此处类似只需要掌握如何正确的使用然后再去深入研究背后的原理已达到可扩展的能力。以下为list中一些常见的重要接口。 1.2.1 list的构造 1.2.2 list iterator的使用 此处大家可暂时将迭代器理解成一个指针该指针指向list中的某个节点。 【注意】 1. begin与end为正向迭代器对迭代器执行操作迭代器向后移动 2. rbegin(end)与rend(begin)为反向迭代器对迭代器执行操作迭代器向前移动 1.2.3 list capacity 1.2.4 list element access 1.2.5 list modifiers list中还有一些操作需要用到时大家可参阅list的文档说明。 1.2.6 list的迭代器失效 注意insert不会失效迭代器依旧指向原来位置erase会失效删除后返回下一个地址跟vector的迭代器失效类比都是因为没有接收删除后的迭代器。insert不会失效因为插入后返回新的节点地址本身就指向新节点不会失效 错误代码 void TestListIterator1()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, arraysizeof(array)/sizeof(array[0]));auto it l.begin();while (it ! l.end()){// erase()函数执行后it所指向的节点已被删除因此it无效在下一次使用it时必须先给
其赋值l.erase(it); it;}
} 改正后 // 改正
void TestListIterator()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, arraysizeof(array)/sizeof(array[0]));auto it l.begin();while (it ! l.end()){l.erase(it); // it l.erase(it);两种写法都对}
} 2. list的模拟实现 要模拟实现list必须要熟悉list的底层结构以及其接口的含义通过上面的学习这些内容已基本掌握现在我们来模拟实现list。
2.1源码
test.cpp #includeiostream
#includelist
#includevector
#includealgorithm
using namespace std;#includeList.hnamespace jzy
{void test_list1(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);listint::iterator it lt.begin();while (it ! lt.end()){//*it 10;cout *it ;it;}cout endl;for (auto e : lt){cout e ;}cout endl;}void test_list2(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout e ;}cout endl;lt.push_back(5);lt.push_front(0);for (auto e : lt){cout e ;}cout endl;lt.pop_back();lt.pop_front();for (auto e : lt){cout e ;}cout endl;lt.clear();for (auto e : lt){cout e ;}cout endl;lt.push_back(10);lt.push_back(20);for (auto e : lt){cout e ;}cout endl;}void test_list3(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout e ;}cout endl;listint copy(lt);for (auto e : copy){cout e ;}cout endl;listint lt1;lt1.push_back(10);lt1.push_back(20);lt1.push_back(30);lt1.push_back(40);lt lt1;for (auto e : copy){cout e ;}cout endl;}void print_list(const listint lt){listint::const_iterator it lt.begin();while (it ! lt.end()){//*it 10;cout *it ;it;}cout endl;for (auto e : lt){cout e ;}cout endl;}void test_list4(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);print_list(lt);listint::iterator it lt.begin();while (it ! lt.end()){*it 10;cout *it ;it;}cout endl;}struct AA{int _a1;int _a2;AA(int a1 1, int a2 1):_a1(a1), _a2(a2){}};void test_list5(){listAA lt;AA aa1;lt.push_back(aa1);lt.push_back(AA());AA aa2(2, 2);lt.push_back(aa2);lt.push_back(AA(2, 2));listAA::iterator it lt.begin();cout (*it)._a1 : (*it)._a2 endl;cout it.operator*()._a1 : it.operator*()._a2 endl;cout it-_a1 : it-_a2 endl;cout it.operator-()-_a1 : it.operator-()-_a2 endl;cout endl;}}int main(){jzy::test_list1();return 0;}list.h
#pragma once
#includeassert.hnamespace jzy
{templateclass Tstruct ListNode{ListNodeT* _next;ListNodeT* _prev;T _data;ListNode(const T x T()):_next(nullptr), _prev(nullptr), _data(x){}};templateclass T, class Ref, class Ptrstruct __list_iterator{typedef ListNodeT Node;typedef __list_iteratorT, Ref, Ptr self;Node* _node;__list_iterator(Node* x):_node(x){}// itself operator(){_node _node-_next;return *this;}// itself operator(int){self tmp(*this);_node _node-_next;return tmp;}self operator--(){_node _node-_prev;return *this;}self operator--(int){self tmp(*this);_node _node-_prev;return tmp;}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const self s){return _node ! s._node;}bool operator(const self s){return _node s._node;}};//templateclass T//struct __list_const_iterator//{// typedef ListNodeT Node;// typedef __list_const_iteratorT self;// Node* _node;// __list_const_iterator(Node* x)// :_node(x)// {}// // it// self operator()// {// _node _node-_next;// return *this;// }// // it// self operator(int)// {// self tmp(*this);// _node _node-_next;// return tmp;// }// self operator--()// {// _node _node-_prev;// return *this;// }// self operator--(int)// {// self tmp(*this);// _node _node-_prev;// return tmp;// }// const T operator*()// {// return _node-_data;// }// bool operator!(const self s)// {// return _node ! s._node;// }// bool operator(const self s)// {// return _node s._node;// }//};templateclass Tclass list{typedef ListNodeT Node;public:typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;iterator begin(){//return iterator(_head-_next);return _head-_next;}iterator end(){return _head;}const_iterator begin() const{return _head-_next;}const_iterator end() const{return _head;}void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;}list(){empty_init();}void clear(){iterator it begin();while (it ! end()){it erase(it);}}~list(){clear();delete _head;_head nullptr;}list(const listT lt){empty_init();for (const auto e : lt){push_back(e);}}// lt1 lt2;// listT operator(const listT lt)/*listT operator(listT lt){if (this ! lt){clear();for (const auto e : lt){push_back(e);}}return *this;}*/void swap(listT tmp){std::swap(_head, tmp._head);}//list operator(list lt)listT operator(listT lt){swap(lt);return *this;}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_back(){erase(--end());}void pop_front(){erase(begin());}// vector insert会导致迭代器失效// list会不会不会iterator insert(iterator pos, const T x){Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(x);// prev newnode curprev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;//return iterator(newnode);return newnode;}iterator erase(iterator pos){assert(pos ! end());Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;return next;}private:Node* _head;};
}
注意list的const迭代器可以实现为一个类也可以实现为模版参数实例化后的结果一般实现为后者会少写很多冗余代码
2.2 list的反向迭代器 ReverseIterator.h templateclass Iterator,class Ref,class Ptr
struct ReverseIterator
{typedef ReverseIteratorIterator, Ref, Ptr Self;Iterator cur;ReverseIterator(Iterator it):cur(it){ }Self operator(){--cur;return *this;}Ref operator*(){Iterator tmp cur;--tmp;return *tmp;}Ptr operator-(){return (operator*());}bool operator!(const Self s){return cur ! s.cur;}
}; List.h 在list类内部多了一些改动将反向迭代器的类重命名并且新加两个成员函数 test.cpp #define _CRT_SECURE_NO_WARNINGS 1#includeiostream
#includelistusing namespace std;#includeList.hint main()
{jzy::listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);jzy::listint::reverse_iterator rit lt.rbegin();while (rit ! lt.rend()){cout *rit ;rit;}cout endl;return 0;
}可以看到反向迭代器起了作用下面我来讲解反向迭代器的原理 反向迭代器可以理解成封装了正向迭代器正向迭代器又封装了原生指针反向迭代器等价于正向迭代器--反向迭代器解引用相当于正向迭代器--再解引用 因为反向迭代器的开始是正向迭代器结束位置结束是正向的开始所以反向迭代器要先--在解引用才是正确的值 反向迭代器的-也就是*拿到存放的值再取地址和之前讲的是一个道理 typedef ReverseIteratoriterator, T, T* reverse_iterator;//typedef ReverseIteratorconst_iterator, const T, const T* const_reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}反向迭代器在list类那里要多加一些东西重命名反向迭代器这个类当是普通反向迭代器的时候实例化iteratorT,T*当是const反向迭代器的时候实例化参数是const_iterator,const T,const T* 总体来讲可以把反向迭代器看成适配器当实例化参数是普通迭代器会按照普通迭代器的行为进行操作当参数是const时会调用const的操作 3. list与vector的对比 vector与list都是STL中非常重要的序列式容器由于两个容器的底层结构不同导致其特性以及应用场景不同其主要不同如下 list模拟实现讲解 定义结点结构体结构体成员是前仆后继指针和元素data还要写一个构造函数用来初始化结点 迭代器封装为一个类类定义的对象存放每个节点的地址也就是_node相当于迭代器指针被封装成了一个类里存放typedef是将类型重命名将长的类型重命名为短的记住类名不是类型类名类型才是类型 这里模版有三个参数第一个T是实例化类型第二个和第三个参数是为了*和-const类型会匹配T,constT ,constT* 正常类型会匹配T,T,T* 这里将原生指针封装了一层包装在一个类里边类定义的对象会通过操作指针前后移动来操作结点解引用拿到对应结点的值或者-拿到对应的地址 迭代器构造函数当返回值是iterator类型时会构造一个临时对象来操作 迭代器--和日期类的原理类似it是当前指针往后走一步this是it的地址然后返回之后的值后置参数多传一个int就行构造一个局部对象指针向后走一步返回走之前的值迭代器--和同理无非是向前走 operator*是*it相当于拿到对应的值我们就把it当成指针*it当成解引用地址即可这里是把指针封装到类里边和前边string和vector的指针有所区分-箭头相当于拿到存放对象的地址当在list内部存放结构体时会用到 最简单的两个运算符重载当判断不等于的时候会用到 list类要把上边两个类typedef后的类型写上去方便等会用 迭代器的重载当我们用begin或者end的时候会调用这四个重载普通对象调用普通迭代器返回普通可修改指向对象的迭代器这个对象可以用类名也可以直接返回Node*的结点指针单参数的构造函数支持隐式类型转换这两个写法都会生成一个临时对象然后进行使用const类型调用const迭代器返回const不可修改指向对象的迭代器慢慢理解这部分其实没有想象的那么难 list类的私有成员是_head充当一个指针用来声明第一个哨兵位头结点 默认构造是初始化一个哨兵位头结点结点内部存放前仆后继指针和data值是某个类型的默认构造然后让_head指向第一个哨兵位结点并且_next和_prev都指向自己完成哨兵位结点的初始化 析构函数先用clear清理删除除了哨兵位结点的剩余存放有效数据的结点释放了空间最后释放哨兵位结点空间_head置空就OK 拷贝构造先初始化一个哨兵位结点然后将要构造的对象内容依次给给e尾插到新对象后边 赋值拷贝先拷贝构造一个lt将lt和新对象交换lt是局部对象出作用域会调用析构函数新对象引用返回完成赋值拷贝 insert插入参数是迭代器指针生成临时对象2次拷贝构造和要插入的值cur指向要插入位置prev存放要插入位置前边的指针new一个新节点是要插入的新结点 三个指针相对位置是这样的一般都是在某个位置之前插入所以是这样的关系然后按顺序链接这三个位置前一个位置的后继指针和后一个位置的前驱指针都指向中间位置最后返回插入节点的迭代器单参数构造函数支持隐式类型转换 删除很简单不能删除哨兵位结点找到要删除节点记录要删除结点的前一个和后一个链接两边的节点最后释放要删除节点的空间返回下一个节点的迭代器会隐式类型转换成iterator类型的对象 尾插可以自己重新写逻辑也可以复用insert逻辑将第一个参数换成最后一个位置的迭代器相当于在哨兵位节点之前插入效果是一样的 头插尾插尾删是一样的复用inserterase逻辑就行 这部分在c语言实现数据结构链表那里讲的很详细了想看的可以看看 代码样例讲解 这是一个很基础的尾插和打印对象逻辑可以用第一个迭代器打印也可以用第二个范围for打印范围for底层就是迭代器无脑替换成迭代器进行打印可以看到*it和it都是我们封装成类的功劳原理很简单前面讲过 测试插入删除逻辑可以看到不管是头插头删尾插尾删都很清晰明了clear是直接删除有效结点只剩哨兵位所以打印不出来 可以看到拷贝构造和赋值拷贝都完成了使命前边讲的很详细这里不再赘述 这里主要测试普通迭代器和const迭代器各自调用各自const迭代器不可修改对象普通迭代器可以修改对象 最后一个样例插入AA类对象*it是拿到存放的结构体变量.操作符访问结构体成员拿到1:1打印第二行是编译器会将*it转换成it.operator*()效果是一样的 -箭头访问操作符会特殊处理一个箭头可以当做两个--并且编译器会转换成it.operator-()-_a1去访问会特殊处理这里当成特殊处理就好 以上就是我对list容器内容的讲解很详细欢迎大神交流
