手机单页面网站模板,互动营销公司,wordpress用网站测速,建设个人网站iplist模拟实现list原理讲解节点结构list类设计push_backIterators:begin与endconst对象的迭代器重载-运算符反向迭代器迭代器所有代码迭代器总结constructor:clear~listfront与backinsert与erasesize与empty与swappop_back()总代码:节点类正向迭代器类反向迭代器类list类lis…
list模拟实现list原理讲解节点结构list类设计push_backIterators:begin与endconst对象的迭代器重载-运算符反向迭代器迭代器所有代码迭代器总结constructor:clear~listfront与backinsert与erasesize与empty与swappop_back()总代码:节点类正向迭代器类反向迭代器类list类list原理讲解
在C中SGI版本的STL中的list容器是用带头双向循环链表来实现的 那么什么是带头双向循环链表 如下图 该链表有一个head头节点该节点不存储任何有效数据仅用于链接第一个有效节点和最后一个有效节点head的前一个节点就是该链表的最后一个有效节点head的后一个节点就是该链表的第一个有效节点 只要我们能够找到head节点我们就能找到整条带头双向循环链表 使用该结构存储数据的话插入和删除数据都非常的快时间复杂度为O(1) 相比于前面的vector来说vector的插入和删除数据效率都比较低当我们需要进行大量的插入和删除数据的时候我们可以考虑使用list数据结构
节点结构
该节点有数据域和指针域其中数据域专门用来存储数据指针域细分的话又有两个指针域前指针域用于存储前一个节点的指针、后指针域用于存储后一个节点的指针 因此我们可以这样设置节点数据结构
//节点template class Tstruct list_node{T _date;list_nodeT* _prev;list_nodeT* _next;list_node(const T val T())//这里可以考虑使用缺省参数//由于模板的出现这就要求了对于内置类型必须提供构造函数不然的话对于这种情况const T val T()我们无法处理因为我们不知道T的具体类型是什么无法准确的给缺省值同时const引用可以延长匿名对象的生命周期直到引用所在作用域销毁:_date(val), _prev(nullptr), _next(nullptr) {}};我们可以用一个模板来写一个节点数据结构因为节点的数据域可以存储任何类型的数据同时我们可以为该节点提供一个构造函数方便后续向节点插入数据的需求 同时这里我们用了struct来创建节点类不用class是因为struct创建的类的默认权限是public更为方便我们后续的操作class创建的类的默认权限是private的当我们将类内部的成员全部放开时我们可以利用struct来创建类当然也可以用class只不过这时候我们需要加上public访问限定符
list类设计
list类也应该成一个模板类因为list可以插入任何类型的元素
template class T
{
public:
private:
//list的成员我们可以设计为一个list_nodeT*的指针
//该指针用于存储带头双向循环链表的head节点
//只要我们找到了head节点我们就能找到整条链表
//list_nodeT * _head;//当然这里我们可以考虑typedef一下list_nodeT毕竟这个类型太长了写起来比较麻烦当然我们也可以不typedef直接使用原生类型
typedef list_nodeT node;
node*_head;
}既然list类成员已经设计出来了那么我们现在就创建一个带头双向循环链表来玩一玩 首先要有一个带头双向循环链表我们就得现有一个head节点方便我们list对于整条链表的管理 因此我们的构造函数可以写成
list()
{
_headnew node;//创建一个头节点
_head-_prev_head-_next_head;//让其头节点的_next指针和_prev指针都指向自己因为现在一个元素也没有_head的下一个节点就是自己_head的前一个节点也是自己
}push_back
在上面我们已经实现出list的一个简单无参构造函数,我们现在就有了_head节点我们现在就只需要插入元素了对于插入元素来说很简单
要实现尾插就需要找到最后一个一个节点那么最后一个节点在哪里 _head-_prev不就是最后一个节点嘛最后在将new_node节点的_next域链接向_head节点_head的_prev域链接向new_node节点就可以了
void push_back(const Tval)
{node*new_nodenew node(val);node*tail_head-_prev;//尾节点tail-_nextnew_node;new_node-_prevtail;new_node-_next_head;_head-_prevnew_node;
}Iterators:
现在我们已经可以向list里面插入元素了但是我们想打印一下list元素以此来检查一下我们push_back的正确性 为此我们就要遍历整个链表,遍历的话我们就需要迭代器可是现在有个问题我们应该拿什么作为迭代器呢 原生的节点指针(list_nodeT*)吗? 如果是这样的话,那么迭代器该如何往后迭代呢?要知道迭代器只允许使用、–等迭代方式是不允许-这样的迭代方式的但是我们使用、–等方式对我们的迭代器进行迭代的话我们能保证it就是下一个节点的指针吗这显然是无法保证的因为节点与节点之间都是不连续的it自然也就无法保证过后就一定是下一个节点的指针但凡list的结构是类似于vector、string的连续空间我们都可以使用原生指针来充当迭代器但对于list不行因此list中使用原生指针作为迭代器的想法被直接pass掉 那么有没有什么既可以指向对应节点同时又能使用、–来进行迭代的东西呢 当然有我们可以对原生指针进行封装封装成一个类让这个类充当迭代器然后在这个类内部重载、–等运算符以此来实现迭代器的迭代 事不宜迟咱们现在就来干一个:
template class T//元素类型
struct _list_iterator
{ //用于初始化迭代器_list_iterator(list_nodeT* nodenullptr):_node(node){}//由于_list_iteratorT 这个迭代器类型使用起来比较麻烦有需要大量的使用我们这里解直接typedef一下typedef _list_iteratorT self;//self就表示迭代器的类型本质还是_list_iteratorT//开始重载、--、*、!等运算符selfoperator()//前置{assert(_node);//防止_node为nullptr避免出现这种情况_list_iterator it;//此时it会调用无参构造_node会被初始化成nullptr这时候如果再使用it就会对nullptr解引用会崩溃_node_node-_next;return *this;}self operator(int)//后置{assert(_node);self tmp(*this);//这里可以使用默认拷贝构造,因为在迭代器类中不会对节点进行析构(*this);return tmp;}T operator*()//对迭代器解引用返回数据域的值{assert(_node);return _node-_date;}bool operator!(const selfit)//两个迭代器之间进行比较{//这也是迭代器继续迭代比较运算符//对于list这类迭代器就不在适合使用、等运算符进行比较了因为节点不是连续的return _node!it._node;}selfoperator--()//前置--{assert(_node);_node_node-_prev;return *this;}self operator(int)//后置--{assert(_node);self tmp(*this);//这里可以使用默认拷贝构造,因为在迭代器类中不会对节点进行析构--(*this);return tmp;}//成员变量list_nodeT *_node;//用于存储当前迭代器所迭代的位置
}实现了迭代器我们就可以在list类内部使用了不过我们需要先将我们实现的迭代器的名字在list类内部typedef一下因为STL的所有容器的迭代器都是iterator这算是一种默认的规范 在list内部加上:
typedef _list_iteratorT iterator;begin与end
有了迭代器在list内部的begin与end函数就可以写了
iterator begin()
{
return iterator(_head-_next);
}
iteratro end()
{
return iterator(_head);
}const对象的迭代器
我们上面实现的迭代器还是有缺陷的比如上面的begin与end我们只是实现了普通list对象对于const对象也无法调用begin、end换而言之const不能使用迭代器进行迭代只有普通list对象可以 那么有读者就说const对象调不了begin、end是因为begin、end的this指针权限过大我们在重载一个const对象的begin、end不就好了
iterator begin()const
{
return iterator(_head-_next);
}
iteratro end()const
{
return iterator(_head);
}嗯这样的话const对象确实能够进行迭代了可是新问题又来了(*迭代器)的时候也能改变迭代器所指节点的值因为operator*的返回值是T嗯这似乎与我们的预期相违背了const对象的值怎么能通过迭代去修改呢我们必须解决这个问题 我们可以不可在普通迭代器前面加个const来充当const对象的迭代器呢 比如
typedef _list_iteratro iterator;
//iterator不是普通对象的迭代器嘛
//那么const对象的迭代器可不可以是:
typedef const _list_iteratro const_iterator;
//const _list_iteratro 来充当const对象的迭代器
//答不可以如果我们这样做了的话我们迭代器本身就无法完成迭代了
//迭代器本身都无法完成迭代那还叫个屁的迭代器
//这就好比int a10;与const int b10
//a可以实现、--但是b就不可以怎么解决呢 1、重新为const对象协议一个迭代器其中operator*的返回值设置为const T ; 2、按照方法1确实可以解决问题可是太麻烦了你看嘛我们const迭代器与普通对象的迭代器都需要实现、–等迭代操作但是这两个迭代器的唯一区别就是operator*()的返回值const迭代器是const T ,而普通迭代器是T 二者之间就差一个const要是我们能用一个“变量”来控制operator*的返回值就好了 那么能不能实现呢 当然可以我们可以在_list_iterator模板参数列表再添加一个参数Ref以此来控制operator*的返回值但我们给_list_iterator类模板传入不同的参数时_list_iterator类模板就会给我们实例化出不同的具体类型 因此我们的迭代器可以优化成
template class T,class Ref
struct _list_iterator
{ //用于初始化迭代器_list_iterator(list_nodeT* nodenullptr):_node(node){}//由于_list_iteratorT 这个迭代器类型使用起来比较麻烦有需要大量的使用我们这里解直接typedef一下typedef _list_iteratorT,Ref self;//self就表示迭代器的类型本质还是_list_iteratorT,Ref//开始重载、--、*、!等运算符selfoperator()//前置{assert(_node);//防止_node为nullptr避免出现这种情况_list_iterator it;//此时it会调用无参构造_node会被初始化成nullptr这时候如果再使用it就会对nullptr解引用会崩溃_node_node-_next;return *this;}self operator(int)//后置{assert(_node);self tmp(*this);//这里可以使用默认拷贝构造,因为在迭代器类中不会对节点进行析构(*this);return tmp;}Ref operator*()//对迭代器解引用返回数据域的值,根据Ref的不同来决定operator\*()的返回值类型{assert(_node);return _node-_date;}bool operator!(const selfit)//两个迭代器之间进行比较{//这也是迭代器继续迭代比较运算符//对于list这类迭代器就不在适合使用、等运算符进行比较了因为节点不是连续的return _node!it._node;}selfoperator--()//前置--{assert(_node);_node_node-_prev;return *this;}self operator(int)//后置--{assert(_node);self tmp(*this);//这里可以使用默认拷贝构造,因为在迭代器类中不会对节点进行析构--(*this);return tmp;}//成员变量list_nodeT *_node;//用于存储当前迭代器所迭代的位置
}这样的话再list内部我们就需要重新实例化一下普通对象与const对象的迭代器了:
typedef _list_iteratorT,T iterator;//普通list对象的迭代器
typedef _list_iteratorT,const T const_iterator;//const对象的迭代器
//由于传递的模板参数不同_list_iteratorclass T,class Ref会实例化出两份不同类型的迭代器重载-运算符
对于list迭代器来说我们可以说是模拟原生指针的行为比如(*迭代器)返回的就是节点数据域的值 那么如果现在有一个结构体:
struct AA
{
int _a;
int _b;AA(int a0;int b0):_a(a),_b(b){}
}
int main()
{listint l1;l1.push_back(AA(1,2));listint :: iterator itl1.begin();//正常写法://std::cout(*it)._a (*it)._bstd::endl;//可是现在我们嫌弃上面那种方法比较麻烦我们可不可以直接使用下面这种方法来实现呢std::coutit-_a it-_bstd::endl;//答案是可以的因此在迭代器内部,我们需要重载-运算符
}迭代器内部重载-运算符
T*operator-()
{
return _node-date;
}我们只有实现了上诉部分的运算符重载我们才能直接使用: std::coutit-_a it-_bstd::endl;语句 可是我们仔细观察一下operator-的返回值就会发现很奇怪的地方operator-的返回值是T*,那么正确访问_a成员的方式不应该是:it--_a 不应该是两个箭头吗为什么这里只需要一个-就可以这里的话就与重载-的特殊性有关了建议观看大佬的这篇文章:C箭头(-)重载函数这位大佬讲的很明白 现在又有个问题如果const对象的迭代使用operator-()函数的或是不是也会改变节点数据域的值 因为operator-的返回值是T*没有const限制为此为了限制这一“漏洞”我们可以效仿operator*()返回值的作法在增加一个模板参数那么_list_iterator就会被优化成
templateclass T,class Ref,class Ptr
struct _list_iterator{_list_iterator(list_nodeT* node nullptr):_node(node) {}typedef _list_iteratorT, Ref, Ptr self;self operator(){_node _node-_next;return *this;}self operator--(){_node _node-_prev;return *this;}self operator--(int){self tmp *this;--*this;return tmp;}self operator(int){self tmp *this;* this;return tmp;}bool operator!(const self it){return _node ! it._node;}Ref operator*(){return _node-_date;}Ptr operator-(){return _node-_date;}//成员list_nodeT* _node;};在list内部普通迭代器与const迭代器的原生类型就是
typedef _list_iteratorT, T, T* iterator; //这是个普通对象的正向迭代器
typedef _list_iteratorT, const T, const T* const_iterator;//const对象的正向迭代器反向迭代器
我们发现上面实现的迭代器操作就是向后迭代、–等操作就是向前迭代妥妥的正向迭代器可是反向迭代器嘞 反向迭代器也可以按照上面的方法来实现只不过反向迭代器内部可以封装一个正向迭代器正向迭代器的就是反向迭代器的–正向迭代器的–就是反向迭代器的 //反向迭代器templateclass Forward_iterators, class Ref, class Ptr//Forward_iterators是个正向迭代器那么到底是普通对象的正向迭代器还是const对象的正向迭代器我们是未知的全靠程序员利用该模板实例化的时候给该模板参数传递的类型Ref、Ptr与上面在正向迭代器中的意义一样struct _list_reverse_iterator{_list_reverse_iterator(const Forward_iterators it Forward_iterators()):_it(it) {}typedef _list_reverse_iteratorForward_iterators, Ref, Ptr Reself;//反向迭代器类型名字太长了换个简短点的Reself operator()//前置{//正向迭代器的----_it;return *this;}Reself operator(int)//后置{Reself tmp(_it);--_it;return tmp;}Reself operator--()//前置{//正向迭代器的--_it;return *this;}Reself operator--(int)//后置{Reself tmp(_it);_it;return tmp;}Ref operator*(){return *_it;}Ptr operator-(){return _it.operator-();}bool operator!(const Reselfrit){return _it ! rit._it;}bool operator(const Reself rit){return _itrit;}//成员是一个正向迭代器;Forward_iterators _it;};因此在list内部的我们需要实例化一下普通对象的反向迭代器、和const对象的反向迭代器:
typedef _list_reverse_iteratoriterator, T, T* reverse_iterator;//普通对象反向迭代器
typedef _list_reverse_iteratorconst_iterator, const T, const T* const_reverse_iterator;//const对象反向迭代器
//给_list_reverse_iteratorForward_iterators ,Ref,Ptr传递的模板参数不同就能实例化出不同类型的反向迭代器迭代器所有代码 iterator begin(){return iterator(_head-_next);}iterator end(){return iterator(_head);}const_iterator begin()const{return const_iterator(_head-_next);}const_iterator end()const{return const_iterator(_head);}reverse_iterator rbegin(){return reverse_iterator(_head-_prev);}reverse_iterator rend(){return reverse_iterator(_head);}const_reverse_iterator rbegin()const{return const_reverse_iterator(_head-_prev);}const_reverse_iterator rend()const{return const_reverse_iterator(_head);}迭代器总结 迭代器主要有两种形式 1、迭代器要么就是原生指针 2、迭代器要么就是自定义类型对原生指针的封装模拟指针的行为 constructor:
list这个容器难点就在于迭代器现在我们把迭代器给啃了后面就好办了 注意在每次初始化list的时候都需要创建头节点为此我们可以把创建头节点的操作封装在一个函数里面 创建头节点
void empty_init(){_head new node;_head-_next _head-_prev _head;}同时我们可以把该函数放在private作用域下不对外开放 无参构造:
list()
{empty_init();
}有参构造(利用n个val来初始化) list(int n, const T val T()){empty_init();for (int i 0; i n; i){push_back(val);}}区间构造(可以用任何容器的元素来进行构造只要可以发生类型转换):
template class InputIteratorlist(InputIterator first, InputIterator last){empty_init();while (first ! last){push_back(*first);first;}}拷贝构造
list(const listT l){//现代写法的拷贝构造empty_init();listT tmp(l.begin(),l.end());//先让tmp去调用区间构造创建一个带头双向双向循环链表//然后交换tmp对象中_head与*this对象中_head的值//相当于让*this中的_head指向了tmp创建的带头双向循环链表//tmp中的_head指向*this创建的带头双向循环链表(只不过只有头而已)swap(tmp);}clear
功能:清除所有节点但是不清除头节点让整个链表的size变为0 void clear(){iterator it begin();while (it ! end()){iterase(it);}_head-_next _head-_prev _head;}~list
析构函数与clear的功能类似但是析构函数需要释放头节点
~list(){clear();delete _head;_head nullptr;}front与back
获取头节点元素与尾节点元素
T front(){assert(empty() false);return _head-_next-_date;}const T front()const{assert(empty() false);return _head-_next-_date;}T back(){assert(empty() false);return _head-_prev-_date;}const T back()const{assert(empty() false);return _head-_prev-_date;}insert与erase //insert过后的pos失效返回新插入节点的迭代器iterator insert(iterator pos, const T val){node* prev pos._node-_prev;node* new_node new node(val);prev-_next new_node;new_node-_prev prev;new_node-_next pos._node;pos._node-_prev new_node;return iterator(new_node);}//erase过后pos迭代器失效返回原pos迭代器的下一个迭代器iterator erase(iterator pos){//不能删除_headassert(empty()false);node* prev pos._node-_prev;node* next pos._node-_next;delete pos._node;prev-_next next;next-_prev prev;pos iterator(next);return pos;}size与empty与swap size_t size()const{size_t count 0;const_iterator cit begin();while (cit ! end())count;return count;}bool empty()const{return (begin() end());}void swap(listTl1){std::swap(_head,l1._head);}
pop_back() void pop_back(){assert(empty()false);erase(--end());}总代码:
节点类 namespace MySpace{//节点template class Tstruct list_node{T _date;list_nodeT* _prev;list_nodeT* _next;list_node(const T val T()):_date(val), _prev(nullptr), _next(nullptr) {}};}正向迭代器类
namespace MySpace
{
//利用一个类来封装list_nodeT*//让这个类作为listT的迭代器,然后重载这个类的、--、*就可以实现迭代器的通用迭代办法templateclass T, class Ref, class Ptrstruct _list_iterator//正向迭代器底层封装了list_nodeT*{_list_iterator(list_nodeT* node nullptr):_node(node) {}typedef _list_iteratorT, Ref, Ptr self;self operator(){_node _node-_next;return *this;}self operator--(){_node _node-_prev;return *this;}self operator--(int){self tmp *this;--* this;return tmp;}self operator(int){self tmp *this;* this;return tmp;}bool operator!(const self it){return _node ! it._node;}bool operator(const self it){return !(*this!it);}Ref operator*(){return _node-_date;}Ptr operator-(){return _node-_date;}//成员list_nodeT* _node;};
}反向迭代器类
namespace MySpace
{
//反向迭代器templateclass Forward_iterators, class Ref, class Ptrstruct _list_reverse_iterator{_list_reverse_iterator(const Forward_iterators it Forward_iterators()):_it(it) {}typedef _list_reverse_iteratorForward_iterators, Ref, Ptr Reself;//反向迭代器类型名字太长了换个简短点的Reself operator()//前置{//正向迭代器的----_it;return *this;}Reself operator(int)//后置{Reself tmp(_it);--_it;return tmp;}Reself operator--()//前置{//正向迭代器的--_it;return *this;}Reself operator--(int)//后置{Reself tmp(_it);_it;return tmp;}Ref operator*(){return *_it;}Ptr operator-(){return _it.operator-();}bool operator!(const Reselfrit){return _it ! rit._it;}bool operator(const Reself rit){return _itrit;}//成员是一个正向迭代器;Forward_iterators _it;};
}list类
namespace MySpace
{
//带头双向循环链表templateclass Tclass list{public:typedef _list_iteratorT, T, T* iterator; //这是个普通对象的正向迭代器typedef _list_iteratorT, const T, const T* const_iterator;//const对象的正向迭代器typedef _list_reverse_iteratoriterator, T, T* reverse_iterator;//普通对象反向迭代器typedef _list_reverse_iteratorconst_iterator, const T, const T* const_reverse_iterator;//const对象反向迭代器typedef list_nodeT node;//节点list(){empty_init();}list(int n, const T val T()){empty_init();for (int i 0; i n; i){push_back(val);}}list(const listT l){empty_init();listT tmp(l.begin(),l.end());swap(tmp);}template class InputIteratorlist(InputIterator first, InputIterator last){empty_init();while (first ! last){push_back(*first);first;}}~list(){clear();delete _head;_head nullptr;}listT operator(listT l){if (this ! l){swap(l);}return *this;}void push_back(const T val){node* tail _head-_prev;node* new_node new node(val);new_node-_prev tail;tail-_next new_node;new_node-_next _head;_head-_prev new_node;}void pop_back(){assert(empty()false);erase(--end());}iterator begin(){return iterator(_head-_next);}iterator end(){return iterator(_head);}const_iterator begin()const{return const_iterator(_head-_next);}const_iterator end()const{return const_iterator(_head);}reverse_iterator rbegin(){return reverse_iterator(_head-_prev);}reverse_iterator rend(){return reverse_iterator(_head);}const_reverse_iterator rbegin()const{return const_reverse_iterator(_head-_prev);}const_reverse_iterator rend()const{return const_reverse_iterator(_head);}T front(){assert(empty() false);return _head-_next-_date;}const T front()const{assert(empty() false);return _head-_next-_date;}T back(){assert(empty() false);return _head-_prev-_date;}const T back()const{assert(empty() false);return _head-_prev-_date;}iterator insert(iterator pos, const T val){node* prev pos._node-_prev;node* new_node new node(val);prev-_next new_node;new_node-_prev prev;new_node-_next pos._node;pos._node-_prev new_node;return iterator(new_node);}iterator erase(iterator pos){//不能删除_headassert(empty()false);node* prev pos._node-_prev;node* next pos._node-_next;delete pos._node;prev-_next next;next-_prev prev;pos iterator(next);return pos;}size_t size()const{size_t count 0;const_iterator cit begin();while (cit ! end())count;return count;}bool empty()const{return (begin() end());}void swap(listTl1){std::swap(_head,l1._head);}void clear(){iterator it begin();while (it ! end()){iterase(it);}_head-_next _head-_prev _head;}private:list_nodeT* _head;void empty_init(){_head new node;_head-_next _head-_prev _head;}};
}
