额额额,浅学了list,老规矩,模拟实现一下list,能让我们更好的理解list。若有兴趣,不妨垂阅!
目录
1.模拟实现list
1.1.list节点
1.2.list正向迭代器
1.3.list模拟实现
2. test
3.小知识
3.1.小知识1
3.2.小知识2
3.3. 小知识3
4.模拟实现list完整代码
同样的,我不可能把list所有接口都模拟实现出来,我也没有这个能力。So,模拟实现一些简单常用的接口。
本工程包括2个文件:
mylist.h:用于模拟实现list。
test.cpp:用于测试模拟实现的list接口是否达到预期。
1.模拟实现list
以下代码均放到mylist.h文件中。
1.1.list节点
由于list底层是带头(哨兵位)双向循环链表。所以模拟实现的list节点需要能找到前驱节点和后继节点,这点是毋庸置疑的。那么,我们将list节点设计如下:
namespace HD
{//list节点template<typename T>struct listNode{typedef listNode node;//类里面可以将listNode<T>用listNode替代T _val;node* _prev;node* _next;};
}
_val用于存储数据,_prev用于指向前驱节点,_next用于指向后继指针。
1.2.list正向迭代器
好的,由于list反向迭代器较为复杂,所以我只模拟实现正向迭代器。正向迭代器分为:普通正向迭代器、const正向迭代器。一个一个来模拟实现:
1.普通正向迭代器
我们知道迭代器是模拟指针的行为,但是却不是所有的迭代器都能直接用原生指针实现。例如:
string的正向迭代器,由于其底层是字符顺序表,可以直接用原生指针来实现迭代器;
但是如list底层是链表,正向迭代器就不能直接用原生指针实现,好比如,list<int>::iterator it; ++it;,如果该list的正向迭代器是原生指针实现的,++操作能让it指向下一个节点吗?显然不能,因为链表的物理空间不是连续的。
那么我们怎么办?
别忘了操作符重载这里利器,我们可以用类封装一下原生指针来实现普通正向迭代器:
namespace HD
{//list 普通正向迭代器template <typename T>struct listIterator{typedef listNode<T>* pNode;typedef listIterator<T> self;pNode _pNode;listIterator<T>(pNode pNode = nullptr):_pNode(pNode){}T& operator*(){return (*_pNode)._val;}self operator++(int)//后置++{self it(_pNode);_pNode = _pNode->_next;return it;}self& operator++()//前置++{_pNode = _pNode->_next;return *this;}self operator--(int)//后置--{self it(_pNode);_pNode = _pNode->_prev;return it;}self& operator--()//前置--{_pNode = _pNode->_prev;return *this;}bool operator!=(const self& it){return _pNode != it._pNode;}bool operator==(const self& it){return _pNode == it._pNode;}T* operator->(){return &_pNode->_val;}};
}
其实仔细看,这个类只有一个成员变量,就是list节点的指针_pNode。把这个指针用类封装一下,提供各种运算符重载作为该类的成员函数,就成了。本质上,这个类不还是list节点指针吗?但是这个list节点指针的行为却不是原生指针的行为能达到的。。。。。好好体会!!!!
2.const正向迭代器
普通正向迭代器和const正向迭代器基本一样。我们想想,const正向迭代器区别于普通正向迭代器,无非就是const正向迭代器指向的节点存储的数据不能更改吗?
SO:
namespace HD
{//list const正向迭代器template <typename T>struct listConstIterator{typedef listNode<T>* pNode;typedef listConstIterator<T> self;pNode _pNode;listConstIterator<T>(pNode pNode = nullptr):_pNode(pNode){}const T& operator*(){return (*_pNode)._val;}self operator++(int)//后置++{self it(_pNode);_pNode = _pNode->_next;return it;}self& operator++()//前置++{_pNode = _pNode->_next;return *this;}self operator--(int)//后置--{self it(_pNode);_pNode = _pNode->_prev;return it;}self& operator--()//前置--{_pNode = _pNode->_prev;return *this;}bool operator!=(const self& it){return _pNode != it._pNode;}bool operator==(const self& it){return _pNode == it._pNode;}const T* operator->(){return &_pNode->_val;}};
}
仔细看,实现起来跟普通正向迭代器的区别就在于operator*和operator->这2个函数的返回值不同罢了。至于operator->这个函数到底干啥的,一会儿说的。
3.普通正向迭代器和const正向迭代器合二为一
看到普通正向迭代器和const正向迭代器这两个类模板基本一样,那么我们完全可以写一个类模板来代替以上2个类模板:
namespace HD
{//list正向迭代器template <typename T,typename Ref,typename Ptr>struct listIterator{typedef listNode<T>* pNode;typedef listIterator<T,Ref,Ptr> self;pNode _pNode;listIterator<T,Ref,Ptr>(pNode pNode=nullptr):_pNode(pNode){}Ref operator*(){return (*_pNode)._val;}self operator++(int)//后置++{self it(_pNode);_pNode = _pNode->_next;return it;}self& operator++()//前置++{_pNode = _pNode->_next;return *this;}self operator--(int)//后置--{self it(_pNode);_pNode = _pNode->_prev;return it;}self& operator--()//前置--{_pNode = _pNode->_prev;return *this;}bool operator!=(const self& it){return _pNode != it._pNode;}bool operator==(const self& it){return _pNode == it._pNode;}Ptr operator->(){return &_pNode->_val;}};
}
通俗易懂讲,当Ref、Ptr是T&、T*的时候,不就是普通正向迭代器吗?
当Ref、Ptr是const T&、const T*的时候,不就是const正向迭代器吗?
1.3.list模拟实现
namespace HD
{//listtemplate<typename T>class list{private:typedef listNode<T> node;typedef listNode<T>* pNode;typedef T value_type;typedef size_t size_type;private:pNode _pHead;size_t _size;public:typedef listIterator<T,T&,T*> iterator;typedef listIterator<T,const T&,const T*> const_iterator;public:void emptyInit(){_pHead = new node;_pHead->_prev = _pHead;_pHead->_next = _pHead;_size = 0;}list(){emptyInit();}list(size_type n, const value_type& val=value_type()){emptyInit();while (n--){push_back(val);}}list(const list& x){emptyInit();pNode cur = x._pHead->_next;while (cur != x._pHead){push_back(cur->_val);cur = cur->_next;}}void swap(list& x){std::swap(x._pHead, _pHead);std::swap(x._size, _size);}list& operator=(list x) {swap(x);return *this;}void push_back(const value_type& val){/*pNode end = _pHead->_prev;pNode newNode = new node;newNode->_val = val;end->_next = newNode;newNode->_prev = end;_pHead->_prev = newNode;newNode->_next = _pHead;_size++;*/insert(_pHead, val);}void push_front(const value_type& val){insert(_pHead->_next, val);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}size_type size()const{return _size;}bool empty()const{return _size == 0;}iterator begin(){/*iterator it(_pHead->_next);return it;*//*return iterator(_pHead->_next);//匿名对象*/return _pHead->_next;}iterator end(){/*iterator it(_pHead);return it;*//*return iterator(_pHead);//匿名对象*/return _pHead;}const_iterator begin()const{return _pHead->_next;}const_iterator end()const{return _pHead;}void clear(){while (size() != 0){pop_back();}}~list(){clear();delete _pHead;_pHead = nullptr;_size = 0;}iterator insert(iterator position, const value_type& val);iterator erase(iterator position);};template <typename T>typename list<T>::iterator list<T>::insert(list<T>::iterator position, const list<T>::value_type& val){pNode cur = position._pNode;pNode prev = position._pNode->_prev;pNode newNode = new node;newNode->_val = val;newNode->_next = cur;cur->_prev = newNode;newNode->_prev = prev;prev->_next = newNode;_size++;return position--;}template<typename T>typename list<T>::iterator list<T> ::erase(list<T>::iterator position){assert(position != end());//不能erase哨兵位节点pNode prev = position._pNode->_prev;pNode next = position._pNode->_next;delete position._pNode;prev->_next = next;next->_prev = prev;_size--;return next;}
}
有点长啊。。 2个成员变量:_pHead是哨兵位的指针,_size是节点个数(不包括哨兵位)。insert和erase采用声明和定义分离,其他成员函数声明和定义不分离。
2. test
在test.cpp中测试一下list正向迭代器中的operator*和operator->这2个接口:
1.operator*
对于list的普通正向迭代器:
#include"mylist.h"
namespace HD
{void test(){list<size_t> l(3, 10);list<size_t>::iterator it = l.begin();while (it != l.end()){(*it)++;cout << *it << ' ';it++;}cout << endl;}
}
int main()
{HD::test();return 0;
}
没什么问题吧:
对于list的const正向迭代器:
#include"mylist.h"
namespace HD
{void test(){const list<size_t> l(3, 10);list<size_t>::const_iterator it = l.begin();while (it != l.end()){(*it)++;cout << *it << ' ';it++;}cout << endl;}
}
int main()
{HD::test();return 0;
}
运行错误了:
问题就出现在*it的类型是const size_t&,不能修改,这就区别于普通正向迭代器了。
如果这样:
#include"mylist.h"
namespace HD
{void test(){const list<size_t> l(3, 10);list<size_t>::const_iterator it = l.begin();while (it != l.end()){cout << *it << ' ';it++;}cout << endl;}
}
int main()
{HD::test();return 0;
}
没什么问题,可以实现遍历list容器的功能:
2.operator->
对于操作符->,我们的使用场景一般是在于结构体指针访问其指向变量的成员,像这样子:
#include"mylist.h"
namespace HD
{struct example{int _a = 1;int _b = 2;};void test(){auto E = new example;cout << E->_a << ' ' << E->_b << endl;}
}
int main()
{HD::test();return 0;
}
我们希望迭代器也能这样子,所以重载了->操作符。
对于list的普通正向迭代器:
#include"mylist.h"
namespace HD
{struct example{int _a = 1;int _b = 2;};void test(){list<example> l(3);auto it = l.begin();while (it != l.end()){it->_a++; it->_b++;//奇怪*2?cout << it->_a << ' ' << it->_b << " ";//奇怪?it++;}}
}
int main()
{HD::test();return 0;
}
先看一下运行结果:
运行成功了,但是细细分析,感觉怪怪的。看到operator->的定义:
Ptr operator->(){return &_pNode->_val;}
返回list节点_val的地址。那么这里的_val的类型是example,返回一个自定义类型指针example*。那么it->_a翻译过来就是example*_a,这是个啥玩意?关键还运行成功了。
其实编译器对这里作了特殊处理,本来应该是2个->才合乎语法,为了可读性,省略了后1个->。其实这里编译器省略了后1个->,在编译器看来,代码是这样子的:
#include"mylist.h"
namespace HD
{struct example{int _a = 1;int _b = 2;};void test(){list<example> l(3);auto it = l.begin();while (it != l.end()){//在编译器看来,等价于it->_a++;it->_b++;it.operator->()->_a++; it.operator->()->_b++;//在编译器看来,等价于cout<<it->_a<<' '<<it->_b<<" ";cout << it.operator->()->_a << ' ' << it.operator->()->_b << " ";it++;}}
}
int main()
{HD::test();return 0;
}
也是可以运行成功的:
仔细体会一下,迭代器是不是在模拟指针的行为?
对于list的const正向迭代器:
#include"mylist.h"
namespace HD
{struct example{int _a = 1;int _b = 2;};void test(){const list<example> l(3);auto it = l.begin();while (it != l.end()){it->_a++; it->_b++;cout << it->_a << ' ' << it->_b << " ";it++;}}
}
int main()
{HD::test();return 0;
}
运行不成功:
问题就在于it->返回值类型为const example* ,这不就区别于普通正向迭代器了吗?
虽然不能通过list的const正向迭代器来修改list容器的值,但是用来遍历list容器是没问题的:
#include"mylist.h"
namespace HD
{struct example{int _a = 1;int _b = 2;};void test(){const list<example> l(3);auto it = l.begin();while (it != l.end()){cout << it->_a << ' ' << it->_b << " ";it++;}}
}
int main()
{HD::test();return 0;
}
3.小知识
3.1.小知识1
讨论1个问题:const迭代器为什么是单独搞了一个类型const_iterator,而不是直接用const修饰普通迭代器?
const iterator:迭代器本身不能修改,若是直接用const修饰普通迭代器当作const迭代器,那么const迭代器就不能用来遍历容器了。
const_iterator:希望指向的内容不能修改,实际上const迭代器也是这样子实现的,例如如上模拟实现。这样子的话const迭代器本身是能修改的,可以可以用来遍历容器。
3.2.小知识2
list迭代器失效问题:
list容器迭代器失效即迭代器所指向的节点的无效,即该节点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入 时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响。
例如说,erase、pop_back、pop_front等操作都会导致迭代器失效,例如在test.cpp中:
#include"mylist.h"
namespace HD
{void test(){list<int> l(3, 10);auto it = l.begin();while (it != l.end()){//erase()函数执行后,it所指向的节点已被删除,//因此it无效,在下一次使用it时,必须先给其赋值l.erase(it);it++;}}
}
int main()
{HD::test();return 0;
}
改正写法:
#include"mylist.h"
namespace HD
{void test(){list<int> l(3, 10);auto it = l.begin();while (it != l.end()){it = l.erase(it);//或者l.erase(it++);}}
}
int main()
{HD::test();return 0;
}
同样的,VS2022对std::list的erase进行了强制的检查,若erase后,没有更新迭代器就访问会报错,在test.cpp中:
#include"mylist.h"
namespace HD
{void test(){std::list<int> l(3, 10);auto it = l.begin();while (it != l.end()){l.erase(it);it++;}}
}
int main()
{HD::test();return 0;
}
所以使用std::list容器时,若是erase等删除操作后想要访问迭代器,请更新!
在list插入,如insert、push_back、push_front等操作,不会使得迭代器失效,所以VS2022对于std::list的insert等操作后也没有对其迭代器是否更新过进行检查。
3.3. 小知识3
按需实例化:
当模板没有实例化,就算模板内有错误,也不一定会报错,对于模板内明显的错误一般会检查出来,例如缺少一个分号这些明显错误;但是一下细节的错误就不一定能检查出来。如:
在test.cpp中,写了一个函数模板用于打印模拟实现的list对象;
#include"mylist.h"
namespace HD
{template<class T>void printList(const list<T>& list){auto it = list.begin();while (it != list.end()){(*it)++;//错误cout << *it << ' ';}cout << endl;}
}
int main()
{return 0;
}
如上代码,有细节错误:list的类型是const list<T>&,显然其值不能修改,但是*it++却想要修改。但是这个模板没有实例化,所以运行不报错:
如果让这个模板实例化一下,肯定会报错:
#include"mylist.h"
namespace HD
{template<class T>void printList(const list<T>& list){auto it = list.begin();while (it != list.end()){(*it)++;cout << *it << ' ';}cout << endl;}void test(){list<int> l(3, 5);printList(l);}
}
int main()
{HD::test();return 0;
}
且看:error C3892: “it”: 不能给常量赋值 ,并且:
4.模拟实现list完整代码
在mylist.h文件下:
#pragma once
#include<iostream>
#include<assert.h>
#include<list>
using namespace std;
namespace HD
{//list节点template<typename T>struct listNode{typedef listNode node;//类里面可以将listNode<T>用listNode替代T _val;node* _prev;node* _next;};//list正向迭代器template <typename T,typename Ref,typename Ptr>struct listIterator{typedef listNode<T>* pNode;typedef listIterator<T,Ref,Ptr> self;pNode _pNode;listIterator<T,Ref,Ptr>(pNode pNode=nullptr):_pNode(pNode){}Ref operator*(){return (*_pNode)._val;}self operator++(int)//后置++{self it(_pNode);_pNode = _pNode->_next;return it;}self& operator++()//前置++{_pNode = _pNode->_next;return *this;}self operator--(int)//后置--{self it(_pNode);_pNode = _pNode->_prev;return it;}self& operator--()//前置--{_pNode = _pNode->_prev;return *this;}bool operator!=(const self& it){return _pNode != it._pNode;}bool operator==(const self& it){return _pNode == it._pNode;}Ptr operator->(){return &_pNode->_val;}};list const正向迭代器//template <typename T>//struct listConstIterator//{// typedef listNode<T>* pNode;// typedef listConstIterator<T> self;// pNode _pNode;// listConstIterator<T>(pNode pNode = nullptr)// :_pNode(pNode)// {// }// const T& operator*()// {// return (*_pNode)._val;// }// self operator++(int)//后置++// {// self it(_pNode);// _pNode = _pNode->_next;// return it;// }// self& operator++()//前置++// {// _pNode = _pNode->_next;// return *this;// }// self operator--(int)//后置--// {// self it(_pNode);// _pNode = _pNode->_prev;// return it;// }// self& operator--()//前置--// {// _pNode = _pNode->_prev;// return *this;// }// bool operator!=(const self& it)// {// return _pNode != it._pNode;// }// bool operator==(const self& it)// {// return _pNode == it._pNode;// }// const T* operator->()// {// return &_pNode->_val;// }//};//list 普通正向迭代器//template <typename T>//struct listIterator//{// typedef listNode<T>* pNode;// typedef listIterator<T> self;// pNode _pNode;// listIterator<T>(pNode pNode = nullptr)// :_pNode(pNode)// {// }// T& operator*()// {// return (*_pNode)._val;// }// self operator++(int)//后置++// {// self it(_pNode);// _pNode = _pNode->_next;// return it;// }// self& operator++()//前置++// {// _pNode = _pNode->_next;// return *this;// }// self operator--(int)//后置--// {// self it(_pNode);// _pNode = _pNode->_prev;// return it;// }// self& operator--()//前置--// {// _pNode = _pNode->_prev;// return *this;// }// bool operator!=(const self& it)// {// return _pNode != it._pNode;// }// bool operator==(const self& it)// {// return _pNode == it._pNode;// }// T* operator->()// {// return &_pNode->_val;// }//};//listtemplate<typename T>class list{private:typedef listNode<T> node;typedef listNode<T>* pNode;typedef T value_type;typedef size_t size_type;private:pNode _pHead;size_t _size;public:typedef listIterator<T,T&,T*> iterator;typedef listIterator<T,const T&,const T*> const_iterator;public:void emptyInit(){_pHead = new node;_pHead->_prev = _pHead;_pHead->_next = _pHead;_size = 0;}list(){emptyInit();}list(size_type n, const value_type& val=value_type()){emptyInit();while (n--){push_back(val);}}list(const list& x){emptyInit();pNode cur = x._pHead->_next;while (cur != x._pHead){push_back(cur->_val);cur = cur->_next;}}void swap(list& x){std::swap(x._pHead, _pHead);std::swap(x._size, _size);}list& operator=(list x) {swap(x);return *this;}void push_back(const value_type& val){/*pNode end = _pHead->_prev;pNode newNode = new node;newNode->_val = val;end->_next = newNode;newNode->_prev = end;_pHead->_prev = newNode;newNode->_next = _pHead;_size++;*/insert(_pHead, val);}void push_front(const value_type& val){insert(_pHead->_next, val);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}size_type size()const{return _size;}bool empty()const{return _size == 0;}iterator begin(){/*iterator it(_pHead->_next);return it;*//*return iterator(_pHead->_next);//匿名对象*/return _pHead->_next;}iterator end(){/*iterator it(_pHead);return it;*//*return iterator(_pHead);//匿名对象*/return _pHead;}const_iterator begin()const{return _pHead->_next;}const_iterator end()const{return _pHead;}void clear(){while (size() != 0){pop_back();}}~list(){clear();delete _pHead;_pHead = nullptr;_size = 0;}iterator insert(iterator position, const value_type& val);iterator erase(iterator position);};template <typename T>typename list<T>::iterator list<T>::insert(list<T>::iterator position, const list<T>::value_type& val){pNode cur = position._pNode;pNode prev = position._pNode->_prev;pNode newNode = new node;newNode->_val = val;newNode->_next = cur;cur->_prev = newNode;newNode->_prev = prev;prev->_next = newNode;_size++;return position--;}template<typename T>typename list<T>::iterator list<T> ::erase(list<T>::iterator position){assert(position != end());//不能erase哨兵位节点pNode prev = position._pNode->_prev;pNode next = position._pNode->_next;delete position._pNode;prev->_next = next;next->_prev = prev;_size--;return next;}
}
感谢阅读!