list模拟实现【C++】

文章目录

全部的实现代码放在了文章末尾

准备工作

创建两个文件，一个头文件

mylist.hpp

，一个源文件

test.cpp

【因为模板的声明和定义

不能

分处于不同的文件中，所以把成员函数的声明和定义放在了同一个文件

mylist.hpp

中】

1. mylist.hpp：存放包含的头文件，命名空间的定义，成员函数和命名空间中的函数的定义
2. test.cpp：存放main函数，以及测试代码

---

包含头文件

1. iostream：用于输入输出
2. assert.h：用于使用报错函数assert

---

定义命名空间

在文件

mylist.hpp

中定义上一个命名空间

mylist

把list类和它的成员函数放进命名空间封装起来，防止与包含的头文件中的函数/变量重名的冲突问题

---

类的成员变量

参考了stl源码中的list的实现，stl中list的底层链表是

双向带头循环链表

【可以看我这篇文章了解

双向带头循环链表

的实现：链表的极致——带头双向循环链表】
成员变量只有一个，就是指向

双向带头循环链表

的头节点的指针。

节点类：

为什么节点类是用struct而不是class呢？

因为节点类里面的成员变量在实现list的时候需要经常访问，所以需要节点类的成员变量是公有的【使用友元也可以，但是比较麻烦】
struct的默认访问权限就是公有，不用加访问限定符了，stl中实现的节点类也是struct
class的默认访问权限是私有的

---

list类：

为什么要写get_head_node?

因为插入节点之前

必须

要有头节点
所以把创建初始头节点的操作写成了一个函数，用于
所有构造函数插入节点之前进行申请头节点

---

迭代器

因为list存储数据的方式是创建一个一个的节点存储数据
所以存储数据的空间

不是

连续的，所以

不能

直接用指针作为迭代器

因为指向一个节点的指针直接++,是

不一定能

指向下一个节点的

所以

要把迭代器实现成一个类

，这样才可以正确地支持++，- -，*等操作

迭代器在list类里的实例化和重命名

普通迭代器

