0
0

【C++】list的模拟实现@STL —— 迭代器

list的模拟实现

本文依旧按照
依赖逻辑模拟实现list，重点讲解
迭代器。

正文开始@边通书

0. list

list即带头双向循环链表，支持在任意位置**O(1)**的插入和删除。

1. list框架

ListNode节点；list即一个头结点指针。

  1.     template<class T>structListNode{
  2.         ListNode<T>* _prev;
  3.         ListNode<T>* _next;
  4.         T _data;ListNode(const T& x =T()){
  5.             _prev = nullptr;
  6.             _next = nullptr;
  7.             _data = x;}};
  9.     template<class T>
  10.     class list
  11.     {typedef ListNode<T> Node;
  12.         
  13.     public:list(){
  14.             _head = new Node;
  15.             _head->_prev = _head;
  16.             _head->_next = _head;}
  17.     private:
  18.         Node* _head;};

为了随写随测，迅速先写一个尾插，这老生常谈了。当然一会儿写完insert(需要迭代器pos) 可以直接复用——

  1. voidpush_back(const T& x){
  2.             Node* newnode =newNode(x);
  3.             Node* tail = _head->_prev;
  4.             tail->_next = newnode;
  5.             newnode->_prev = tail;
  6.             newnode->_next = _head;
  7.             _head->_prev = newnode;}

2. 迭代器(重点)

❤️ 迭代器访问容器就是在模仿指针的两个重点行为：解引用 能够访问数据；++可以到下一个位置。对于string和vector这样连续的物理空间，原生指针就是天然的迭代器；然而对于list这样在物理空间上不连续的数据结构，解引用就是结点访问不到数据，++不能到下一个结点，原生指针做不了迭代器。

因此，对于链表的迭代器，我们用自定义类型对结点的指针进行封装，底层仍然是结点的指针。C++的自定义类型支持运算符重载，原本的运算符编程变成函数调用，这样就可以实现像内置类型一样使用运算符。这就是类型的力量！

构造迭代器，一个节点的指针就可以构造 ——

  1. template<classT>struct__list_iterator{typedef ListNode<T> Node;typedef __list_iterator<T,Ref,Ptr> Self;
  2.         Node* _node;__list_iterator(Node* x):_node(x){}};

迭代器的拷贝构造&赋值重载都不需要我们自己实现，因为要的就是浅拷贝，用编译器默认生成的即可。

析构函数呢？也不需要我们实现。那释放链表呢，节点属于链表list，迭代器是借助结点指针来访问修改链表的，不属于迭代器。就像是你自己的碗要自己洗，去外面吃就不用自己洗；我把结点的指针给你让你访问，结果你把我链表给释放了这不搞笑嘛。

2.1 iterator & const_iterator

迭代器遍历。下面是测试代码 ——

  1. voidprint_list(const list<int>& lt){
  2.         list<int>::const_iterator it = lt.begin();while(it != lt.end()){// *it /= 2; 不可写
  3.             cout <<*it <<" ";++it;}
  4.         cout << endl;}// 测试迭代器voidtest_list1(){
  5.         list<int> lt;
  6.          lt.push_back(1);
  7.         lt.push_back(2);
  8.         lt.push_back(3);
  9.         lt.push_back(4);
  11.         list<int>::iterator it = lt.begin();while(it != lt.end()){*it *=2;//可写
  12.             cout <<*it <<" ";++it;}
  13.         cout << endl;//测试const迭代器print_list(lt);}

可以看到我们首先需要重载++，*，!=这些运算符。

2.1.1 重载*

  • 我们在list中进行typedef，这样所有容器迭代器名字统一都是iterator。
  • 关于iterator和const_iterator：普通迭代器返回的是T&，可读可写；const迭代器返回的是const T&，可读不可写。我们当然可以再封装一个类就叫做__const_list_iterator，稍作修改，但是这样会造成严重的代码冗余，因为++/–/==的重载都没有区别，只是返回值不同罢了。我们巧妙的传入模板参数解决了这个问题，这也是迭代器的精华。
  • 我们把类模板typedef成self[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xRfb4xoc-1648974512795)(C:\Users\13136\AppData\Roaming\Typora\typora-user-images\image-20220402162738840.png)]

