一、模拟实现接口总览

实现接口总览

//无参构造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模拟实现

一、模拟实现接口总览

二、整体框架搭建

2.1 节点类框架搭建

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

2.3 迭代器类框架搭建

2.3.1 迭代器分类

2.3.2 list 所需迭代器分析

2.3.3 list普通迭代器实现

2.3.4 list的const迭代器实现

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

2.4 整体框架代码

三、list函数接口模拟实现

3.1 构造函数

3.1.2 迭代器区间构造

3.1.3 拷贝构造

3.2 赋值重载

3.3 析构函数

3.4 Iterators

3.5 Capacity

3.6 Modifiers

四、list模拟实现全部代码

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

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

一、模拟实现接口总览

二、整体框架搭建

2.1 节点类框架搭建

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

2.3 迭代器类框架搭建

2.3.1 迭代器分类

2.3.2 list 所需迭代器分析

2.3.3 list普通迭代器实现

2.3.4 list的const迭代器实现

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

2.4 整体框架代码

三、list函数接口模拟实现

3.1 构造函数

3.1.2 迭代器区间构造

3.1.3 拷贝构造

3.2 赋值重载

3.3 析构函数

3.4 Iterators

3.5 Capacity

3.6 Modifiers

四、list模拟实现全部代码

热门文章

最新文章

相关课程

相关电子书