list模拟实现
list定义list用法list iterator的使用begin() + end()rbegin()+rend() reverse()sort()merge()unique()remove()splice() list模拟实现struct和class的区别list三个类模板默认成员函数构造函数拷贝构造函数赋值运算符重载析构函数 数据修改操作push_back()push_front()pop_back()pop_front()swap()clear()insert()erase() 容量操作sizeempty 数据访问操作front()back() 迭代器正向迭代器构造函数begin() + end()const_iterator begin()/end()constoperator*()operator->()operator!=()operator==()前置++和后置++前置--和后置-- 反向迭代器定义构造函数rbegin() + rend()const_reverse_iterator rbegin()/rend()constoperator*()operator->()operator!=()operator==()前置++和后置++前置--和后置-- list模拟实现总代码铁汁们，今天给大家分享一篇list模拟实现+反向迭代器，来吧，开造⛳️
list定义
? list< typename> name ;
list底层是带头双向循环链表结构，且该容器可以前后双向迭代。
双向链表中每个元素存储互不相关的独立节点，在结点中通过指针访问其前一个元素和后一个元素。
list允许在任意位置进行插入和删除操作，时间复杂度为O(1)，时间效率高。
list不支持任意位置的随即访问，若想要访问某个位置，必须从已知的位置（头部或者尾部）迭代到该位置，时间开销为O(n)。
list需要额外的空间开销，用来保存每个节点的相关联信息。
typename为任意类型，例如：int、char、double、string、vector。
list用法
list iterator的使用
begin() + end()
?iterator begin( )、const_iterator begin( )const ；
功能：返回第一个元素的位置(迭代器）。Tips：const_iterator表示对迭代器进行解引用后的值(*it)不能被修改,而迭代器本身(it)可以被修改。const修饰this指针，表示在该成员函数中成员变量不允许被修改，此处const的用法只能用于类中的成员函数。
?iterator end( )、const_iterator end( )const ；
功能：返回最后一个元素的下一个位置(迭代器）。rbegin()+rend()
?iterator begin( )、const_iterator rbegin( )const ；
功能：返回第一个元素的前一个位置(迭代器）。?iterator rend( )、const_iterator rend( )const ；
功能：返回第一个元素的位置(迭代器）。
reverse()
? void reverse( ) ;
功能 : 逆置，将list中元素的顺序进行颠倒 。sort()
? void sort( ) ;
功能：排序，默认为升序。模板参数中的默认仿函数为less。Tips：list中的sort为归并排序，算法库中的sort为快排。
#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>#include<list>using namespace std;int main(){list<int> lt1;lt1.push_back(4);lt1.push_back(1);lt1.push_back(3);lt1.push_back(2); lt1.sort(); for (auto& e : lt1){cout << e << ' ';}cout << endl; return 0;}
merge()
?void merge(list& lt) ;
功能：将两个已经有序的链表进行合并，默认为升序 。#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>#include<list>using namespace std;int main(){list<int> lt1;lt1.push_back(4);lt1.push_back(1);lt1.push_back(3);lt1.push_back(2);list<int> lt2;lt2.push_back(9);lt2.push_back(7);lt2.push_back(10);lt2.push_back(8);lt1.sort();lt2.sort();lt1.merge(lt2);for (auto& e : lt1){cout << e << ' ';}cout << endl;for (auto& e : lt2){cout << e << ' ';}cout << endl; return 0;}
unique()
? void unique( ) ;
功能：去重，将链表中连续相等的元素组中删除除第一个元素外的所有元素。#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>#include<list>using namespace std;int main(){list<int> lt1;lt1.push_back(4);lt1.push_back(4);lt1.push_back(4);lt1.push_back(1);lt1.push_back(3);lt1.push_back(3);lt1.push_back(2);lt1.push_back(4);lt1.push_back(4);for (auto& e : lt1){cout << e << ' ';}cout << endl;lt1.unique();for (auto& e : lt1){cout << e << ' ';}cout << endl;return 0;}
remove()
? void remove(const T& val) ;
功能：去除，将链表中值为val的元素删除。#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>#include<list>using namespace std;int main(){list<int> lt1;lt1.push_back(4);lt1.push_back(1);lt1.push_back(3);lt1.push_back(2);for (auto& e : lt1){cout << e << ' ';}cout << endl;lt1.remove(4);for (auto& e : lt1){cout << e << ' ';}cout << endl;return 0;}
splice()
? void splice(iterator position , list& lt) ;
功能 ：将容器lt中所有的元素转移到容器中指定位置（迭代器）的前面，容器lt的大小为0。#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>#include<list>using namespace std;int main(){list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);list<int> lt2(3, 2);for (auto& e : lt1){cout << e << ' ';}cout << endl;for (auto& e : lt2){cout << e << ' ';}cout << endl;lt1.splice(lt1.begin(), lt2);for (auto& e : lt1){cout << e << ' ';}cout << endl;for (auto& e : lt2){cout << e << ' ';}cout << endl;return 0;}
? void splice(iterator position , list& lt , iterator i ) ;
功能：将容器lt中迭代器i指向的节点转移到容器中指定位置（迭代器）的前面，容器lt的大小减一。#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>#include<list>using namespace std;int main(){list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);list<int> lt2;lt2.push_back(10);lt2.push_back(11);lt2.push_back(12);for (auto& e : lt1){cout << e << ' ';}cout << endl;for (auto& e : lt2){cout << e << ' ';}cout << endl;lt1.splice(lt1.begin(), lt2, ++lt2.begin());for (auto& e : lt1){cout << e << ' ';}cout << endl;for (auto& e : lt2){cout << e << ' ';}cout << endl;return 0;}
? void splice(iterator position , list& lt , iterator first , iterator last ) ；
功能：将容器lt中[first, last)范围中的元素转移到容器中指定位置（迭代器）的前面。#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>#include<list>using namespace std;int main(){list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);list<int> lt2;lt2.push_back(10);lt2.push_back(11);lt2.push_back(12);lt2.push_back(13);for (auto& e : lt1){cout << e << ' ';}cout << endl;for (auto& e : lt2){cout << e << ' ';}cout << endl;lt1.splice(lt1.begin(), lt2, ++lt2.begin(),--lt2.end());for (auto& e : lt1){cout << e << ' ';}cout << endl;for (auto& e : lt2){cout << e << ' ';}cout << endl;return 0;}
list模拟实现
struct和class的区别
在c++中，struct和class都可以定义类，但两者默认的访问权限(即在变量或函数定义处不写访问限定符)不同，struct默认访问权限为public(为了兼容c)，class默认访问权限为private。 访问限定符有三种，分别为public、private、protect。public修饰的变量或函数在类外可以通过类名+域作用限定符或者 类对象 + . 进行访问，protect、private修饰的变量或函数在类外不可以进行访问。list三个类模板
Tips : list本质为带头双向循环链表，模拟实现list，要实现以下三个类：模拟实现节点的类、模拟实现带头双向循环链表结构的类、模拟实现迭代器的类。template<class T> //节点 struct ListNode { //struct类未用访问限定符修饰的变量为public,在类外指定类域就可以直接进行访问ListNode* _prev; //带头双向循环链表ListNode* _next;T _data;}template<class T> //链表-带头双向循环链表，存储的元素为节点class list { //class类未用访问限定符修饰的变量为private,在类外不可以访问public:typedef ListNode<T> Node; //为了符合规范，需要将迭代器的类型typedef为iteratortypedef list_iterator<T, T&, T*> iterator; //非consttypedef list_iterator<T, const T&, const T*> const_iterator; //constNode* _head; //头指针，该指针指向的节点为头节点，不存储任何有效数据//头节点中的_data不能存储后面节点的总个数，原因:若T为char型，数据个数过大，会数据溢出}template<class T, class Ref, class Ptr> //迭代器 Ref(T、const T)、Ptr(T*、const T*):*、->的返回值是否被修改，根据实际清况而定struct list_iterator { typedef ListNode<T> Node; //节点typedef list_iterator<T, Ref, Ptr> Self; //迭代器类型Node* _node; //节点指针}
list<int> lt1(2, 10);lt1.push_back(3);lt1.push_back(2);lt1.push_back(1);zzx::list<int>::iterator it1 = lt1.begin();while (it1 != lt1.end()){cout << *it1 << ' ';it1++;}cout << endl;const list<int> lt2(lt1.begin(), --lt1.end());zzx::list<int>::const_iterator it2 = lt2.begin();while (it2 != lt2.end()){cout << *it2 << ' ';it2++;}cout << endl;
默认成员函数
构造函数
void CreatHead() //创造带头双向循环链表结构{_head = new Node;_head->_prev = _head;_head->_next = _head;}?list( ) { } ;
功能：构造无参的对象。list() //无参构造{CreatHead();}?list(size_t n, const T& val = T( ) ) ；
功能：构造含n个val值的对象。list(size_t n, const T& val) //用n个val值构造{CreatHead();for (int i = 0; i < n; i++){push_back(val);}}list(int n, const T& val) //为了防止出现“非法间接寻址”错误{CreatHead();for (int i = 0; i < n; i++){push_back(val);}}Tips: 因为模板参数的匹配原则，会出现防止“非法间接寻址”错误。
?list( InputIterator first, InputIterator last ) ；
功能：构造与[first, last)范围一样多元素的对象。template<class InputIterator> // 注意：模板内可以在嵌套模板list(InputIterator first, InputIterator last) //用迭代区间进行构造{CreatHead();while (first != last){push_back(*first); ++first;}}拷贝构造函数
?list(const list& v) ；
功能：用一个已经存在的对象创建新的对象，两对象中的值相同。list(const list& lt) //拷贝构造函数，深拷贝-》浅拷贝，指向同一块空间，析构两次{CreatHead();for (auto& e : lt){push_back(e);}}Tips : 深拷贝，否则会造成指向同一块空间，被析构两次。
list<int> lt1(5, 2); // 先构造的对象后析构list<int> lt2 = lt1; //编译器会优化，构造 + 拷贝 - 》构造，默认拷贝构造为值拷贝lt1.push_back(1);for (auto& e : lt1){cout << e << ' ';}cout << endl;for (auto& e : lt2){cout << e << ' ';}cout << endl;
赋值运算符重载
?list& operator=(list v) ；
功能：赋值，两对象已经存在。list<T>& operator=(list lt) //赋值运算符{swap(lt);return *this;}Tips : 深拷贝，否则会造成指向同一块空间，被析构两次。
析构函数
?~vector( ) { } ；
功能：将列表中的元素全部删除(销毁)，并链表结构也被销毁。~list() //析构函数{clear();delete _head; //_head = nullptr;}数据修改操作
push_back()
?void push_back(const T& val) ;
功能：尾插。void push_back(const T& val) //尾插{/*传统写法Node* newnode = new Node(val);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;*/insert(end(), val);}push_front()
?void push_front(const T& val) ;
功能：头插。void push_front(const T& val) //头插{insert(begin(), val);}pop_back()
?void pop_back( ) ；
功能：尾删。void pop_back() //尾删{erase(--end());}pop_front()
?void pop_front( ) ;
功能：头删。void pop_front() //头删{erase(begin());}swap()
?void swap(list& lt) ;
功能：交换。void swap(list<T>& lt) //交换{std::swap(_head, lt._head);}clear()
?void clear( ) ；
功能：从列表容器中删除所有元素（已销毁），并使容器的大小为0，但带头双向链表结构仍在。void clear() //清空链表中的节点，哨兵位头节点除外，带头双向循环链表结构未被破坏{iterator it = begin();while (it != end()){it = erase(it);}}insert()
?void insert(iterator position , const T& val) ；
功能：在指定的位置(迭代器）前插入元素x。/*insert中迭代器不会失效原因:未扩容未引起底层空间发生变化，position迭代器未发生变化，仍指向了正确的位置，即使在使用此迭代器仍可以完成insert*/iterator insert(iterator position, const T& val){Node* newnode = new Node(val);Node* cur = position._node; //struct中public变量访问可以 对象.变量名Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return newnode; //有返回值，与erase匹配}
erase()
?iterator erase(iterator pos) ;
功能: 删除指定位置(迭代器)处的值。//erase中迭代器会失效,原因:position迭代器被delete了，此迭代器不能在被使用了iterator erase(iterator position){assert(position != end()); //断言，防止删除哨兵位头节点 Node* cur = position._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur; //cur = nullptr;return next; //返回删除节点的下一个节点}
容量操作
size
?size_t size( )const ;
功能：计算元素的总个数。size_t size()const{size_t count = 0;for (auto const& e : *this){count++;}return count;}empty
?bool empty( )const ;
功能：判断list中是否存在元素，为空，则返回true,不为空，则返回false。bool empty()const{return size() == 0;}数据访问操作
front()
?T& front( ) ;
功能：返回第一个节点中的元素。T& front(){return _head->_next->_data;}const T& front()const{return _head->_next->_data;}back()
?T& back( ) ;
功能：返回最后一个节点中的元素。T& back(){return _head->_prev->_data;}const T& back()const{ return _head->_prev->_data;}迭代器
正向迭代器
template<class T, class Ref, class Ptr> //迭代器 Ref(T、const T)、Ptr(T*、const T*):*、->的返回值是否被修改，根据实际清况而定struct list_iterator { typedef ListNode<T> Node; //节点typedef list_iterator<T, Ref, Ptr> Self; //迭代器类型Node* _node; //节点指针}list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);//it1: 内置类型ListNode<int>* it1 = lt1._head->_next; //it2：自定义类型list<int>::iterator it2 = lt1.begin();/*尽管it1和it2的值是相同的，但进行++操作时，编译器将it1当作内置类型(由语言标准指定的)进行处理,*表示取其指向空间中的值，++表示向后走sizeof(类型)的步长it2为自定义类型，去调用operator*()、operator++()运算符*/*it1;++it1;*it2;++it2;cout << sizeof(it1) << endl;cout << sizeof(it2) << endl;
Tips ：将模拟实现迭代器的类定义为struct类，且指针_node默认访问权限为public, 原因:list类中的insert、erase，position类型为迭代器，为了类型要匹配(node*),则在类外用迭代器._node进行访问，否则在类外就访问不到_node。
?不用显示写析构函数，原因:若显示写了，则表示是把该指针指向的节点一并删除，此处并不希望删除链表中的节点，默认生成的析构函数对内置类型不做处理。
未进行资源申请。
?不用显示写拷贝构造函数，默认生成的拷贝构造函数进行值拷贝，尽管两个指针指向同一块空间，一个指针被销毁，会去调用析构函数，因未显示写析构函数，析构函数对内置类型不做处理,指针变量会被销毁，系统将其回收了，但该指针变量指向的节点还在;
构造函数
?list_iterator(Node* node = nullptr) ；
list_iterator(Node* node = nullptr) //单参数构造函数支持隐式类型转换 Node*->iterator:_node(node){ }Tips : 单参数构造函数支持隐式类型转换 Node*->iterator 。
begin() + end()
?iterator begin( ) ；
功能：返回第一个元素的位置(迭代器）。Tips：list对象为非const对象，就调用begin()、end()，list为const对象，就调用const_iterator begin()const、const_iterator end()const。
iterator begin() //list对象为非const对象{return _head->_next; //单参数构造函数支持隐式类型转换}?iterator end( ) ；
功能：返回最后一个元素的下一个位置(迭代器）。iterator end(){return _head;}const_iterator begin()/end()const
?const_iterator begin( )const ;
Tips : const_iterator表示对迭代器解引用(*)的值不可以被修改，而迭代器本身可以被修改，const修饰类成员函数，实际修饰该成员函数隐含的this指针，表明在该成员函数中不能对类的任何成员进行修改。
/*const_iterator表示* 迭代器的值不可以被修改，而迭代器本身可以被修改，const修饰类成员函数，实际修饰该成员函数隐含的this指针，表明在该成员函数中不能对类的任何成员进行修改 */const_iterator begin()const //list对象为const对象， const对象才能调用const成员函数{return _head->_next; //单参数构造函数支持隐式类型转换}?const_iterator end( )const ;
const_iterator end()const{return _head;}operator*()
?Ref operator*( ) ；
/*oprator*()不用const，原因:iterator普通迭代器调用普通成员函数，const_iterator中迭代器为非const对象，指向的内容可以被修改*/Ref operator*() //只有返回值类型不一致-》模板参数{return _node->_data;}operator->()
?Ptr operator->( ) ；
Ptr operator->() //结构体指针，_data为结构体，*it只能取到结构体(自定义类型），若需要cout<<*it，则需要重载<<{//特殊处理，为了可读性，省略了一个 ->return &_node->_data; //it->_a1 -》 it.operator->()->_a1}struct AA{ int _a1;int _a2;AA(int a1 = 1, int a2 = 2):_a1(a1) ,_a2(a2){ }};list<AA> lt4; lt4.push_back(AA()); //AA()为匿名对象lt4.push_back(AA(10, 20));zzx::list<AA>::iterator it2 = lt4.begin();while (it2 != lt4.end()){cout << it2->_a1 << ":" << it2->_a2 << endl;++it2;}cout << endl;
operator!=()
?bool operator!=(const Self& tmp) ;
bool operator!=(const Self& tmp){return _node != tmp._node; //指针为内置类型，可以直接进行比较}operator==()
?bool operator==(const Self& tmp) ;
bool operator==(const Self& tmp){return _node == tmp._node;}前置++和后置++
?Self& operator++( ) ；
Self& operator++() //前置++{_node = _node->_next;return *this; //引用返回，出了作用域,*this还在，提高返回效率}?Self operator++(int) ；
Self operator++(int) //后置++{Self tmp(*this);_node = _node->_next;return tmp; //传值返回，出了作用域,tmp就被销毁}前置–和后置–
?Self& operator–( ) ；
Self& operator--() //前置--{_node = _node->_prev;return *this; //引用返回，出了作用域,*this还在，提高返回效率}?Self operator–(int) ；
Self operator--(int) //后置--{Self tmp(*this);_node = _node->_prev;return tmp; //传值返回，出了作用域,tmp就被销毁}反向迭代器
定义
正向迭代器为begin()、end()，反向迭代器为rbegin()、rend()。 反向迭代器的++就是正向迭代器的–，反向迭代器的–就是正向迭代器的++，所以反向迭代器的实现可以借助于正向迭代器来实现，将正向迭代器转换为反向迭代器，即：迭代器适配器。 迭代器适配器：给了我任何容器的正向迭代器，就可以适配出该容器的反向迭代器。将正向迭代器的类型定义为类模板，在反向迭代器中根据类模板参数定义正向迭代器对象，反向迭代器各接口的实现均通过调用正向迭代器的接口来实现。
构造函数
?list_reverse_iterator(iterator cur) ；
//正向迭代器封装了Node*指针，其构造函数参数为Node*,反向迭代器封装了iterator,其构造函数参数为iteratorlist_reverse_iterator(iterator cur) //构造函数:_cur(cur) //单参数构造函数支持隐式类型转换 iterator-》reverse_iterator{ }rbegin() + rend()
?reverse_iterator rbegin( ) ；
功能：返回第一个元素的前一个位置(迭代器）。reverse_iterator rbegin() //非const对象{return end();}?reverse_iterator rend( ) ；
功能：返回第一个元素的位置(迭代器）。reverse_iterator rend(){return begin();}const_reverse_iterator rbegin()/rend()const
?const_reverse_iterator rbegin( )const ;
const_reverse_iterator rbegin()const //const对象{return end();}?const_reverse_iterator rend( )const ;
const_reverse_iterator rend()const{return begin();}operator*()
?Ref operator*( ) ；
Ref operator*() //只是取其所指向的节点中的值，指针的值并未发生变化{ //rbegin()=end()、rend()=begin()iterator tmp = _cur; --tmp; return *tmp;}
operator->()
?Ptr operator->( ) ；
//正向迭代器operator->()是返回结构体的地址(结构体指针)Ptr operator->() //结构体指针{return &(operator*());}operator!=()
?bool operator!=(const Self& s) ;
bool operator!=(const Self& s) {return _cur != s._cur;}operator==()
?bool operator==(const Self& s) ;
bool operator==(const Self& s){return _cur == s._cur;}前置++和后置++
?Self& operator++( ) ；
Self& operator++() //前置++{ --_cur; //正向迭代器往前走return *this;}?Self operator++(int) ；
Self operator++(int) //后置++{Self tmp = *this;--_cur;return tmp;}前置–和后置–
?Self& operator–( ) ；
Self& operator--() //前置--{++_cur; //正向迭代器往后走return *this;}?Self operator–(int) ；
Self operator--(int) //后置--{Self tmp = *this;++_cur; return tmp;}list模拟实现总代码
#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>#include<assert.h>#include<list>#include"Reserve_Iterator.h"using namespace std;namespace zzx {struct AA{ int _a1;int _a2;AA(int a1 = 1, int a2 = 2):_a1(a1),_a2(a2){ }};template<class T> //节点 struct ListNode { //struct类未用访问限定符修饰的变量为public,在类外指定类域就可以直接进行访问ListNode* _prev; //带头双向循环链表ListNode* _next;T _data;ListNode(const T& val = T()) //缺省值-》防止无参调用，因无默认构造函数，又显示写了构造函数，编译器会报错:_prev(nullptr),_next(nullptr),_data(val){ }};/*迭代器:1.提供统一的方式进行访问和修改，摒弃了底层的细节，使容器进行访问和修改更加容易;* 2.底层为原生指针,因为list底层结构为链表，物理空间是不连续的，需要运算符重载，而重载运算符需要是自定义类型，指针为内置类型，* 所以对指针进行了封装list_iterator；* 3.为了符合规范，需要typedef将迭代器类型命名为iterator*/template<class T, class Ref, class Ptr> //迭代器 Ref(T、const T)、Ptr(T*、const T*):*、->的返回值是否被修改，根据实际清况而定struct list_iterator { typedef ListNode<T> Node; //节点typedef list_iterator<T, Ref, Ptr> Self; //迭代器类型Node* _node; //节点指针/*不用显示写析构函数，原因:若显示写了，则表示是把该指针指向的节点一并删除，此处并不希望删除链表中的节点，默认生成的析构函数对内置类型不做处理。 未进行资源申请;不用显示写拷贝构造函数，默认生成的拷贝构造函数进行值拷贝，尽管两个指针指向同一块空间，一个指针被销毁，会去调用析构函数，因未显示写析构函数，析构函数对内置类型不做处理,指针变量会被销毁，系统将其回收了，但该指针变量指向的节点还在;*/list_iterator(Node* node = nullptr) //单参数构造函数支持隐式类型转换 Node*->iterator:_node(node){ }Ptr operator->() //结构体指针，_data为结构体，*it只能取到结构体(自定义类型），若需要cout<<*it，则需要重载<<{//特殊处理，为了可读性，省略了一个 ->return &_node->_data; //it->_a1 -》 it.operator->()->_a1}/*oprator*()不用const，原因:iterator普通迭代器调用普通成员函数，const_iterator中迭代器为非const对象，指向的内容可以被修改*/Ref operator*() //只有返回值类型不一致-》模板参数{return _node->_data;}Self& operator++() //前置++{_node = _node->_next;return *this; //引用返回，出了作用域,*this还在，提高返回效率}Self operator++(int) //后置++{Self tmp(*this);_node = _node->_next;return tmp; //传值返回，出了作用域,tmp就被销毁}Self& operator--() //前置--{_node = _node->_prev;return *this; //引用返回，出了作用域,*this还在，提高返回效率}Self operator--(int) //后置--{Self tmp(*this);_node = _node->_prev;return tmp; //传值返回，出了作用域,tmp就被销毁}bool operator!=(const Self& tmp){return _node != tmp._node; //指针为内置类型，可以直接进行比较}bool operator==(const Self& tmp){return _node == tmp._node;}}; template<class iterator, class Ref, class Ptr> //反向迭代器:通过正向迭代器转换而来(迭代器适配器) struct list_reverse_iterator { iterator _cur; //迭代器适配器 typedef list_reverse_iterator<iterator, Ref, Ptr> Self;//正向迭代器封装了Node*指针，其构造函数参数为Node*,反向迭代器封装了iterator,其构造函数参数为iterator list_reverse_iterator(iterator cur) //构造函数 :_cur(cur) //单参数构造函数支持隐式类型转换 iterator-》reverse_iterator { } Ref operator*() //只是取其所指向的节点中的值，指针的值并未发生变化 { //rbegin()=end()、rend()=begin() iterator tmp = _cur; --tmp; return *tmp; } Self& operator++() //前置++ { --_cur; //正向迭代器往前走 return *this; } Self operator++(int) //后置++ { Self tmp = *this; --_cur; return tmp; } Self& operator--() //前置-- { ++_cur; //正向迭代器往后走 return *this; } Self operator--(int) //后置-- { Self tmp = *this; ++_cur; return tmp; } //正向迭代器operator->()是返回结构体的地址(结构体指针) Ptr operator->() //结构体指针 { return &(operator*()); } bool operator!=(const Self& s) { return _cur != s._cur; } bool operator==(const Self& s) { return _cur == s._cur; } };template<class T> //链表-带头双向循环链表，存储的元素为节点class list { //class类未用访问限定符修饰的变量为private,在类外不可以访问public:typedef ListNode<T> Node; //为了符合规范，需要将迭代器的类型typedef为iteratortypedef list_iterator<T, T&, T*> iterator; // 正向迭代器 、非consttypedef list_iterator<T, const T&, const T*> const_iterator; //consttypedef list_reverse_iterator<iterator, T&, T*> reverse_iterator; // 反向迭代器 、非consttypedef list_reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator; //const//正向迭代器iterator begin() //list对象为非const对象{return _head->_next; //单参数构造函数支持隐式类型转换}iterator end(){return _head;}/*const_iterator表示* 迭代器的值不可以被修改，而迭代器本身可以被修改，const修饰类成员函数，实际修饰该成员函数隐含的this指针，表明在该成员函数中不能对类的任何成员进行修改 */const_iterator begin()const //list对象为const对象， const对象才能调用const成员函数{return _head->_next; //单参数构造函数支持隐式类型转换}const_iterator end()const{return _head;}//反向迭代器reverse_iterator rbegin(){return end();}reverse_iterator rend(){return begin();}const_reverse_iterator rbegin()const{return end();}const_reverse_iterator rend()const{return begin();}void CreatHead() //创造带头双向循环链表结构{_head = new Node;_head->_prev = _head;_head->_next = _head;}//构造函数list() //无参构造{CreatHead();}list(size_t n, const T& val) //用n个val值构造{CreatHead();for (int i = 0; i < n; i++){push_back(val);}}list(int n, const T& val) //为了防止出现“非法间接寻址”错误{CreatHead();for (int i = 0; i < n; i++){push_back(val);}}template<class InputIterator> // 注意： 模板内可以在嵌套模板list(InputIterator first, InputIterator last) //用迭代区间进行构造{CreatHead();while (first != last){push_back(*first);++first;}}list(const list& lt) //拷贝构造函数，深拷贝-》浅拷贝，指向同一块空间，析构两次{CreatHead();for (auto& e : lt){push_back(e);}}list<T>& operator=(list lt) //赋值运算符{swap(lt);return *this;}~list() //析构函数{clear();delete _head; //_head = nullptr;}//修改void swap(list<T>& lt) //交换{std::swap(_head, lt._head);}void clear() //清空链表中的节点，哨兵位头节点除外，带头双向循环链表结构未被破坏{iterator it = begin();while (it != end()){it = erase(it);}}void push_back(const T& val) //尾插{/*传统写法Node* newnode = new Node(val);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;*/insert(end(), val);}void push_front(const T& val) //头插{insert(begin(), val);}void pop_back() //尾删{erase(--end());}void pop_front() //头删{erase(begin());}/*insert中迭代器不会失效原因:未扩容未引起底层空间发生变化，position迭代器未发生变化，仍指向了正确的位置，即使在使用此迭代器仍可以完成insert*/iterator insert(iterator position, const T& val){Node* newnode = new Node(val);Node* cur = position._node; //struct中public变量访问可以 对象.变量名Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return newnode; //有返回值，与erase匹配}//erase中迭代器会失效,原因:position迭代器被delete了，此迭代器不能在被使用了iterator erase(iterator position){assert(position != end()); //断言，防止删除哨兵位头节点Node* cur = position._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur; //cur = nullptr;return next; //返回删除节点的下一个节点}//AccessT& front(){return _head->_next->_data;}const T& front()const{return _head->_next->_data;}T& back(){return _head->_prev->_data;}const T& back()const{return _head->_prev->_data;}//Capacitysize_t size()const{size_t count = 0;for (auto const& e : *this){count++;}return count;}bool empty()const{return size() == 0;}Node* _head; //头指针，该指针指向的节点为头节点，不存储任何有效数据//头节点中的_data不能存储后面节点的总个数，原因:若T为char型，数据个数过大，会数据溢出};}铁铁们，list模拟实现+反向迭代器就到此结束啦，若博主有不好的地方，请指正，欢迎铁铁们留言，请动动你们的手给作者点个?鼓励吧，你们的鼓励就是我的动力✨