迭代器相关完整代码附在2.1.3小节.

2.1.2 重载->

如果T不是int这样的内置类型，而是自定义类型，我们要访问其中的每一个成员，还需要重载

  1. ->

。我们以日期类为例 ——

  1. structDate{Date(int year =0,int month =0,int day =0):_year(year),_month(month),_day(day){}int _year;int _month;int _day;};voidtest_list2(){
  2.         list<Date> lt;
  3.         lt.push_back(Date(2022,3,31));
  4.         lt.push_back(Date(2022,3,31));
  5.         lt.push_back(Date(2022,3,31));// 遍历链表，打印日期
  6.         list<Date>::iterator it = lt.begin();while(it != lt.end()){//cout << *it << endl; // 错误示范，请勿模仿// 因为Date是自定义类型，需要重载<<来打印，但要就是不给你提供呢，下面这样是可以的
  7.             cout <<(*it)._year <<"."<<(*it)._month <<"."<<(*it)._day << endl;
  8.             it++;}
  9.         cout << endl;}//小细节：Date构造函数需要给缺省值，因为哨兵位头结点没给数

迭代器it是去模仿指针的行为。在list中，如果节点中是int这样的内置类型，解引用(本质调用函数)访问数据即可；而像这里一个结构体的指针，我们固然可以

  1. (*it)

拿到日期类对象

  1. .

访问成员，但我们更希望能

  1. ->

访问成员，因此我们还需要重载

  1. ->

——

  1.     cout << it->_year <<"."<< it->_month <<"."<< it->_day << endl;

这里本来应该是

  1. it->->_year

，但是这样写运算符可读性太差了，所以编译器进行了优化，省略了一个

  1. ->

，所有类型想要重载

  1. ->

都是这样。对于const对象，可读不可写，那么应该返回const指针，因此我们在添加一个Ptr参数。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uK6PjyBu-1648974512796)(C:\Users\13136\AppData\Roaming\Typora\typora-user-images\image-20220402190825429.png)]

2.1.3 重载++/-- & ==/!=

++/–这些都比较简单，迭代器的完整代码附在这里了 ——

  1. template<classT,classRef,classPtr>struct__list_iterator{typedef ListNode<T> Node;typedef __list_iterator<T, Ref, Ptr> self;
  2.         Node* _node;__list_iterator(Node* x):_node(x){}
  4.         Ref operator*(){return _node->_data;}
  6.         Ptr operator->(){return&_node->_data;}
  8.         self&operator++(){
  9.             _node = _node->_next;return*this;}
  11.         self operator++(int){
  12.             self tmp(*this);
  13.             _node = _node->_next;return tmp;}
  15.         self&operator--(){
  16.             _node = _node->_prev;return*this;}
  18.         self operator--(int){
  19.             self tmp(*this);
  20.             _node = _node->_prev;return tmp;}booloperator==(const Self& it)const{return _node = it._node;}booloperator!=(const Self& it)const{return _node != it._node;}};

list中的begin()和end()接口 ——

  1. template<classT>classlist{typedef ListNode<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T,const T&,const T*> const_iterator;list(){
  2.             _head =new Node;
  3.             _head->_prev = _head;
  4.             _head->_next = _head;}
  5.         
  6.         iterator begin(){returniterator(_head->_next);}
  8.         iterator end(){returniterator(_head);}
  10.         const_iterator begin()const{returnconst_iterator(_head->_next);}
  12.         const_iterator end()const{returnconst_iterator(_head);}private:
  13.             Node* _head;};

2.2 reverse_iterator

