C++ list的模拟实现
一.前置说明
对于list而言,最难的点是它如何进行设计与封装的
尤其是list的迭代器
而不是链表的基础操作
只要实现好迭代器之后,list就非常好实现了
1.前言
首先我们要说明的是:
1.list就是数据结构当中的带头双向循环链表
2.list的迭代器不是简简单单的原生指针,而是在原生指针的基础上进行了一层封装
3.关于链表的操作我们就不再赘述了,因为带头双向循环链表的知识并不难,而且大家应该都是掌握了的
2.list是如何封装的?
1.STL库中的实现
下面我们依次看一下成员变量,构造函数和迭代器
1.成员变量
2.构造函数
3.迭代器
因此我们要实现的这三个类的介绍如下:
2.节点类
template<classT>structlist_node{
T _data;
list_node<T>* _next;
list_node<T>* _prev;list_node(const T& x =T()):_data(x),_next(nullptr),_prev(nullptr){}};
3.迭代器类
template<classT,classRef,classPtr>struct__list_iterator{typedef __listIterator<T, Ref, Ptr> Self;typedef __listIterator<T, T&, T*> iterator;typedef ListNode<T> Node;
Node* _node;__listIterator(Node* node):_node(node){}__listIterator(const iterator& it):_node(it._node){}
self&operator++();
self&operator--();
self operator++(int);
Ref operator*();
Ptr operator->();//注意:一定是判断节点指针是否相等,不是迭代器是否相等!!!!booloperator!=(const self& s);booloperator==(const self& s);};
这里把节点类和迭代器类都用struct来定义
是因为这两个类我们一般都是开放使用的
而struct的默认访问限定符是public 外部可以访问
4.list类
template<classT>classlist{typedef list_node<T> Node;public:typedef __list_iterator<T> iterator;typedef __list_iterator<T,const T&,const T*> const_iterator;
iterator begin();
iterator end();
const_iterator begin()const;
const_iterator end()const;list(){empty_init();}voidempty_init(){
_head =new Node;
_head->_next = _head;
_head->_prev = _head;
_size =0;}//其他一堆成员函数private:
Node* _head;
size_t _size;//记录数据个数};
3.const迭代器的说明
我们先基于非const迭代器实现完整个list之后
最后在加上const迭代器的版本形成最终的大致框架
4.最终的大致框架:
namespace wzs
{template<classT>structlist_node{
T _data;
list_node<T>* _next;
list_node<T>* _prev;list_node(const T& x =T());};template<classT,classRef,classPtr>struct__list_iterator{typedef __listIterator<T, Ref, Ptr> Self;typedef __listIterator<T, T&, T*> iterator;typedef ListNode<T> Node;
Node* _node;__listIterator(Node* node):_node(node){}__listIterator(const iterator& it):_node(it._node){}
self&operator++();
self&operator--();
self operator++(int);
self operator--(int);
Ref operator*();
Ptr operator->();//注意:一定是判断节点指针是否相等,不是迭代器是否相等!!!!booloperator!=(const self& s);booloperator==(const self& s);};template<classT>classlist{typedef list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T,const T&,const T*> const_iterator;
iterator begin();
iterator end();
const_iterator begin()const;
const_iterator end()const;voidempty_init();list();list(const list<T>& lt);voidswap(list<T>& lt);//现代写法
list<int>&operator=(list<int> lt);~list();//复用erasevoidclear();//复用insertvoidpush_back(const T& x);voidpush_front(const T& x);voidpop_front();voidpop_back();//list的insert没有迭代器失效的问题
iterator insert(iterator pos,const T& x);//list的erase有迭代器失效的问题
iterator erase(iterator pos);
size_t size()const;boolempty()const;private:
Node* _head;
size_t _size;};}
5.初步版本(不包含const迭代器的版本)
namespace wzs
{template<classT>structlist_node{
T _data;
list_node<T>* _next;
list_node<T>* _prev;list_node(const T& x =T());};template<classT>struct__list_iterator{typedef list_node<T> Node;typedef __list_iterator<T> self;
Node* _node;__list_iterator(Node* node);
self&operator++();
self&operator--();
self operator++(int);
self operator--(int);
Ref operator*();
Ptr operator->();//注意:一定是判断节点指针是否相等,不是迭代器是否相等!!!!booloperator!=(const self& s);booloperator==(const self& s);};template<classT>classlist{typedef list_node<T> Node;public:typedef __list_iterator<T> iterator;
iterator begin();
iterator end();voidempty_init();list();list(list<T>& lt);voidswap(list<T>& lt);//现代写法
list<int>&operator=(list<int> lt);~list();//复用erasevoidclear();//复用insertvoidpush_back(const T& x);voidpush_front(const T& x);voidpop_front();voidpop_back();//list的insert没有迭代器失效的问题
iterator insert(iterator pos,const T& x);//list的erase有迭代器失效的问题
iterator erase(iterator pos);
size_t size()const;boolempty()const;private:
Node* _head;
size_t _size;};}
二.迭代器类的实现
1.iterator的成员变量和构造函数
typedef list_node<T> Node;typedef __list_iterator<T> self;
Node* _node;__list_iterator(Node* node):_node(node){}
注意这两个typedef
一个是把
list_node<T>
给命名为Node
一个是把迭代器自身
__list_iterator<T>
命名为self
增强代码的可读性
这里的构造函数的作用就是能够通过节点指针直接转换为迭代器
2.前置后置++ –
迭代器++就是指向下一个元素
迭代器–就是指向前一个元素
在链表这里
假设有这么一个节点:
Node* cur
指向下一个元素就是
cur=cur->_next
指向前一个元素就是
cur=cur->_prev
因此我们可以写出这样的代码
self就是这个迭代器本身的类型
//前置++
self&operator++(){
_node = _node->_next;return*this;}//前置--
self&operator--(){
_node = _node->_prev;return*this;}//后置++
self operator++(int){//拷贝构造一个tmp
self tmp(*this);
_node = _node->_next;return tmp;}//后置--
self operator--(int){//拷贝构造一个tmp
self tmp(*this);
_node = _node->_prev;return tmp;}
3.解引用* ->
迭代器解引用就是取出迭代器指向的数据
因此对于链表而言
假设有这么一个节点:
Node* cur
就是 cur->data,类型为T&
->就是&cur->data,类型为T
因此我们写出这样的代码
T&operator*(){return _node->_data;}
T*operator->(){return&_node->_data;}
4.== !=
注意:我们一定是判断节点指针是否相等,而不是判断迭代器是否相等!
booloperator!=(const self& s){return _node != s._node;}booloperator==(const self& s){return _node == s._node;}
list的iterator体现了一个非常重要面向对象的设计思想:
封装:屏蔽了底层差异和实现细节,提供了统一的访问修改遍历方式
也正是因为这层封装,list的迭代器在使用的时候才能够让我们无需关心底层的具体实现细节而能够快速上手和使用
list的非const迭代器就是这些内容
三.list类的实现
1.构造函数
typedef list_node<T> Node;voidempty_init(){
_head =new Node;
_head->_next = _head;
_head->_prev = _head;
_size =0;}list(){empty_init();}
头节点一开始就是要存在的
头节点的前驱是自己,后继也是自己
2.begin end
begin是指向第一个有效数据的迭代器
end是指向最后一个有效数据的下一个位置的迭代器
又因为list是带头双向循环链表,头节点_head是不存储有效数据的
因此第一个有效数据的节点是_head->_next
最后一个有效数据的节点是_head->_prev
最后一个有效数据的下一个节点就是_head
typedef __list_iterator<T> iterator;
iterator begin(){returniterator(_head->_next);}
iterator end(){returniterator(_head);}
list类中把
__list_iterator<T>
typedef成了iterator
这里调用了iterator这个类的构造函数
3.insert
list的insert没有迭代器失效的问题
因为list没有扩容这一概念,节点都是一个一个按需申请的
//在pos位置前面插入x
iterator insert(iterator pos,const T& x){//new一个新节点
Node* newnode =newNode(x);//利用迭代器取出其中的节点
Node* cur = pos._node;//记录当前节点的前驱
Node* prev = cur->_prev;//插入新节点
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
prev->_next = newnode;//有效数据个数+1++_size;//返回新节点的迭代器returniterator(newnode);}
到此我们就可以插入数据并且遍历访问修改数据了
4.erase
//list的erase有迭代器失效的问题//因此要返回被删除位置的下一个位置的迭代器
iterator erase(iterator pos){//利用迭代器取出当前节点
Node* cur = pos._node;//找到当前节点的前驱和后继
Node* prev = cur->_prev;
Node* next = cur->_next;//在链表中删除当前节点
prev->_next = next;
next->_prev = prev;//释放当前节点delete cur;
cur =nullptr;//有效数据个数-1--_size;//返回被删除位置的下一个位置的迭代器//也就是后继指针的迭代器returniterator(next);}
5.头插头删,尾插尾删的复用
voidpush_back(const T& x){insert(end(), x);}voidpush_front(const T& x){insert(begin(), x);}voidpop_front(){erase(begin());}voidpop_back(){erase(--end());}
6.clear和析构函数
1.clear
clear:清空所有有效数据,恢复到原始状态(无参构造后的状态)
超级传统的版本
voidclear(){if(!empty()){//释放所有有效数据的节点
Node* cur = _head->_next;while(cur != _head){
Node* next = cur->_next;delete cur;
cur = next;}//恢复成原始状态
_head->_next = _head;
_head->_prev = _head;
_size =0;}}
复用erase的版本
voidclear(){
iterator it =begin();while(it !=end()){
it =erase(it);}}
2.析构函数
有了clear之后,析构函数就能复用clear了
~list(){clear();delete _head;
_head =nullptr;}
注意:我们new节点的时候是直接new的
不是这样new []的
因此delete的时候要直接delete
而不要这样delete[]
否则会出现错误的,而且不容易看出来
7.swap和其他小函数
1.swap
因为list的成员变量只有Node*和size,而且他们都是内置类型(指针类型和int类型)
因此交换这两个成员变量即可
voidswap(list<T>& lt){
std::swap(_head, lt._head);
std::swap(_size, lt._size);}
2.empty
boolempty()const{return _head->_next == _head;}
只有头节点自己的时候就是空链表
3.size
记录链表当中有效数据的个数
size_t size()const{return _size;}
8.拷贝构造函数
对于拷贝构造函数
参数类型应该是
const list<T>& lt
的
但是因为我们还没有实现const迭代器,所以这里先用一下非const的引用作为参数
list(list<T>& lt){//先初始化listempty_init();//然后逐个取出lt中的数据尾插到list当中即可typenamelist<T>::iterator it = lt.begin();while(it != lt.end()){push_back(*it);++it;}}
9.赋值运算符重载
这里我们直接写现代写法了
list<int>&operator=(list<int> lt){swap(lt);return*this;}
四.const迭代器加入后的改动
想要加入const迭代器
首先想到的就是再写一个const_iterator类
首先我们要明白:const迭代器中const修饰的是迭代器指向的内容不能被修改
而通过迭代器修改数据的方式就是解引用
因此只需要修改一下解引用的地方即可
对于非const迭代器来说
返回的是T&
->返回的是T
因此对于const迭代器来说
返回的是const T&
->返回的是const T
同时不要忘了改一下名字
把iterator改为const_iterator
并且在list类当中实现const修饰后的begin和end
1.原版
其他的地方都跟非const迭代器一样
template<classT>struct__list_const_iterator{typedef list_node<T> Node;typedef __list_const_iterator<T> self;
Node* _node;__list_const_iterator(Node* node):_node(node){}//T& 改为了 const T&const T&operator*(){return _node->_data;}//修改的地方://T* 改为了 const T*const T*operator->(){return&_node->_data;}};
template<classT>classlist{typedef list_node<T> Node;public:typedef __list_iterator<T> iterator;//加上const_iteratortypedef __list_const_iterator<T> const_iterator;
iterator begin(){returniterator(_head->_next);}
iterator end(){returniterator(_head);}//实现const修饰后的begin和end
const_iterator begin()const{returnconst_iterator(_head->_next);}
const_iterator end()const{returnconst_iterator(_head);}
其他的成员函数,成员变量等等都不用修改....
不过这样的话代码就有些冗余了
有没有更好的方法呢?
设计STL的大佬就出了这么一个主意
2.精简版
既然你const迭代器和非const迭代器只有两个地方不同
那么我就直接把那两个地方也放到类模板当中
这样不就能把你们两个合并成一个类了吗?
Ref:reference:引用的英文
Ptr:pointer:指针的英文
template<classT,classRef,classPtr>struct__list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;typedef __listIterator<T, T&, T*> iterator;
Node* _node;__list_iterator(Node* node):_node(node){}//const_iterator和iterator的转化//支持用iterator构造const_iterator__listIterator(const iterator& it):_node(it._node){}//这里修改成了Ref
Ref operator*(){return _node->_data;}//这里修改成了Ptr
Ptr operator->(){return&_node->_data;}};
对于list类的修改
template<classT>classlist{typedef list_node<T> Node;public://把实例化的操作放在list类当中完成typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T,const T&,const T*> const_iterator;
iterator begin(){returniterator(_head->_next);}
iterator end(){returniterator(_head);}
const_iterator begin()const{returnconst_iterator(_head->_next);}
const_iterator end()const{returnconst_iterator(_head);}
其他的成员函数,成员变量等等都不用修改....};
此时const迭代器实现完毕了
拷贝构造就可以改回来了
list(const list<T>& lt){empty_init();
list<T>::const_iterator it = lt.begin();while(it != lt.end()){push_back(*it);++it;}}
五.完整代码
#pragmaonce#include<iostream>usingnamespace std;#include<string>#include<vector>namespace wzs
{template<classT>structlist_node{
T _data;
list_node<T>* _next;
list_node<T>* _prev;list_node(const T& x =T()):_data(x),_next(nullptr),_prev(nullptr){}};template<classT,classRef,classPtr>struct__list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;typedef __listIterator<T, T&, T*> iterator;
Node* _node;__list_iterator(Node* node):_node(node){}//const_iterator和iterator的转化//支持用iterator构造const_iterator__listIterator(const iterator& it):_node(it._node){}
self&operator++(){
_node = _node->_next;return*this;}
self&operator--(){
_node = _node->_prev;return*this;}
self operator++(int){
self tmp(*this);
_node = _node->_next;return tmp;}
self operator--(int){
self tmp(*this);
_node = _node->_prev;return tmp;}
Ref operator*(){return _node->_data;}
Ptr operator->(){return&_node->_data;}//注意:一定是判断节点指针是否相等,不是迭代器是否相等!!!!booloperator!=(const self& s){return _node != s._node;}booloperator==(const self& s){return _node == s._node;}};template<classT>classlist{typedef list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T,const T&,const T*> const_iterator;
iterator begin(){returniterator(_head->_next);}
iterator end(){returniterator(_head);}
const_iterator begin()const{returnconst_iterator(_head->_next);}
const_iterator end()const{returnconst_iterator(_head);}voidempty_init(){
_head =new Node;
_head->_next = _head;
_head->_prev = _head;
_size =0;}list(){empty_init();}//const迭代器搞完之后:修改为//list(const list<T>& lt);list(const list<T>& lt){empty_init();
list<T>::const_iterator it = lt.begin();while(it != lt.end()){push_back(*it);++it;}}voidswap(list<T>& lt){
std::swap(_head, lt._head);
std::swap(_size, lt._size);}//现代写法
list<int>&operator=(list<int> lt){swap(lt);return*this;}~list(){clear();delete _head;
_head =nullptr;}//超级传统版本//void clear()//{// if (!empty())// {// //释放所有有效数据的节点// Node* cur = _head->_next;// while (cur != _head)// {// Node* next = cur->_next;// delete cur;// cur = next;// }// //恢复成原始状态// _head->_next = _head;// _head->_prev = _head;// _size = 0;// }//}//复用erasevoidclear(){
iterator it =begin();while(it !=end()){
it =erase(it);}}//void push_back(const T& x)//{// Node* newnode = new Node(x);// Node* tail = _head->_prev;// tail->_next = newnode;// newnode->_prev = tail;// newnode->_next = _head;// _head->_prev = newnode;// _size++;//}//复用insertvoidpush_back(const T& x){insert(end(), x);}voidpush_front(const T& x){insert(begin(), x);}voidpop_front(){erase(begin());}voidpop_back(){erase(--end());}//list的insert没有迭代器失效的问题
iterator insert(iterator pos,const T& x){
Node* newnode =newNode(x);
Node* cur = pos._node;
Node* prev = cur->_prev;
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
prev->_next = newnode;++_size;//调用iterator的构造函数构造一个新的迭代器并返回returniterator(newnode);}//list的erase有迭代器失效的问题
iterator erase(iterator pos){
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;delete cur;
cur =nullptr;//调用iterator的构造函数构造一个新的迭代器并返回--_size;returniterator(next);}
size_t size()const{return _size;}boolempty()const{return _head->_next == _head;}private:
Node* _head;
size_t _size;};}
六.补充
1.一个"奇怪"的现象
template<classT>voidprint_list(const list<T>& lt){
list<T>::const_iterator it = lt.begin();while(it != lt.end()){
cout <<*it <<" ";++it;}}
这是一个打印list的内容的函数
不过运行的时候却会报错
2.小小优化一下
刚才那个只能打印list
如果我想让它也能打印vector,string等等类型呢?
在上面加一个模板即可
template<typenameContainer>voidprint_container(const Container& con){typenameContainer::const_iterator it = con.begin();while(it != con.end()){
cout <<*it <<" ";++it;}
cout << endl;}
因此我们就能知道
模板实现了泛型编程
而泛型编程的本质就是把本来应该由我们做的工作交给了编译器去做
以上就是C++ list模拟实现的全部内容,希望能对大家有所帮助!
本文转载自: https://blog.csdn.net/Wzs040810/article/details/134997760
版权归原作者 program-learner 所有， 如有侵权，请联系我们删除。
版权归原作者 program-learner 所有， 如有侵权，请联系我们删除。