一、模拟实现接口总览

实现接口总览

//无参构造list()
//迭代器区间构造template<classInputIterator>//拷贝构造 - 现代写法list(constlist<T>&lt)
//赋值重载 - 现代写法list<T>&operator=(list<T>lt)
//析构函数~list()
//Iteratorsiteratorend()
iteratorbegin()
const_iteratorend()constconst_iteratorbegin()const//Capacityboolempty()constsize_tsize() const//Modifiersiteratorinsert(iteratorpos, constT&x)
iteratorerase(iteratorpos)
voidpush_back(constT&x)
voidpop_back()
voidpush_front(constT&x)
voidpop_front()
voidswap(list<T>&lt)
voidclear()

注：list 的模拟实现，重点放在 list 模拟实现的整体框架和迭代器的实现上，实现参考版本：SGI版 STL3.0 的写法

SLT 的模拟实现，不是为了造更好的轮子，而是为了去学习它，理解它的底层，自己造一次，心里会更清楚，更利于加深对它们的理解

二、整体框架搭建

注：模拟实现的代码要写在自己的命名空间里面，否则会与库中的产生冲突

2.1 节点类框架搭建

首先，我们知道 list 就是一个带头双向循环链表

因此，我们若要实现 list，则首先需要实现一个结点类。而一个结点需要存储的信息有：数据、前一个结点的地址、后一个结点的地址，于是该结点类的成员变量也就出来了（数据、前驱指针、后继指针）-> (_data、_prve、_next) ，还有一个哨兵位的头节点 _head

框架：