反向迭代器就是对正向迭代器的封装，这样它可以是任意容器的反向迭代器。

  • 它们的不同就在于++调的是正向迭代器的–；–调的是正向迭代器的++
  • 源码中为了使正向迭代器&反向迭代器的开始和结束保持对称，解引用*取前一个位置这样做是有一定原因的，对于vector的反向迭代器，如果是我们预想的那样(解引用取的是当前位置)，会有越界访问问题。

为了获取数据类型T，我们还需要增加两个类模板参数

  1. Ref

、

  1. Ptr

。源码中不带这两个参数，是通过迭代器萃取技术实现的。

  1. #pragmaoncenamespace beatles
  2. {// 可以是任意容器的反向迭代器// Iterator是哪个容器的迭代器，reverse_iterator<Iterator>就可以适配哪个容器的反向迭代器(复用)template<classIterator,classRef,classPtr>classreverse_iterator{typedef reverse_iterator<Iterator, Ref, Ptr> self;public:reverse_iterator(Iterator it):_it(it){}
  4.         Ref operator*(){
  5.             Iterator prev = _it;return*--prev;}
  7.         Ptr operator->(){return&operator*();}
  9.         self&operator++(){--_it;return*this;}
  11.         self operator++(int){
  12.             self tmp(*this);--_it;return tmp;}
  14.         self&operator--(){
  15.             self tmp(*this);++_it;return tmp;}
  17.         self operator--(int){return++_it;}booloperator==(const self& rit)const{return _it == rit._it;}booloperator!=(const self& rit)const{return _it != rit._it;}private:
  18.         Iterator _it;};}

3. Modifiers

带头双向循环链表无死角的完美结构，使得任意位置的插入删除变得简单。

3.1 insert & erase

🍓 insert

  1.     iterator insert(iterator pos,const T& x){
  2.         Node* cur = pos._node;
  3.         Node* prev = cur->_prev;
  4.         Node* newnode =newNode(x);
  5.         
  6.         prev->_next = newnode;
  7.         newnode->_prev = prev;
  8.         newnode->_next = cur;
  9.         cur->_prev = newnode;returniterator(newnode);}
  • 返回值是newnode位置的迭代器
  • list的insert会发生迭代器失效吗？众所周知，vector中insert迭代器失效有两种原因：扩容野指针；pos意义改变。显然，list这里不会再发生迭代器失效。

🍓 erase

  1.     iterator erase(iterator pos){assert(pos !=end());
  2.         Node* prev = pos._node->_prev;
  3.         Node* next = pos._node->_next;delete pos._node;
  4.         
  5.         prev->_next = next;
  6.         next->_prev = prev;returniterator(next);}
  • 返回值是指向erase的下一个节点处的迭代器
  • erase后迭代器必然要失效，节点都被干掉了，是野指针

3.2 push_back & push_front

注意插入位置。

  1. voidpush_back(const T& x){insert(end(), x);}voidpush_front(const T& x){insert(begin(), x);}

3.3 pop_back & pop_front

注意删除位置。

  1. voidpop_back(){erase(--end());}voidpop_front(){erase(begin());}

4. list的默认成员函数

4.1 构造

🍓 无参构造

  1. list(){
  2.         _head =new Node;
  3.         _head->_prev = _head;
  4.         _head->_next = _head;}

🍓 迭代器区间构造

  1. // 迭代器区间构造template<classInputIterator>list(InputIterator first, InputIterator last){
  2.         _head =new Node;
  3.         _head->_prev = _head;
  4.         _head->_next = _head;while(first != last){push_back(*first);
  5.             first++;}}

4.2 clear() & 析构函数

🍓 clear清掉链表中所有数据，在重新进行插入，注意需要保留头结点。

  1. voidclear(){
  2.         iterator it =begin();while(it !=end()){
  3.             iterator del = it++;delete del._node;//delete (it++)._node;}//更改链接关系
  4.         _head->_prev = _head;
  5.         _head->_next = _head;}

🍓 析构函数

  1. ~list(){clear();delete _head;
  2.         _head =nullptr;}

4.3 拷贝构造

深拷贝。传统写法，利用范围for🍬尾插——

  1. //拷贝构造 - 传统写法//lt2(lt1)list(const list<T>& lt){
  2.         _head =new Node;
  3.         _head->_prev = _head;
  4.         _head->_next = _head;for(auto e : lt){push_back(e);}}

