前言
list的底层是带头双向循环链表,在数据结构专栏我们使用C语言简单模拟实现过,这里使用C++模拟实现也是大同小异的。
建议:阅读本文如有困难的,可以点击下面链接,复习带头双向循环链表:
C语言实现带头双向循环链表
list_5">一、list的基本框架
list_6">1. 将list封装
使用命名空间将我们模拟实现的list封装,避免命名冲突!
2. 链表结点
//将其封装在wjs命名空间中,与STL中的list区别开
namespace wjs
{//链表节点//因为后期需要频繁访问节点的成员,所以使用struct定义template<class T>struct list_node{//注意:类模板中类名不是类型,需要显式实例化list_node<T>* _next;list_node<T>* _prev;T _val;//结点的默认构造函数——初始化新结点list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}};
}
list_36">3. list类模板的基本框架
//将其封装在wjs命名空间中,与STL中的list区别开
namespace wjs
{//带头双向循环链表template<class T>class list{//因为类模板的类名不是类型,需要实例化,但是我们写的时候容易忘记,所以模板喜欢typedeftypedef list_node<T> Node;public://list的默认构造函数——初始化链表list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}//list的尾插void push_back(const T& x){//逻辑草图:tail《——》newnode《——》_head//①找尾Node* tail = _head->_prev;//②创建新节点Node* newnode = new Node(x);//③链接tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}private://指向哨兵位结点的指针Node* _head;};
}
list_80">4. list的迭代器(重点)
(1)普通迭代器
- 前面我们学习的string和vector的底层是数组,空间是连续,所以迭代器可以是原生指针。
- list的迭代器也和vector一样吗,是原生指针Node*吗,答案当然是不可以的,因为:
- Node*解引用得到的是结点,而迭代器解引用得到的是该位置的数据
- Node*++不能移动到下一位置,而迭代器++移动到下一位置
- 所以list的迭代器是一种自定义类型,通过自定义类型封装,然后通过运算符重载改变它的行为(即让它满足我们迭代器的需求)
- list的迭代器本质上是结点指针的自定义类型,通过封装,运算符重载使之解引用得到数据,++移动到下一个位置等
- 因为结点是list创建和释放的,不属于迭代器,迭代器不用去管它的创建和释放,所以迭代器的拷贝构造、析构函数使用默认生成的即可,不需要自己实现
//将其封装在wjs命名空间中,与STL中的list区别开
namespace wjs
{//list的迭代器——其实是一个结点的自定义类型//我们可以通过运算符重载(改变它原先的行为),使之满足我们的需求template<class T>struct __list_iterator{typedef list_node<T> Node;Node* _node;//构造函数——通过一个结点的指针即可初始化一个迭代器__list_iterator(Node* node):_node(node){}//重载运算符解引用——iterator解引用得到结点的数据T& operator*(){return _node->_val;}//重载运算符++——iterator++得到下一结点的位置//①前置++__list_iterator<T>& operator++(){_node = _node->_next;return *this;}//②后置++——为了区分后置+我们使用int占位__list_iterator<T>& operator++(int){__list_iterator<T> tmp(*this);_node = _node->_next;return tmp;}//重载运算符!=——迭代器不相等返回真//注意:end是传值返回,所以迭代器具有常性,所以形参需要const修饰bool operator!=(const __list_iterator<T>& it){return _node != it._node;}//重载运算符==——迭代器相等返回真bool operator==(const __list_iterator<T>& it){return _node == it._node;}};//带头双向循环链表template<class T>class list{//因为类模板的类名不是类型,需要实例化,但是我们写的时候容易忘记,所以模板喜欢typedeftypedef list_node<T> Node;public://重命名list的迭代器——虽然底层实现是不一样的,但是迭代器的用法是一样的!typedef __list_iterator<T> iterator;iterator begin(){//单参数的构造函数支持隐式类型的转换//所以直接传结点的指针就可以转换为迭代器return _head->_next;//return iterator(_head->_next);}iterator end(){//单参数的构造函数支持隐式类型的转换//所以直接传结点的指针就可以转换为迭代器return _head;//return iterator(_head);}private://指向哨兵位结点的指针Node* _head;};
}
(2)const迭代器
- 普通迭代器和const迭代器的区别:
- 普通对象调用普通迭代器,迭代器可读可写
- const对象调用const迭代器,迭代器只可读不可写
- 如下图代码,我们可以这样设计const迭代器吗?
答案自然是不可以的,这样设计的迭代器本身不可以修改!- const迭代器是指向的内容不可修改,但是迭代器本身是可以修改的。
- 即const迭代器和普通迭代器唯一的区别是它解引用返回的是const对象,其它的都与普通迭代器一样。
- 那我们粘贴一份普通迭代器代码,将解引用模块修改为const迭代器的,再将其重命名为const_iterator是不是就可以了?
答案:虽然这样可以满足我们const迭代器的需求,但是这样设计的太冗余了,STL库中并没有这样设计。- STL库中是通过模板来解决的,普通迭代器和const迭代器只有operator*的返回类型不一样,那我们可以通过增加一个模板参数来控制即可。
- 模板增加了一个模板参数,那在使用了类模板类型都需要更改,我们可以将其typedef一改全改,这样后续类模板的参数发生变换我们也只需要更改typedef即可。
namespace wjs
{//list迭代器template<class T, class Ref>struct __list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref> self;Node* _node;__list_iterator(Node* node):_node(node){}//重载运算符解引用——iterator解引用得到结点的数据返回普通迭代器——可读可写//T& operator*()//{// return _node->_val;//}返回const迭代器——只可读不可写//const T& operator*()//{// return _node->_val;//}//普通迭代器和const迭代器只有返回类型不一样,我们将其设计成模板参数,通过传参来控制其类型即可!Ref operator*(){return _node->_val;}//重载运算符++——iterator++得到下一结点的位置//①前置++self& operator++(){_node = _node->_next;return *this;}//②后置++——为了区分后置+我们使用int占位self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}//重载运算符!=——迭代器不相等返回真//注意:end是传值返回,所以迭代器具有常性,所以形参需要const修饰bool operator!=(const self& it)const{return _node != it._node;}//重载运算符==——迭代器相等返回真bool operator==(const self& it)const{return _node == it._node;}};//带头双向循环链表template<class T>class list{//因为类模板的类名不是类型,需要实例化,但是我们写的时候容易忘记,所以模板喜欢typedeftypedef list_node<T> Node;public://重命名list的迭代器——虽然底层实现是不一样的,但是迭代器的用法是一样的!//普通迭代器typedef __list_iterator<T, T&> iterator;//const迭代器typedef __list_iterator<T, const T&> const_iterator;iterator begin(){//单参数的构造函数支持隐式类型的转换//所以直接传结点的指针就可以转换为迭代器return _head->_next;//return iterator(_head->_next);}iterator end(){//单参数的构造函数支持隐式类型的转换//所以直接传结点的指针就可以转换为迭代器return _head;//return iterator(_head);}const_iterator begin()const{return _head->_next;}const_iterator end()const{return _head;}};
}
- 迭代器其本质是模拟的指针的行为,所有的容器都期望提供一种像指针去访问容器的方式。
- 容器将迭代器进行了封装,在上层我们都使用begin、end等来获取迭代器。
- 迭代器类似指针,指针可以通过箭头运算符访问自定类类型的成员变量,那迭代器自然也可以,list的迭代器是结点的自定类类型,所以list的箭头运算符需要我们自己重载运算符!
- 对于point->mem表达式,point必须是指向类对象的指针或者是一个重载了operator->的类对象。
- 根据point类型的不一样,point分别等价于:
- point是指针,则我们应用内置的箭头运算符,表达式等价于(*point).mem。首先解引用该指针,然后从所得对象中获取指定的成员。
- point是定义了operator->的类的一个对象,则使用point.operator->()的结果来获取mem。其中,如果该结果是指针,则执行则应用内置的箭头运算符(因为运算符重载要求可读性,所以编译器特殊处理,省略了一个->);如果该结果本身含有重载的operator->(),则重复调用当前步骤。
- 重载的箭头运算符的返回类型:
- 返回类的指针
- 自定义箭头运算符的类的对象
- 所有调用operator->()语法上应该连续写两个箭头运算符,第一个调用operator->()得到一个类的指针,第二个调用内置的箭头运算符访问类的成员,但是为了可读性,所以编译器做了特殊处理,省略一个->。
- list迭代器重载的箭头运算符,重载后指向结点的内容的地址。
- list迭代器重载的箭头运算符,普通迭代器返回T*,const迭代器返回const T*,所以和operator*一样,这里我们也将其设计成模板参数
- 学到这里我们就可以明白为什么库中迭代器的类模板设计了3个模板参数:
- 第一个模板参数T:迭代器的类型是不一样的
- 第二个模板参数Ref:迭代器解引用的返回类型不一样
- 第三个模板参数Ptr:迭代器重载的箭头运算符的返回类型不一样
namespace wjs
{//list的迭代器——其实是一个结点的自定义类型//我们可以通过运算符重载(改变它原先的行为),使之满足我们的需求template<class T, class Ref, class Ptr>struct __list_iterator{typedef list_node<T> Node;//模板类在使用时需要显式实例化,现在我们给类模板增加了一个模板参数,那所有使用类模板的地方都需要更改//所以我们使用typedef重命名,这样后续类模板的参数发生改变我们也只需要更改typedef即可typedef __list_iterator<T, Ref, Ptr> self;Node* _node;//构造函数——通过一个结点的指针即可初始化一个迭代器__list_iterator(Node* node):_node(node){}//普通迭代器和const迭代器只有返回类型不一样,我们将其设计成模板参数,通过传参来控制其类型即可!Ref operator*(){return _node->_val;}//重载运算符->——返回指向结点内容的指针(即类的地址)//普通迭代器返回T*,const迭代器返回const T*,所以和operator*一样,这里我们也将其设计成模板参数Ptr operator->(){return &_node->_val;}//重载运算符++——iterator++得到下一结点的位置//①前置++self& operator++(){_node = _node->_next;return *this;}//②后置++——为了区分后置+我们使用int占位self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}//重载运算符!=——迭代器不相等返回真//注意:end是传值返回,所以迭代器具有常性,所以形参需要const修饰bool operator!=(const self& it)const{return _node != it._node;}//重载运算符==——迭代器相等返回真bool operator==(const self& it)const{return _node == it._node;}};//带头双向循环链表template<class T>class list{//因为类模板的类名不是类型,需要实例化,但是我们写的时候容易忘记,所以模板喜欢typedeftypedef list_node<T> Node;public://重命名list的迭代器——虽然底层实现是不一样的,但是迭代器的用法是一样的!//普通迭代器typedef __list_iterator<T, T&, T*> iterator;//const迭代器typedef __list_iterator<T, const T&, const T*> const_iterator;iterator begin(){//单参数的构造函数支持隐式类型的转换//所以直接传结点的指针就可以转换为迭代器return _head->_next;//return iterator(_head->_next);}iterator end(){//单参数的构造函数支持隐式类型的转换//所以直接传结点的指针就可以转换为迭代器return _head;//return iterator(_head);}const_iterator begin()const{return _head->_next;}const_iterator end()const{return _head;}};
}
list_399">5. list的插入删除
(1)insert&push_back&push_front
- insert:在pos迭代器之前插入一个新节点
- list的空间不连续是按需申请,insert之后不会导致迭代器失效问题
- 我们只需要实现insert后,头插和尾插复用insert即可
//insert:在pos位置之前插入
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 newnode;
}//list的尾插:复用insert
void push_back(const T& x)
{insert(end(), x);
}
//list的头插:复用insert
void push_front(const T& x)
{insert(begin(), x);
}
(2)erase&pop_back&pop_front
- erase:删除pos迭代器指向的结点,注意哨兵位不能删
- erase之后迭代器失效,我们通过返回下一个位置的迭代器解决失效问题
- 尾删和头删复用erase即可
//erase:删除pos位置结点
iterator erase(iterator pos)
{//哨兵位不能删assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;//链接:prev《——》nextprev->_next = next;next->_prev = prev;//删除curdelete cur;//删除之后迭代器失效,返回下一个位置的迭代器return next;
}//list的尾删:复用erase
void pop_back()
{erase(--end());
}
//list的头删:复用erase
void pop_front()
{erase(begin());
}
(3)clear
- clear:将所有有效结点释放,但保留哨兵位
//list的清理:将所有有效结点释放,但保留哨兵位(因为链表的空间不是连续的,按需申请,所以不要了可以将其释放)
void clear()
{iterator it = begin();while (it != end()){//erase之后迭代器失效,我们通过接收它的返回值解决它的失效问题it = erase(it);}
}
(4)size
//list的大小:有效节点的个数
size_t size()
{//方式1:通过遍历链表得到有效结点个数size_t sz = 0;iterator it = begin();while (it != end()){++it;++sz;}return sz;//方式2:可以增加一个成员变量_size用于存储有效结点个数,返回_size即可。
}
list_503">6. list的拷贝构造&析构
(1)析构函数
- list设计动态资源申请,所以需要显示实现析构函数
- delete释放完空间之后与free一样,不会改变指向动态空间的指针变量,有危险,建议释放完之后将其置为空
//析构函数:释放整个list,包括哨兵位
~list()
{//复用clear:释放所有的有效节点clear();//释放哨兵位delete _head;//释放之后_head为野指针,将其置为空_head = nullptr;
}
(2)拷贝构造函数
- list涉及动态资源申请,需要深拷贝,所以需要我们显示实现拷贝构造
- 拷贝构造的深拷贝有如下两种实现方式:
- 传统写法:自己开空间,自己拷贝
- 现代写法:把工作交给别人,别人完成了再获取(即直接拿别人的结果)
- 我们发现构造函数和拷贝构造有一些代码重复(成员变量初始化),我们可以将其提炼出来将其封装为一个单独模块,库里面也是这样做的。
- operator=也是一样的,当涉及深拷贝时,需要我们显示实现。
- 现代写法和传统写法并没有效率上的差别,只不过是复用代码,让代码简洁了。
//成员变量的初始化
void empty_init()
{_head = new Node;_head->_next = _head;_head->_prev = _head;
}//拷贝构造函数
//传统写法:自己开空间,自己拷贝
list(const list<T>& lt)
{//自己开空间empty_init();//自己拷贝for (auto& e : lt){push_back(e);}
}//重载赋值运算符
list<T>& operator=(list<T> lt)
{//我们已经直接叫形参帮我们开好空间,并且做了拷贝//所以这里我们直接交换形参,拿到结果即可swap(lt);return *this;
}//交换两个链表
void swap(list<T> lt)
{std::swap(_head, lt._head);
}
list的接口我们模拟这些常用的即可,模拟只是让我们更加深入的去了解list,并不是去造一个更好的轮子!
完整代码参考:
#pragma once#include<assert.h>//将其封装在wjs命名空间中,与STL中的list区别开
namespace wjs
{//链表节点//因为后期需要频繁访问节点的成员,所以使用struct定义template<class T>struct list_node{//注意:类模板中类名不是类型,需要显式实例化list_node<T>* _next;list_node<T>* _prev;T _val;//结点的默认构造函数——初始化新结点list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}};//list的迭代器——其实是一个结点的自定义类型//我们可以通过运算符重载(改变它原先的行为),使之满足我们的需求//普通迭代器//typedef __list_iterator<T, T&> iterator;//const迭代器//typedef __list_iterator<T, const T&> const_iterator;template<class T, class Ref, class Ptr>struct __list_iterator{typedef list_node<T> Node;//模板类在使用时需要显式实例化,现在我们给类模板增加了一个模板参数,那所有使用类模板的地方都需要更改//所以我们使用typedef重命名,这样后续类模板的参数发生改变我们也只需要更改typedef即可typedef __list_iterator<T, Ref, Ptr> self;Node* _node;//构造函数——通过一个结点的指针即可初始化一个迭代器__list_iterator(Node* node):_node(node){}//重载运算符解引用——iterator解引用得到结点的数据返回普通迭代器——可读可写//T& operator*()//{// return _node->_val;//}返回const迭代器——只可读不可写//const T& operator*()//{// return _node->_val;//}//普通迭代器和const迭代器只有返回类型不一样,我们将其设计成模板参数,通过传参来控制其类型即可!Ref operator*(){return _node->_val;}//重载运算符->——返回指向结点内容的指针(即类的地址)//普通迭代器返回T*,const迭代器返回const T*,所以和operator*一样,这里我们也将其设计成模板参数Ptr operator->(){return &_node->_val;}//重载运算符++——iterator++得到下一结点的位置//①前置++self& operator++(){_node = _node->_next;return *this;}//②后置++——为了区分后置+我们使用int占位self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}//重载运算符--——iterator--得到前一结点的位置//①前置--self& operator--(){_node = _node->_prev;return *this;}//②后置--——为了区分后置-我们使用int占位self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}//重载运算符!=——迭代器不相等返回真//注意:end是传值返回,所以迭代器具有常性,所以形参需要const修饰bool operator!=(const self& it)const{return _node != it._node;}//重载运算符==——迭代器相等返回真bool operator==(const self& it)const{return _node == it._node;}};//带头双向循环链表template<class T>class list{//因为类模板的类名不是类型,需要实例化,但是我们写的时候容易忘记,所以模板喜欢typedeftypedef list_node<T> Node;public://重命名list的迭代器——虽然底层实现是不一样的,但是迭代器的用法是一样的!//普通迭代器typedef __list_iterator<T, T&, T*> iterator;//const迭代器typedef __list_iterator<T, const T&, const T*> const_iterator;iterator begin(){//单参数的构造函数支持隐式类型的转换//所以直接传结点的指针就可以转换为迭代器return _head->_next;//return iterator(_head->_next);}iterator end(){//单参数的构造函数支持隐式类型的转换//所以直接传结点的指针就可以转换为迭代器return _head;//return iterator(_head);}const_iterator begin()const{return _head->_next;}const_iterator end()const{return _head;}//如下:我们可以这样设计迭代器吗?//不可以,这样设计是迭代器本身不可修改,//而const迭代器是期望指向的内容不可修改,本身是可以修改的!//typedef const __list_iterator<T> const_iterator;//list的默认构造函数——初始化链表list(){empty_init();}//insert:在pos位置之前插入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 newnode;}//erase:删除pos位置结点iterator erase(iterator pos){//哨兵位不能删assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;//链接:prev《——》nextprev->_next = next;next->_prev = prev;//删除curdelete cur;//删除之后迭代器失效,返回下一个位置的迭代器return next;}//list的尾插//void push_back(const T& x)//{// //逻辑草图:tail《——》newnode《——》_head// //①找尾// Node* tail = _head->_prev;// //②创建新节点// Node* newnode = new Node(x);// //③链接// tail->_next = newnode;// newnode->_prev = tail;// newnode->_next = _head;// _head->_prev = newnode;//}//list的尾插:复用insertvoid push_back(const T& x){insert(end(), x);}//list的头插:复用insertvoid push_front(const T& x){insert(begin(), x);}//list的尾删:复用erasevoid pop_back(){erase(--end());}//list的头删:复用erasevoid pop_front(){erase(begin());}//list的大小:有效节点的个数size_t size(){//方式1:通过遍历链表得到有效结点个数size_t sz = 0;iterator it = begin();while (it != end()){++it;++sz;}return sz;//方式2:可以增加一个成员变量_size用于存储有效结点个数,返回_size即可。}//list的清理:将所有有效结点释放,但保留哨兵位(因为链表的空间不是连续的,按需申请,所以不要了可以将其释放)void clear(){iterator it = begin();while (it != end()){//erase之后迭代器失效,我们通过接收它的返回值解决它的失效问题it = erase(it);}}//析构函数:释放整个list,包括哨兵位~list(){//复用clear:释放所有的有效节点clear();//释放哨兵位delete _head;//释放之后_head为野指针,将其置为空_head = nullptr;}//成员变量的初始化void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;}//拷贝构造函数//传统写法:自己开空间,自己拷贝list(const list<T>& lt){//自己开空间empty_init();//自己拷贝for (auto& e : lt){push_back(e);}}//重载赋值运算符list<T>& operator=(list<T> lt){//我们已经直接叫形参帮我们开好空间,并且做了拷贝//所以这里我们直接交换形参,拿到结果即可swap(lt);return *this;}//交换两个链表void swap(list<T> lt){std::swap(_head, lt._head);}private://指向哨兵位结点的指针Node* _head;};
}