#pragma once#include <iostream>usingnamespacestd;
namespacefy{
template<classT>structlist_node    {
//成员变量list_node<T>*_prve; //前驱指针list_node<T>*_next; //后继指针T_data;             //数据域    };
}

该类只需要对节点进行初始化即可，即该类只需提供构造函数

#pragma once#include <iostream>usingnamespacestd;
namespacefy{
template<classT>structlist_node    {
//成员函数//构造函数list_node(constT&x)
            :_prve(nullptr)
            , _next(nullptr)
            , _data(x)
        {}
//成员变量list_node<T>*_prve; //前驱指针list_node<T>*_next; //后继指针T_data;             //数据域    };
}

2.2 头节点类框架搭建（list模拟实现主体）

list是一个带头双向循环链表，在构造一个list对象时，直接申请一个头结点，并让其前驱指针和后继指针都指向自己即可，list 模拟实现主体也在这个类里面

节点类为什么不封装在头结点类里面？节点类为什么使用 struct 不使用 class?

C++ 不喜欢使用内部类；使用 struct 和 class 都可以，看你喜欢使用哪一个，struct 没有访问超限定符限制，如果使用 class 需要把成员变量设置为公有

#pragma once#include <iostream>usingnamespacestd;
namespacefy{
//结点类template<classT>structlist_node    {
//成员函数//构造函数list_node(constT&x)
            :_prve(nullptr)
            , _next(nullptr)
            , _data(x)
        {}
//成员变量list_node<T>*_prve; //前驱指针list_node<T>*_next; //后继指针T_data;             //数据域    };
//头结点类（list模拟实现主体）template<classT>classlist    {
typedeflist_node<T>node;
public:
private:
node*_head; //头结点    };
}

主体实现下面详解，这里先说一下框架

2.3 迭代器类框架搭建

2.3.1 迭代器分类

前面学习了 string 和 vector，我们已经知道迭代器的行为像指针，迭代器是内嵌类型（封装在类里面或内部类里面）

迭代器分类：

单向迭代器：只能 ++，不能 --；比如单链表
双向迭代器：既能 ++ 也能 --；比如 list
随机迭代器：即可以随机访问，既能 ++ 也能 --，还能 + 还能 -；比如：vector、string

2.3.2 list 所需迭代器分析

list 模拟实现最重点是 list迭代器的实现，因为这里的迭代器的实现和我们之前讲的实现方式都不同。我们之前讲的 string 和 vector 的迭代器都是一个原生指针，实现起来是非常简单的

为什么原生指针就可以满足 string 和 vector 迭代器的需求？

因为 string 和 vector 开辟的空间都是一块连续的内存空间，通过指针进行自增（++）、自减（--）以及解引用（*）等操作，就可以对相应位置的数据进行一系列操作，因此原生指针可以满足 string 和 vector 迭代器的需求

但是 list 是一个链表，在空间上不是连续的，原生指针如何往后走？原生指针无法进行 list 迭代器的各项操作（++、--、* 等等），这就说明原生指针已经不满足 list 迭代器的需要了

而迭代器的意义就是，让使用者可以不必关心容器的底层实现，可以用简单统一的方式对容器内的数据进行访问，可分为两点：

封装底层实现，不暴露底层实现的细节

提供统一的访问方式，降低使用成本

所以，想要满足 list 迭代器的需求，就必须对指针进行封装和重载，让其支持 list 迭代器的需求

如何进行封装和重载？单独提供一个类，在里面就那些封装和重载

2.3.3 list普通迭代器实现

框架：

//迭代器类template<classT>struct__list_iterator{
typedeflist_node<T>node;
//成员变量node*_pnode;
};

（1）构造函数

迭代器类实际上就是对结点指针进行了封装，其成员变量就只有一个，那就是结点指针，其构造函数直接根据所给结点指针构造一个迭代器对象即可，即迭代器类只需要提供构造函数

//构造函数__list_iterator(node*p)
    :_pnode(p)
{}

（2）++运算符的重载

前置++：让结点指针指向后一个结点，然后再返回 ++ 后的结点指针即可

//前置++__list_iterator<T>&operator++()
{
_pnode=_pnode->_next; //让结点指针指向下一个结点return*this; //返回++后的结点指针}

后置++：先记录当前结点指针，然后让结点指针指向后一个结点，然后再返回 ++ 前的结点指针即可

//后置++__list_iterator<T>&operator++(int)
{
__list_iterator<T>tmp(*this); //记录当前结点指针_pnode=_pnode->_next; //让结点指针指向下一个结点returntmp; //返回++前的结点指针}

（3）--运算符的重载

前置--：让结点指针指向前一个结点，然后再返回 -- 后的结点指针即可

//前置--__list_iterator<T>&operator--()
{
_pnode=_pnode->_prve; //让结点指针指向前一个结点return*this; //返回--后的结点指针}

后置--：先记录当前结点指针，然后让结点指针指向前一个结点，然后再返回 -- 前的结点指针即可

//后置--__list_iterator<T>&operator--(int)
{
__list_iterator<T>tmp(*this); //记录当前结点指针_pnode=_pnode->_prve; //让结点指针指向前一个结点returntmp; //返回--前的结点指针}

（4）解引用就是取结点 _node 里的数据 _data

T&operator*()
{
return_pnode->_data;
}

（5）!=运算符的重载

两个迭代器结点的指针指向的是同一个结点，那就说明是相等的迭代器，否则不相等

booloperator!=(const__list_iterator<T>&it)
{
return_pnode!=it._pnode;
}

就先介绍到这，其他就先不介绍了

迭代器代码总览

//迭代器类template<classT>struct__list_iterator{
typedeflist_node<T>node;
//成员函数//构造函数__list_iterator(node*p)
        :_pnode(p)
    {}
T&operator*()
    {
return_pnode->_data;
    }
//前置++__list_iterator<T>&operator++()
    {
_pnode=_pnode->_next; //让结点指针指向下一个结点return*this; //返回++后的结点指针    }
//后置++__list_iterator<T>&operator++(int)
    {
__list_iterator<T>tmp(*this); //记录当前结点指针_pnode=_pnode->_next; //让结点指针指向下一个结点returntmp; //返回++前的结点指针    }
//前置--__list_iterator<T>&operator--()
    {
_pnode=_pnode->_prve; //让结点指针指向前一个结点return*this; //返回--后的结点指针    }
//后置--__list_iterator<T>&operator--(int)
    {
__list_iterator<T>tmp(*this); //记录当前结点指针_pnode=_pnode->_prve; //让结点指针指向前一个结点returntmp; //返回--前的结点指针    }
booloperator!=(const__list_iterator<T>&it)
    {
return_pnode!=it._pnode;
    }
booloperator==(const__list_iterator<T>&it)
    {
return_pnode==it._pnode;
    }
//成员变量node*_pnode;
};

2.3.4 list的const迭代器实现

普通迭代器是可读可写，const 迭代器是只读，不支持修改数据，即普通迭代器访问普通对象，可读可写；const 迭代器访问 const 对象，可读但不可写

直接在类成员函数前面加 const ，这种写法是错误的

1. T& operator*()
2. const T& operator*()const//error

第一个：非 const 对象可以调用（即可以 *），也可以进行 ++ 等操作，没毛病

第二个：const 对象调用（可以 *），但是不能进行 ++ 等操作，因为 ++ 没有 const 版本，++ 本来就是写函数，所以这种方法不行

const 迭代器实现的方法是把 list_iterator 这个类复制一下，然后把名称改成 __const_list_iterator

//迭代器类template<classT>struct__list_iterator{
typedeflist_node<T>node;
//成员函数//构造函数__list_iterator(node*p)
        :_pnode(p)
    {}
T&operator*()
    {
return_pnode->_data;
    }
//前置++__list_iterator<T>&operator++()
    {
_pnode=_pnode->_next; //让结点指针指向下一个结点return*this; //返回++后的结点指针    }
//后置++__list_iterator<T>&operator++(int)
    {
__list_iterator<T>tmp(*this); //记录当前结点指针_pnode=_pnode->_next; //让结点指针指向下一个结点returntmp; //返回++前的结点指针    }
//前置--__list_iterator<T>&operator--()
    {
_pnode=_pnode->_prve; //让结点指针指向前一个结点return*this; //返回--后的结点指针    }
//后置--__list_iterator<T>&operator--(int)
    {
__list_iterator<T>tmp(*this); //记录当前结点指针_pnode=_pnode->_prve; //让结点指针指向前一个结点returntmp; //返回--前的结点指针    }
booloperator!=(const__list_iterator<T>&it)
    {
return_pnode!=it._pnode;
    }
booloperator==(const__list_iterator<T>&it)
    {
return_pnode==it._pnode;
    }
//成员变量node*_pnode;
};
//const迭代器类template<classT>struct__list_const_iterator{
typedeflist_node<T>node;
//成员函数//构造函数__list_const_iterator(node*p)
        :_pnode(p)
    {}
constT&operator*()
    {
return_pnode->_data;
    }
//前置++__list_const_iterator<T>&operator++()
    {
_pnode=_pnode->_next; //让结点指针指向下一个结点return*this; //返回++后的结点指针    }
//后置++__list_const_iterator<T>&operator++(int)
    {
__list_const_iterator<T>tmp(*this); //记录当前结点指针_pnode=_pnode->_next; //让结点指针指向下一个结点returntmp; //返回++前的结点指针    }
//前置--__list_const_iterator<T>&operator--()
    {
_pnode=_pnode->_prve; //让结点指针指向前一个结点return*this; //返回--后的结点指针    }
//后置--__list_const_iterator<T>&operator--(int)
    {
__list_const_iterator<T>tmp(*this); //记录当前结点指针_pnode=_pnode->_prve; //让结点指针指向前一个结点returntmp; //返回--前的结点指针    }
booloperator!=(const__list_const_iterator<T>&it)
    {
return_pnode!=it._pnode;
    }
booloperator==(const__list_const_iterator<T>&it)
    {
return_pnode==it._pnode;
    }
//成员变量node*_pnode;
};

然后 list 的const的迭代器就完成了，这种实现方式可以是可以，但是这么实现好像有点搓啊！代码极度冗余！！这个 const 迭代器和普通迭代器也就是类型名称和返回值不一样而已

我们去看看源码，看看大佬是怎么写的（源码已经上传资源了，审核中）

大佬在定义 template 模板的时增加一个模板参数 Ref（第三个模板参数下面讲），然后只需修改一下就可以了，const 迭代器和非 const 迭代器就完成了

但是改起来太麻烦了，直接进行 typedef 一下

typedrf __list_iterator<T, Ref> Self;

//迭代器类// 同一个类模板实例化出的两个类型// typedef __list_iterator<T, T&> iterator;// typedef __list_iterator<T, const T&> const_iterator;template<classT, classRef>struct__list_iterator{
typedeflist_node<T>node;
typedrf__list_iterator<T, Ref>Self;
//成员函数//构造函数__list_iterator(node*p)
        :_pnode(p)
    {}
Refoperator*()
    {
return_pnode->_data;
    }
//前置++Self&operator++()
    {
_pnode=_pnode->_next; //让结点指针指向下一个结点return*this; //返回++后的结点指针    }
//后置++Self&operator++(int)
    {
Selftmp(*this); //记录当前结点指针_pnode=_pnode->_next; //让结点指针指向下一个结点returntmp; //返回++前的结点指针    }
//前置--Self&operator--()
    {
_pnode=_pnode->_prve; //让结点指针指向前一个结点return*this; //返回--后的结点指针    }
//后置--Self&operator--(int)
    {
Selftmp(*this); //记录当前结点指针_pnode=_pnode->_prve; //让结点指针指向前一个结点returntmp; //返回--前的结点指针    }
booloperator!=(constSelf&it)
    {
return_pnode!=it._pnode;
    }
booloperator==(constSelf&it)
    {
return_pnode==it._pnode;
    }
//成员变量node*_pnode;
};

这样const版本的迭代器和非const版本的迭代器就完成了，接下来说迭代器的第三个模板参数 Ptr

2.3.5 list迭代器第三个模板参数Ptr

->运算符的重载

T*operator->()
{
return&_pnode->_data;
}

这里也是 const 和非const 版本的问题，直接加第三个模板参数 Ptr 即可解决

参数修改直接在这两处添加即可，这就是 typedef 好处

//迭代器类// 同一个类模板实例化出的两个类型// typedef __list_iterator<T, T&, T*> iterator;// typedef __list_iterator<T, const T&, const T*> const_iterator;template<classT, classRef, classPtr>struct__list_iterator{
typedeflist_node<T>node;
typedef__list_iterator<T, Ref, Ptr>Self;
//成员函数//构造函数__list_iterator(node*p)
        :_pnode(p)
    {}
Ptroperator->()
    {
return&_pnode->_data;
    }
Refoperator*()
    {
return_pnode->_data;
    }
//前置++Self&operator++()
    {
_pnode=_pnode->_next; //让结点指针指向下一个结点return*this; //返回++后的结点指针    }
//后置++Self&operator++(int)
    {
Selftmp(*this); //记录当前结点指针_pnode=_pnode->_next; //让结点指针指向下一个结点returntmp; //返回++前的结点指针    }
//前置--Self&operator--()
    {
_pnode=_pnode->_prve; //让结点指针指向前一个结点return*this; //返回--后的结点指针    }
//后置--Self&operator--(int)
    {
Selftmp(*this); //记录当前结点指针_pnode=_pnode->_prve; //让结点指针指向前一个结点returntmp; //返回--前的结点指针    }
booloperator!=(constSelf&it)
    {
return_pnode!=it._pnode;
    }
booloperator==(constSelf&it)
    {
return_pnode==it._pnode;
    }
//成员变量node*_pnode;
};

某些情景下，我们使用迭代器的时候可能会用到 -> 运算符，后面在讲

迭代器类的拷贝构造、赋值重载、析构函数为什么不用实现？

拷贝构造和赋值不需要自己实现，默认生成的即可，当前迭代器赋值给另一个迭代器是不需要深拷贝的，浅拷贝就可以，拷贝构造也是；析构释放空间的事情不归迭代器类管理，迭代器类只需构建迭代器对象即可，释放空间归 list 管理

到这里，基本框架已经打好了，下面可以直接实现 list 了

2.4 整体框架代码

#pragma once#include <iostream>usingnamespacestd;
namespacefy{
//结点类template<classT>structlist_node    {
//成员函数//构造函数list_node(constT&x)
            :_prve(nullptr)
            , _next(nullptr)
            , _data(x)
        {}
//成员变量list_node<T>*_prve; //前驱指针list_node<T>*_next; //后继指针T_data;             //数据域    };
//迭代器类// 同一个类模板实例化出的两个类型// typedef __list_iterator<T, T&, T*> iterator;// typedef __list_iterator<T, const T&, const T*> const_iterator;template<classT, classRef, classPtr>struct__list_iterator    {
typedeflist_node<T>node;
typedef__list_iterator<T, Ref, Ptr>Self;
//成员函数//构造函数__list_iterator(node*p)
            :_pnode(p)
        {}
Ptroperator->()
        {
return&_pnode->_data;
        }
Refoperator*()
        {
return_pnode->_data;
        }
//前置++Self&operator++()
        {
_pnode=_pnode->_next; //让结点指针指向下一个结点return*this; //返回++后的结点指针        }
//后置++Self&operator++(int)
        {
Selftmp(*this); //记录当前结点指针_pnode=_pnode->_next; //让结点指针指向下一个结点returntmp; //返回++前的结点指针        }
//前置--Self&operator--()
        {
_pnode=_pnode->_prve; //让结点指针指向前一个结点return*this; //返回--后的结点指针        }
//后置--Self&operator--(int)
        {
Selftmp(*this); //记录当前结点指针_pnode=_pnode->_prve; //让结点指针指向前一个结点returntmp; //返回--前的结点指针        }
booloperator!=(constSelf&it)
        {
return_pnode!=it._pnode;
        }
booloperator==(constSelf&it)
        {
return_pnode==it._pnode;
        }
//成员变量node*_pnode;
    };
//头结点类（list模拟实现主体）template<classT>classlist    {
typedeflist_node<T>node;
public:
typedef__list_iterator<T, T&, T*>iterator;
typedef__list_iterator<T, constT&, constT*>const_iterator;
private:
node*_head; //头结点    };
}

list 模拟实现，最重要的就是上面框架的实现了，下面开始实现 list 的函数接口

三、list函数接口模拟实现

3.1 构造函数

3.1.1 无参构造

list是一个带头双向循环链表，在构造一个list对象时，直接申请一个头结点，并让其前驱指针和后继指针都指向自己即可，直接写一个empty_initialize() 函数，进行复用，注：为了方便，_size 是新添加的成员变量，_size 也要置 0

list()
{
empty_initialize();
}
voidempty_initialize()
{
_head=newnode(T());
_head->_next=_head;
_head->_prve=_head;
_size=0;
}

3.1.2 迭代器区间构造

提供一段迭代器区间进程构造，创建新头结点，遍历尾插到新头结点即可

//迭代器区间构造template<classInputIterator>list(InputIteratorfirst, InputIteratorlast)
{
//初始化头结点empty_initialize();
//遍历进行尾插while (first!=last)
    {
push_back(*first);
++first;
    }
}

3.1.3 拷贝构造

拷贝构造要注意深浅拷贝的问题

（1）传统写法

也是创建新头结点，遍历尾插到新头结点即可

//拷贝构造//传统写法list(constlist<T>&lt)
{
empty_initialize();//初始化头结点for (constauto&e : lt)//遍历进行尾插    {
push_back(e);
    }
}

（2）现代写法

复用迭代器区间构造，创建一个 tmp，再进行交换即可

//现代写法list(constlist<T>&lt)
{
empty_initialize();//初始化头结点list<T>tmp(lt.begin(), lt.end());
swap(tmp);//两个对象交换}

3.2 赋值重载

赋值重载也要注意深浅拷贝的问题

（1）传统写法

先调用clear函数将原容器清空，然后将容器 lt 当中的数据，通过遍历的方式一个个尾插到清空后的容器当中即可

//赋值重载list<T>&operator=(constlist<T>&lt)
{
if (this!=&lt)
    {
clear();//清空容器for (constauto&e : lt)//遍历进行尾插        {
push_back(e);
        }
    }
return*this;
}

（2）现代写法

传参使用传值传参，自动调用其拷贝构造函数，然后交换两个对象即可

//现代写法list<T>&operator=(list<T>lt)//传值传参，自动调用拷贝构造{
swap(lt);//交换两个对象return*this;
}

3.3 析构函数

在 clear 函数实现的情况下，可以直接复用，最后再将头结点删除释放置空即可

//析构函数~list()
{
clear();//复用delete_head;//删除释放头结点_head=nullptr;//置空}

3.4 Iterators

首先对迭代器类 typedef

typedef__list_iterator<T, T&, T*>iterator;
typedef__list_iterator<T, constT&, constT*>const_iterator;

（1） end

end函数返回的是最后一个有效数据的下一个位置的迭代器，最后一个有效数据的下一个节点就是头结点，可以直接使用匿名对象

iteratorend()
{
//iterator it(_head);//return it;//使用匿名对象，便捷returniterator(_head);
}

const版本，只读

const_iteratorend()
{
returnconst_iterator(_head);
}

2）begin

begin函数返回的是第一个有效数据的迭代器，第一个有效数据就是头结点的下一个结点

iteratorbegin()
{
returniterator(_head->_next);
}

const版本，只读

const_iteratorbegin()
{
returnconst_iterator(_head->_next);
}

3.5 Capacity

（1）empty

empty用于判断容器 list 是否为空，直接判断该容器的 begin 和 end 所返回的迭代器，是否是同一个位置的迭代器即可，是同一个说明容器当中只有一个头结点；或者直接判断 _size 是否为 0，注：为了方便，_size 是新添加的成员变量

boolempty()const{
return_size==0;
}

（2）size

size函数用于获取当前容器当中的有效数据个数

size_tsize() const{
return_size;
}

3.6 Modifiers

这里很多函数都可以进行复用，首先实现 insert 和 erase 这两个函数，然后进行复用

（1）insert

insert 可以在所给迭代器之前插入一个新结点，insert 之后，pos 迭代器不失效，我们也可以返回新节点位置的迭代器

iteratorinsert(iteratorpos, constT&x)
{
//建立一个新节点node*newnode=newnode(x);
node*cur=pos._pnode;
node*prve=cur->_prve;
//与新节点 newnode 建立连续prve->_next=newnode;
newnode->_prve=prve;
newnode->_next=cur;
cur->_prve=newnode;
//有效数据+1++_size;
returniterator(newnode);//返回新节点迭代器的位置}

（2） erase

erase函数可以删除所给迭代器位置的结点，删除之后 pos 位置的迭代器就失效了，为了防止失效，我们可以返回被删除节点的下一个节点的迭代器

iteratorerase(iteratorpos)
{
assert(pos!=end());//不能删头结点//节点重新建立联系node*prve=pos._pnode->_prve;
node*next=pos._pnode->_next;
prve->_next=next;
next->_prve=prve;
//释放被删除节点的空间，有效数据个数-1deletepos._pnode;
--_size;
returniterator(next);//返回被删除节点的下一个节点的迭代器}

（3）push_back和pop_back

push_back是尾插，即在头结点前插入结点；pop_back是尾删，即删除头结点的前一个结点。在已经实现了insert和erase函数的情况下，我们可以通过复用函数来实现push_back和pop_back函数

voidpush_back(constT&x)
{
insert(end(), x);
}
voidpop_back()
{
erase(--end());
}

（4）push_front和pop_front

push_front 是头插，即在第一个有效结点前插入结点，头结点后插入新节点；pop_front是头删，即删除第一个有效结点，头结点的下一个节点；也是直接复用 insert 和 erase 来实现

voidpush_front(constT&x)
{
insert(begin(), x);
}
voidpop_front()
{
erase(begin());
}

（5）swap

swap函数用于交换两个容器，只需将两个容器当中的头指针交换即可，还有 _size 交换一下即可

voidswap(list<T>&lt)
{
std::swap(_head, lt._head);//使用库 swapstd::swap(_size, lt._size);
}

（6）clear

clear函数用于清空容器，通过遍历的方式，逐个删除结点，只保留头结点即可

voidclear()
{
iteratorit=begin();
while (it!=end())
    {
it=erase(it);//重新赋值，防止迭代器it 失效    }
}

四、list模拟实现全部代码

list.h

#pragma once#include <iostream>#include <assert.h>usingnamespacestd;
namespacefy{
//结点类template<classT>structlist_node    {
//成员函数//构造函数list_node(constT&x)
            :_prve(nullptr)
            , _next(nullptr)
            , _data(x)
        {}
//成员变量list_node<T>*_prve; //前驱指针list_node<T>*_next; //后继指针T_data;             //数据域    };
//迭代器类// 同一个类模板实例化出的两个类型// typedef __list_iterator<T, T&, T*> iterator;// typedef __list_iterator<T, const T&, const T*> const_iterator;template<classT, classRef, classPtr>struct__list_iterator    {
typedeflist_node<T>node;
typedef__list_iterator<T, Ref, Ptr>Self;
//成员函数//构造函数__list_iterator(node*p)
            :_pnode(p)
        {}
Ptroperator->()
        {
return&_pnode->_data;
        }
Refoperator*()
        {
return_pnode->_data;
        }
//前置++Self&operator++()
        {
_pnode=_pnode->_next; //让结点指针指向下一个结点return*this; //返回++后的结点指针        }
//后置++Self&operator++(int)
        {
Selftmp(*this); //记录当前结点指针_pnode=_pnode->_next; //让结点指针指向下一个结点returntmp; //返回++前的结点指针        }
//前置--Self&operator--()
        {
_pnode=_pnode->_prve; //让结点指针指向前一个结点return*this; //返回--后的结点指针        }
//后置--Self&operator--(int)
        {
Selftmp(*this); //记录当前结点指针_pnode=_pnode->_prve; //让结点指针指向前一个结点returntmp; //返回--前的结点指针        }
booloperator!=(constSelf&it)
        {
return_pnode!=it._pnode;
        }
booloperator==(constSelf&it)
        {
return_pnode==it._pnode;
        }
//成员变量node*_pnode;
    };
const迭代器类//template<class T>//struct __list_const_iterator//{//  typedef list_node<T> node;//  //成员函数//  //构造函数//  __list_const_iterator(node* p)//      :_pnode(p)//  {}//  const T& operator*()//  {//      return _pnode->_data;//  }//  //前置++//  __list_const_iterator<T>& operator++()//  {//      _pnode = _pnode->_next; //让结点指针指向下一个结点//      return *this; //返回++后的结点指针//  }//  //后置++//  __list_const_iterator<T>& operator++(int)//  {//      __list_const_iterator<T> tmp(*this); //记录当前结点指针//      _pnode = _pnode->_next; //让结点指针指向下一个结点//      retrun tmp; //返回++前的结点指针//  }//  //前置--//  __list_const_iterator<T>& operator--()//  {//      _pnode = _pnode->_prve; //让结点指针指向前一个结点//      return *this; //返回--后的结点指针//  }//  //后置--//  __list_const_iterator<T>& operator--(int)//  {//      __list_const_iterator<T> tmp(*this); //记录当前结点指针//      _pnode = _pnode->_prve; //让结点指针指向前一个结点//      retrun tmp; //返回--前的结点指针//  }//  bool operator!=(const __list_const_iterator<T>& it)//  {//      return _pnode != it._pnode;//  }//  bool operator==(const __list_const_iterator<T>& it)//  {//      return _pnode == it._pnode;//  }//  //成员变量//  node* _pnode;//};//头结点类（list模拟实现主体）template<classT>classlist    {
typedeflist_node<T>node;
public:
typedef__list_iterator<T, T&, T*>iterator;
typedef__list_iterator<T, constT&, constT*>const_iterator;
//无参构造list()
        {
empty_initialize();
        }
voidempty_initialize()
        {
_head=newnode(T());
_head->_next=_head;
_head->_prve=_head;
_size=0;
        }
//迭代器区间构造template<classInputIterator>list(InputIteratorfirst, InputIteratorlast)
        {
//初始化头结点empty_initialize();
//遍历进行尾插while (first!=last)
            {
push_back(*first);
++first;
            }
        }
//拷贝构造传统写法//list(const list<T>& lt)//{//  empty_initialize();//初始化头结点//  for (const auto& e : lt)//遍历进行尾插//  {//      push_back(e);//  }//}//现代写法list(constlist<T>&lt)
        {
empty_initialize();//初始化头结点list<T>tmp(lt.begin(), lt.end());
swap(tmp);//两个对象交换        }
//赋值重载//list<T>& operator=(const list<T>& lt)//{//  if (this != &lt)//  {//      clear();//清空容器//      for (const auto& e : lt)//遍历进行尾插//      {//          push_back(e);//      }//  }//  return *this;//}//现代写法list<T>&operator=(list<T>lt)//传值传参，自动调用拷贝构造        {
swap(lt);//交换两个对象return*this;
        }
//析构函数~list()
        {
clear();//复用delete_head;//删除释放头结点_head=nullptr;//置空        }
//--------------------------------------------------------//Iteratorsiteratorend()
        {
//iterator it(_head);//return it;//使用匿名对象，便捷returniterator(_head);
        }
iteratorbegin()
        {
returniterator(_head->_next);
        }
const_iteratorend()const        {
returnconst_iterator(_head);
        }
const_iteratorbegin()const        {
returnconst_iterator(_head->_next);
        }
//--------------------------------------------------------//Capacityboolempty()const        {
return_size==0;
        }
size_tsize() const        {
return_size;
        }
//--------------------------------------------------------//Modifiersiteratorinsert(iteratorpos, constT&x)
        {
//建立一个新节点node*newnode=newnode(x);
node*cur=pos._pnode;
node*prve=cur->_prve;
//与新节点 newnode 建立连续prve->_next=newnode;
newnode->_prve=prve;
newnode->_next=cur;
cur->_prve=newnode;
//有效数据+1++_size;
returniterator(newnode);//返回新节点迭代器的位置        }
iteratorerase(iteratorpos)
        {
assert(pos!=end());//不能删头结点//节点重新建立联系node*prve=pos._pnode->_prve;
node*next=pos._pnode->_next;
prve->_next=next;
next->_prve=prve;
//释放被删除节点的空间，有效数据个数-1deletepos._pnode;
--_size;
returniterator(next);//返回被删除节点的下一个节点的迭代器        }
voidpush_back(constT&x)
        {
insert(end(), x);
        }
voidpop_back()
        {
erase(--end());
        }
voidpush_front(constT&x)
        {
insert(begin(), x);
        }
voidpop_front()
        {
erase(begin());
        }
voidswap(list<T>&lt)
        {
std::swap(_head, lt._head);//使用库 swapstd::swap(_size, lt._size);
        }
voidclear()
        {
iteratorit=begin();
while (it!=end())
            {
it=erase(it);//重新赋值，防止迭代器it 失效            }
        }
private:
node*_head; //头结点size_t_size;//记录节点有多少个    };
}

Test.cpp

#include "list.h"voidTest_list()
{
fy::list<int>lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
lt1.push_back(5);
fy::list<int>::iteratorit=lt1.begin();
while (it!=lt1.end())
    {
cout<<*it<<" ";
++it;
    }
cout<<endl;
fy::list<int>lt2(lt1);//拷贝构造for (autoe : lt2)//编译器自动转换成迭代器cout<<e<<" ";
cout<<endl;
fy::list<int>lt3(lt2.begin(), lt2.end());//迭代器区间构造for (autoe : lt3)//编译器自动转换成迭代器cout<<e<<" ";
cout<<endl;
fy::list<int>lt4;
lt4=lt3;//赋值重载for (autoe : lt4)//编译器自动转换成迭代器cout<<e<<" ";
cout<<endl;
cout<<"l4size: "<<lt4.size() <<endl;
//清空l4lt4.clear();
cout<<"清空后lt4size: "<<lt4.size() <<endl;
fy::list<int>lt5(lt1);
for (autoe : lt5)//编译器自动转换成迭代器cout<<e<<" ";
cout<<endl;
lt5.push_front(0);
lt5.push_front(-1);
lt5.push_front(-2);
for (autoe : lt5)//编译器自动转换成迭代器cout<<e<<" ";
cout<<endl;
lt5.pop_back();
lt5.pop_back();
lt5.pop_front();
for (autoe : lt5)//编译器自动转换成迭代器cout<<e<<" ";
cout<<endl;
}
intmain()
{
Test_list();
return0;
}

----------------我是分割线---------------

文章到这里就结束了，下一篇即将更新

【C++初阶】八、STL---list模拟实现