🍓 拷贝构造现代写法，需要迭代器区间构造

  1. // 拷贝构造 - 现代写法// lt2(lt1)list(const list<T>& lt){
  2.         _head =new Node;
  3.         _head->_prev = _head;
  4.         _head->_next = _head;
  6.         list<T>tmp(lt.begin(), lt.end());swap(_head, tmp._head);}

注意必须给一个头，否则_head是一个随机值，换给tmp后出作用域调用析构函数，clear时获取begin()要解引用 _head-> _next会崩溃。

4.4 赋值重载

传统写法，复用clear()和尾插 ——

  1. //赋值重载 - 传统写法//lt1 = lt3
  2.     list<T>&operator=(const list<T>& lt){if(this!=&lt){clear();//lt1for(auto e : lt){push_back(e);}}return*this;}

🍓 现代写法

  1. // 赋值重载// lt1 = lt3
  2.     list<T>&operator=(list<T> lt){swap(_head, lt._head);return*this;}

5. list & vector 区别和联系

【面试题】 list & vector的区别和联系
vectorlist互补连续的物理空间，可以随机访问，是优势也是劣势带头双向循环链表，不能随机访问1. 空间不够需要增容，增容代价比较大1. 按需申请释放空间2. 按需申请，一般是2倍左右扩容，可能存在一定的空间浪费 (reseve一定程度缓解)3. 头部和中间的插入删除需要挪动数据，效率低下2.支持任意位置O(1)的插入删除迭代器原生指针用类去封装节点指针。重载*、++等操作符，让它像指针一样

附：

list.h

  1. #pragmaonce#include<iostream>#include<assert.h>#include"reverse_iterator.h"usingnamespace std;namespace beatles
  2. {template<classT>structListNode{
  3.         ListNode<T>* _prev;
  4.         ListNode<T>* _next;
  5.         T _data;ListNode(const T& x =T()){
  6.             _prev =nullptr;
  7.             _next =nullptr;
  8.             _data = x;}};template<classT,classRef,classPtr>struct__list_iterator{typedef ListNode<T> Node;typedef __list_iterator<T, Ref, Ptr> self;
  9.         Node* _node;__list_iterator(Node* x):_node(x){}
  11.         Ref operator*(){return _node->_data;}
  13.         Ptr operator->(){return&_node->_data;}
  15.         self&operator++(){
  16.             _node = _node->_next;return*this;}
  18.         self operator++(int){
  19.             self tmp(*this);
  20.             _node = _node->_next;return tmp;}
  22.         self&operator--(){
  23.             _node = _node->_prev;return*this;}
  25.         self operator--(int){
  26.             self tmp(*this);
  27.             _node = _node->_prev;return tmp;}booloperator==(const self& it)const{return _node = it._node;}booloperator!=(const self& it)const{return _node != it._node;}};template<classT>classlist{typedef ListNode<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T,const T&,const T*> const_iterator;//把正向迭代器作为模板参数传给反向迭代器typedef reverse_iterator<const_iterator,const T&,const T*> const_reverse_iterator;typedef reverse_iterator<iterator, T&, T*> reverse_iterator;list(){
  28.             _head =new Node;
  29.             _head->_prev = _head;
  30.             _head->_next = _head;}// 迭代器区间构造template<classInputIterator>list(InputIterator first, InputIterator last){
  31.             _head =new Node;
  32.             _head->_prev = _head;
  33.             _head->_next = _head;while(first != last){push_back(*first);
  34.                 first++;}}// 拷贝构造 - 现代写法// lt2(lt1)list(const list<T>& lt){
  35.             _head =new Node;
  36.             _head->_prev = _head;
  37.             _head->_next = _head;
  39.             list<T>tmp(lt.begin(), lt.end());swap(_head, tmp._head);}// 赋值重载// lt1 = lt3
  40.         list<T>&operator=(list<T> lt){swap(_head, lt._head);return*this;}~list(){clear();delete _head;
  41.             _head =nullptr;}voidclear(){
  42.             iterator it =begin();while(it !=end()){
  43.                 iterator del = it++;delete del._node;//delete (it++)._node;}//更改链接关系
  44.             _head->_prev = _head;
  45.             _head->_next = _head;}//拷贝构造 - 传统写法//lt2(lt1)/*list(const list<T>& lt)
  46.         {
  47.             _head = new Node;
  48.             _head->_prev = _head;
  49.             _head->_next = _head;
  50.             
  51.             for (auto e : lt)
  52.             {
  53.                 push_back(e);
  54.             }
  55.         }*///赋值重载 - 传统写法//lt1 = lt3//list<T>& operator=(const list<T>& lt)//{//    if (this != &lt)//    {//        clear(); //lt1//        for (auto e : lt)//        {//            push_back(e);//        }//    }//    return *this;//}
  57.         iterator begin(){returniterator(_head->_next);}
  59.         iterator end(){returniterator(_head);}
  61.         const_iterator begin()const{returnconst_iterator(_head->_next);}
  63.         const_iterator end()const{returnconst_iterator(_head);}
  65.         reverse_iterator rbegin(){returnreverse_iterator(end());}
  66.         
  67.         reverse_iterator rend(){returnreverse_iterator(begin());}
  69.         const_reverse_iterator rbegin()const{returnconst_reverse_iterator(end());}
  71.         const_reverse_iterator rend()const{returnconst_reverse_iterator(begin());}
  73.         iterator insert(iterator pos,const T& x){
  74.             Node* cur = pos._node;
  75.             Node* prev = cur->_prev;
  76.             Node* newnode =newNode(x);
  77.             prev->_next = newnode;
  78.             newnode->_prev = prev;
  79.             newnode->_next = cur;
  80.             cur->_prev = newnode;returniterator(newnode);}voidpush_back(const T& x){/*Node* newnode = new Node(x);
  81.             Node* tail = _head->_prev;
  82.             tail->_next = newnode;
  83.             newnode->_prev = tail;
  84.             newnode->_next = _head;
  85.             _head->_prev = newnode;*/insert(end(), x);}voidpush_front(const T& x){insert(begin(), x);}
  87.         iterator erase(iterator pos){assert(pos !=end());
  88.             Node* prev = pos._node->_prev;
  89.             Node* next = pos._node->_next;delete pos._node;
  90.             prev->_next = next;
  91.             next->_prev = prev;returniterator(next);}voidpop_back(){erase(--end());}voidpop_front(){erase(begin());}private:
  92.         Node* _head;};voidprint_list(const list<int>& lt){
  93.         list<int>::const_iterator it = lt.begin();while(it != lt.end()){// *it /= 2; 不可写
  94.             cout <<*it <<" ";++it;}
  95.         cout << endl;}// 测试迭代器voidtest_list1(){
  96.         list<int> lt;
  97.          lt.push_back(1);
  98.         lt.push_back(2);
  99.         lt.push_back(3);
  100.         lt.push_back(4);
  102.         list<int>::iterator it = lt.begin();while(it != lt.end()){*it *=2;//可写
  103.             cout <<*it <<" ";++it;}
  104.         cout << endl;//测试const迭代器print_list(lt);}structDate{Date(int year =0,int month =0,int day =0):_year(year),_month(month),_day(day){}int _year;int _month;int _day;};voidtest_list2(){
  105.         list<Date> lt;
  106.         lt.push_back(Date(2022,3,31));
  107.         lt.push_back(Date(2022,3,31));
  108.         lt.push_back(Date(2022,3,31));// 遍历链表，打印日期
  109.         list<Date>::iterator it = lt.begin();while(it != lt.end()){//cout << (*it)._year << "." << (*it)._month << "." << (*it)._day << endl;
  110.             cout << it->_year <<"."<< it->_month <<"."<< it->_day << endl;
  111.             it++;}
  112.         cout << endl;}// 测试插入&删除voidtest_list3(){
  113.         list<int> lt;
  114.         lt.push_back(1);
  115.         lt.push_back(2);
  116.         lt.push_back(3);
  117.         lt.push_back(4);
  118.         lt.push_front(0);
  119.         lt.push_front(-1);for(auto e : lt){
  120.             cout << e <<" ";}
  121.         cout << endl;
  123.         lt.pop_back();
  124.         lt.pop_front();for(auto e : lt){
  125.             cout << e <<" ";}
  126.         cout << endl;}// 测试拷贝构造&赋值重载voidtest_list4(){
  127.         list<int> lt1;
  128.         lt1.push_back(1);
  129.         lt1.push_back(2);
  130.         lt1.push_back(3);
  131.         lt1.push_back(4);/*lt1.clear();
  132.         for (auto e : lt1)
  133.         {
  134.             cout << e << " ";
  135.         }
  136.         cout << endl;*/
  138.         list<int>lt2(lt1);for(auto e : lt2){
  139.             cout << e <<" ";}
  140.         cout << endl;
  142.         list<int> lt3;
  143.         lt3.push_back(10);
  144.         lt3.push_back(20);
  145.         lt3.push_back(30);
  146.         lt3.push_back(40);
  147.         lt3.push_back(50);
  148.         lt1 = lt3;for(auto e : lt1){
  149.             cout << e <<" ";}
  150.         cout << endl;}// 测试反向迭代器voidtest_list5(){
  151.         list<int> lt;
  152.         lt.push_back(1);
  153.         lt.push_back(2);
  154.         lt.push_back(3);
  155.         lt.push_back(4);
  157.         list<int>::reverse_iterator rit = lt.rbegin();while(rit != lt.rend()){
  158.             cout <<*rit <<" ";
  159.             rit++;}
  160.         cout << endl;}}