template<classT,classR,classF>structIterator{
    把自己的类型重命名一下
    typedef Iterator<T, R, F> Self;

    成员变量的类型是 双向带头循环链表的节点类型
    listnode<T>* _n;Iterator(listnode<T>*l=nullptr) 构造函数
    {
        _n = l;}
    Self&operator++()前置++{++就是指向下一个节点
        _n = _n->_next;return*this;}
    Self operator++(int)  后置++{
        Self tmp =*this;  先记录一下++之前的值

        _n = _n->_next;  再++return tmp;}
    Self&operator--()  前置--{--就是指向上一个节点
        _n = _n->_prev;return*this;}
    Self operator--(int) 后置--{
        Self tmp =*this; 先记录一下--之前的值

        _n = _n->_prev;  再--return tmp;}

    R operator*()const{
         类比指针
        *就是获取  节点中存储的数据
        return _n->_data;}
    F operator->()const{
        返回  节点中 存储数据的成员变量的  地址
        return&(_n->_data);}booloperator!=(const Self&obj)const![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/f3d8c3b768b14a04a69d04a69c2d9829.png#pic_center){return _n != obj._n;}booloperator==(const Self& obj){return!(*this!= obj);}};

operator->()的作用是什么？

为了实现：
当节点中存储的数据是

自定义类型的变量

时，可以直接使用 迭代器->访问自定义类型中的成员
【原来访问需要调用两次->，

为了可读性，省略了一个->

】

例

---

const迭代器

const迭代器与普通迭代器的区别是什么？
区别就只有==

不能

通过const迭代器改变节点中存储的数据==

转换一下就是：

1. 不能使用迭代器的operator*()改变节点中存储的数据，即把operator*()的返回值改成const T&就可以了
2. 不能使用迭代器的operator->()改变节点中存储的数据的成员，即把operator->()的返回值改成const T*就可以了

所以const迭代器与普通迭代器的区别就只有两个函数的返回值类型不同，所以增加两个模板参数：R和F

普通迭代器

实例化时:

R就是T&

，

F就是T*

const迭代器

实例化：

R就是const T&

，

F就是const T*

---

反向迭代器

反向迭代器与普通迭代器的

实现上

的区别就是：

普通

迭代器++是指向

下一个

节点

反向

迭代器++是指向

上一个

节点

普通

迭代器- -是指向

上一个

节点

反向

迭代器- -是指向

下一个

节点

template<classT,classR,classF>structReverse_iterator{
    把自己的类型重命名一下
    typedef Reverse_iterator<T, R, F> Self;

    成员变量的类型是 双向带头循环链表的节点类型
    listnode<T>* _n;Reverse_iterator(listnode<T>* l) 构造函数
    {
        _n = l;}

    Self&operator++(){
        反向迭代器++，是移动到  前  一个节点
        _n = _n->_prev;return*this;}
    Self operator++(int){
        Self tmp =*this;
        _n = _n->_prev;return tmp;}
    Self&operator--(){
        反向迭代器--，是移动到  后  一个节点
        _n = _n->_next;return*this;}
    Self operator--(int){
        Self tmp =*this;
        _n = _n->_next;return tmp;}
    R operator*()const{return _n->_data;}
    F operator->()const{return&(_n->_data);}booloperator!=(const Self& obj)const{return _n!=obj._n;}booloperator==(const Self& obj)const{return!(*this!= obj);}};

---

迭代器的获取

iterator begin(){
    头节点的下一个节点 才是第一个节点
    return _head->_next;}const修饰的对象只能调用const修饰的成员函数
const_iterator begin()const{
    头节点的下一个节点 才是第一个节点
    return _head->_next;}

iterator end(){
    最后一个节点的下一个节点是  头节点
    因为是循环链表
    return _head;}const修饰的对象只能调用const修饰的成员函数
const_iterator end()const{return _head;}

reverse_iterator rend(){
    反向迭代器的rend返回的是第一个节点的   前一个节点
    return _head;}const修饰的对象只能调用const修饰的成员函数
const_reverse_iterator rend()const{return _head;}
reverse_iterator rbegin(){
    反向迭代器的rbegin()返回的是  最后一个节点
    最后一个节点是  头节点的前一个
    因为是循环链表
    return _head->_prev;}

const_reverse_iterator rbegin()const{return _head->_prev;}

---

构造函数

默认构造

---

使用n个val构造

---

迭代器区间构造

---

解决迭代器区间构造 和 用n个val构造的冲突

当重载了

迭代器区间构造

和

使用n个val构造

的时候
如果传入的

两个参数都是int类型

的话就会报错

为什么？
因为在模板函数构成重载时，编译器会调用更合适的那一个
什么叫更合适？
就是

不会

类型转

如果传入的

两个参数都是int类型

，那么调用的应该是

使用n个值构造

，因为没有int类型的迭代器

但是

使用n个值构造

的第一个参数是size_t , int传进去要隐式类型转换
而调用

迭代器区间构造

，两个int的实参传进去，就会直接把

InputIterator

推导成int，

不会

发生类型转换，所以编译器会调用

迭代器区间构造

解决方法：
再重载一个

使用n个值构造

的函数，把第一个参数改成int，这样根据

模板偏特化

，就会在都不类型转换时优先调用第一个参数特化成int的那个构造函数

---

initializer_list构造

写了这个构造函数，就可以支持直接使用{}初始化了
例

initializer_list

是iostream库里面的自定义类型，它可以

直接接收{ }里面的值 进行初始化

，而且有迭代器

所以可以直接使用迭代器循环+尾插进行对

list

的构造

---

拷贝构造

---

析构函数

---

swap

只需要交两个list对象的

头指针中存储的地址

就可以了

因为两个list对象都有头结点，交换了

头指针中存储的地址

，就相当于把这两个对象的头指针的指向交换了，
而链表的所有节点都是由头节点出发去找到的

voidswap(list& obj){
    调用库里面的swap，交换头指针
    std::swap(_head, obj._head);}

---

赋值运算符重载

list&operator=(list obj){swap(obj);return*this;}

为什么上面的两句代码就可以完成深拷贝呢？
这是因为：

使用了传值传参，会在传参之前调用拷贝构造，再把拷贝构造出的临时对象作为参数传递进去

赋值运算符的左操作数，*this再与传入的临时对象obj交换，就

直接完成了拷贝

在函数结束之后，存储在栈区的obj再函数结束之后，obj生命周期结束

obj调用析构函数，把指向的从*this那里交换来的不需要的空间销毁

---

erase

删除pos迭代器指向的节点

为什么要返回next？

因为使用了erase之后的迭代器会失效，需要提供更新的方法

为什么使用了erase之后的迭代器会失效？

因为pos指向的节点erase之后，节点被释放了

stl库里面规定erase的返回值是

指向删除数据的下一个数据的迭代器

，下一个数据就是next指向的数据，所以返回next【没有接收返回值的迭代器，在检测较严格的编译器中，

不管指向的位置是否正确，都会禁止使用，使用了就报错

】

---

删除迭代器区间

---

insert

在迭代器pos之前插入一个节点

为什么要返回newnode?

list的迭代器

pos在使用完insert之后其实是

不会失效

的

但是为了与其他容器的nsert的返回值进行统一，所以也返回了

指向新插入的节点的迭代器

---

在迭代器pos之前插入一个迭代器区间的数据

---

push_back

复用insert即可

voidpush_back(const T&val){insert(end(), val);}

---

push_front

复用insert即可

voidpush_front(const T& val){insert(begin(), val);}

---

pop_front

复用erese即可

voidpop_front(){erase(begin());}

---

pop_back

复用erese即可

voidpop_back(){erase(--end());}

---

size

---

empty

---

back

---

front

---

assign

---

resize

---

clear

复用erase

---

全部代码

#include<iostream>#include<assert.h>usingnamespace std;namespace mylist
{template<classT>structlistnode//双向带头循环链表的节点类{
        T _data;//节点存储的数据

        listnode* _next;//指向下一个节点的指针

        listnode* _prev;//指向前一个节点的指针};template<classT,classR,classF>structIterator{//把自己的类型重命名一下typedef Iterator<T, R, F> Self;//成员变量的类型是 双向带头循环链表的节点类型
        listnode<T>* _n;Iterator(listnode<T>*l=nullptr)//构造函数{
            _n = l;}
        Self&operator++()//前置++{//++就是指向下一个节点
            _n = _n->_next;return*this;}
        Self operator++(int)//后置++{
            Self tmp =*this;//先记录一下++之前的值

            _n = _n->_next;//再++return tmp;}
        Self&operator--()//前置--{//--就是指向上一个节点
            _n = _n->_prev;return*this;}
        Self operator--(int)//后置--{
            Self tmp =*this;//先记录一下--之前的值

            _n = _n->_prev;//再--return tmp;}

        R operator*()const{//类比指针//*就是获取  节点中存储的数据return _n->_data;}
        F operator->()const{//返回  节点中 存储数据的成员变量的  地址return&(_n->_data);}booloperator!=(const Self&obj)const{return _n != obj._n;}booloperator==(const Self& obj){return!(*this!= obj);}};template<classT,classR,classF>structReverse_iterator{//把自己的类型重命名一下typedef Reverse_iterator<T, R, F> Self;//成员变量的类型是 双向带头循环链表的节点类型
        listnode<T>* _n;Reverse_iterator(listnode<T>* l)//构造函数{
            _n = l;}

        Self&operator++(){//反向迭代器++，是移动到  前  一个节点
            _n = _n->_prev;return*this;}
        Self operator++(int){
            Self tmp =*this;
            _n = _n->_prev;return tmp;}
        Self&operator--(){//反向迭代器--，是移动到  后  一个节点
            _n = _n->_next;return*this;}
        Self operator--(int){
            Self tmp =*this;
            _n = _n->_next;return tmp;}
        R operator*()const{return _n->_data;}
        F operator->()const{return&(_n->_data);}booloperator!=(const Self& obj)const{return _n!=obj._n;}booloperator==(const Self& obj)const{return!(*this!= obj);}};template<classT>classlist{//把双向带头循环链表的节点类型重命名成nodetypedef listnode<T> node;private:
        node* _head;//唯一的成员变量//获取初始头结点
        node*get_head_node(){//申请一个节点大小的空间
            node* tmp =new node;//最开始的头节点的prev和next都指向自己
            tmp->_next = tmp;
            tmp->_prev = tmp;return tmp;}public:typedef  Iterator<T, T&, T*> iterator;//普通迭代器typedef  Iterator<T,const T&,const T*>  const_iterator;//const迭代器typedef  Reverse_iterator<T, T&, T*>  reverse_iterator;//反向迭代器typedef  Reverse_iterator<T,const T&,const T*> const_reverse_iterator;//const反向迭代器list(){//获取头结点//为之后的插入操作做准备
            _head=get_head_node();}list(size_t n,const T& val=T()){//必须先获取头节点，才能进行插入数据
            _head =get_head_node();for(int i =0; i < n; i++){push_back(val);//尾插n次}}template<classInputIterator>list(InputIterator first, InputIterator last){//必须先获取头节点，才能进行插入数据
            _head =get_head_node();while(first != last){//把解引用之后的值，一个一个尾插进去push_back(*first);
                first++;}}list(int n,const T& val =T()){//必须先获取头节点，才能进行插入数据
            _head =get_head_node();for(int i =0; i < n; i++){push_back(val);}}list(initializer_list<T> il){//必须先获取头节点，才能进行插入数据
            _head =get_head_node();auto it = il.begin();while(it != il.end()){//把解引用之后的值，一个一个尾插进去push_back(*it);
                it++;}}list(const list& obj){//必须先获取头节点，才能进行插入数据
            _head =get_head_node();//使用const迭代器接收  const修饰的对象的迭代器
            const_iterator it = obj.begin();while(it != obj.end()){//把解引用之后的获得的值，一个一个尾插进去push_back(*it);
                it++;}}~list(){//先把list里面除了头结点//以外的节点全部删除clear();//再把头结点申请的空间释放delete _head;

            _head =nullptr;}

        list&operator=(list obj){swap(obj);return*this;}voidswap(list& obj){//调用库里面的swap，交换头指针
            std::swap(_head, obj._head);}

        iterator begin(){//头节点的下一个节点 才是第一个节点return _head->_next;}//const修饰的对象只能调用const修饰的成员函数
        const_iterator begin()const{//头节点的下一个节点 才是第一个节点return _head->_next;}

        iterator end(){//最后一个节点的下一个节点是  头节点//因为是循环链表return _head;}//const修饰的对象只能调用const修饰的成员函数
        const_iterator end()const{return _head;}

        reverse_iterator rend(){//反向迭代器的rend返回的是第一个节点的   前一个节点return _head;}//const修饰的对象只能调用const修饰的成员函数
        const_reverse_iterator rend()const{return _head;}
        reverse_iterator rbegin(){//反向迭代器的rbegin()返回的是  最后一个节点//最后一个节点是  头节点的前一个//因为是循环链表return _head->_prev;}

        const_reverse_iterator rbegin()const{return _head->_prev;}voidpush_back(const T&val){/*node* tail = _head->_prev;

            node* newnode = new node;
            newnode->_data = val;
            newnode->_next = _head;
            newnode->_prev = tail;

            tail->_next = newnode;

            _head->_prev = newnode;*/insert(end(), val);}

        iterator erase(iterator pos){//不能  把 头节点 给删了assert(pos!=end());//记录pos的前一个节点（prev） // 和后一个节点（next）
            node* prev = pos._n->_prev;
            node* next = pos._n->_next;//让prev的下一个节点变成next
            prev->_next = next;//让prev的上一个节点变成next
            next->_prev = prev;//释放pos指向的节点delete pos._n;//返回被删除的节点的下一个节点//用于更新迭代器return next;}

        iterator erase(iterator first, iterator last){
            iterator it = first;while(it != last){//删除it指向的节点//删除后让it接收返回值，进行更新
                it =erase(it);}//返回被删除的  最后一个节点  的下一个节点//用于更新迭代器return last;}boolempty()const{//size==0就   是空    返回true//size!=0就   不是空  返回falsereturnsize()==0;}

        size_t size()const{//用count记录节点个数
            size_t count =0;//使用const迭代器接收  const修饰的对象的迭代器
            const_iterator it =begin();//遍历链表while(it !=end()){
                count++;++it;}return count;}

        T&back(){//list不能为空，为空就报错assert(!empty());//end（）返回的迭代器指向  头结点//头结点的上一个节点就是，最后一个节点//因为是循环链表return*(--end());}//const修饰的成员，只能调用const修饰的成员函数const T&back()const{assert(!empty());return*(--end());}

        T&front(){//list不能为空，为空就报错assert(!empty());//begin()返回的迭代器  就指向第一个节点return*begin();}//const修饰的成员，只能调用const修饰的成员函数const T&front()const{assert(!empty());return*begin();}template<classInputIterator>voidassign(InputIterator first, InputIterator last){//先把数据现有的节点(除了头结点)都删除clear();//再循环把数据一个一个尾插进去while(first != last){//尾插push_back(*first);
                first++;}}voidassign(size_t n,const T& val){clear();for(int i =0; i < n; i++){push_back(val);}}voidassign(int n,const T& val){clear();for(int i =0; i < n; i++){push_back(val);}}

        iterator insert(iterator pos,const T& val){//记录指向 pos 前一个节点的指针
            node* prev = pos._n->_prev;//申请新节点的空间
            node* newnode =new node;//存储数据
            newnode->_data = val;

            newnode->_next = pos._n;
            newnode->_prev = prev;

            prev->_next = newnode;
            pos._n->_prev = newnode;//返回指向新插入的节点的迭代器//用于更新迭代器return newnode;}template<classInputIterator>voidinsert(iterator pos, InputIterator first, InputIterator last){while(first!=last){//循环插入即可//因为list的迭代器使用完insert之后 不会失效//所以不用接收返回值  也可以insert(pos,*first);
                first++;}}voidpush_front(const T& val){insert(begin(), val);}voidpop_front(){erase(begin());}voidpop_back(){erase(--end());}voidresize(size_t n,const T& val =T()){//获取一下size，加快后续比较效率//因为获取size()的时间复杂度为  O(N)
            size_t size =this->size();if(n > size){//缺失的数据用val填上//填到size()==n为止while(size < n){push_back(val);++size;}}else{//把多出来的数据（节点）删除//删除到n==size()为止while(n < size){pop_back();
                    n++;}}}voidclear(){//[begin(),end())之间的数据//就是所有的有效数据(节点)//复用erase删除即可erase(begin(),end());}};}