reverse_iterator.h

可以是适配成任意容器的反向迭代器，Iterator是哪个容器的迭代器，reverse_iterator< Iterator>就可以适配哪个容器的反向迭代器(复用)

  1. #pragmaoncenamespace beatles
  2. {// 可以是任意容器的反向迭代器// Iterator是哪个容器的迭代器，reverse_iterator<Iterator>就可以适配哪个容器的反向迭代器(复用)template<classIterator,classRef,classPtr>classreverse_iterator{typedef reverse_iterator<Iterator, Ref, Ptr> self;public:reverse_iterator(Iterator it):_it(it){}
  4.         Ref operator*(){
  5.             Iterator prev = _it;return*--prev;}
  7.         Ptr operator->(){return&operator*();}
  9.         self&operator++(){--_it;return*this;}
  11.         self operator++(int){
  12.             self tmp(*this);--_it;return tmp;}
  14.         self&operator--(){
  15.             self tmp(*this);++_it;return tmp;}
  17.         self operator--(int){return++_it;}booloperator==(const self& rit)const{return _it == rit._it;}booloperator!=(const self& rit)const{return _it != rit._it;}private:
  18.         Iterator _it;};}

test.cpp

  1. #define_CRT_SECURE_NO_WARNINGS1#include"list.h"intmain(){//beatles::test_list1();//beatles::test_list2();//beatles::test_list3();//beatles::test_list4();
  2.     beatles::test_list5();return0;}

💜 风尘仆仆我会化作天边的晚霞~

持续更新@边通书

标签： c++ STL list
本文转载自: https://blog.csdn.net/qq_54851255/article/details/123939684
版权归原作者 呀小边同学 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【C++】list的模拟实现@STL &mdash;&mdash; 迭代器”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？