list【2】模拟实现（含迭代器实现超详解哦）

模拟实现list

引言（实现概述）

在前面，我们介绍了list的使用：
戳我看list的介绍与使用详解哦

在本篇文章中将重点介绍list的接口实现，通过模拟实现可以更深入的理解与使用list

我们模拟实现的 list 底层是一个带头双向循环链表

在实现list时，我们首先需要一个**结构体以表示链表中结点的结构

list_node

，大致包括数据与指向前后结点的指针**：

template<classT>structlist_node//结点类{
    list_node<T>* _prev;
    list_node<T>* _next;
    T _date;list_node(const T& date =T())//匿名对象:_prev(nullptr),_next(nullptr),_date(date){}};

在有了结点之后，还需要一个 **

list

类，包括双向链表的头结点指针

_pHead

，链表中的元素个数

_size

**：

template<classT>classlist//带头双向循环链表{typedef list_node<T> Node;private:
    Node* _pHead;
    size_t _size;};

大致结构如下：

关于带头双向循环链表的实现可以参考之前的C语言版本实现，在本篇文章中结构将不是最重点的内容：戳我看C语言实现带头双向循环链表详解哦

与vector相同，list是一个类模板，其声明与定义不能分离。我们将模拟实现的list放在我们创建的命名空间内，以防止与库发生命名冲突。
在list的模拟实现中，我们只实现一些主要的接口，包括默认成员函数、迭代器、容量、元素访问与数据修改：

list迭代器实现

与vector不同，list的迭代器是指针的封装，通过运算符重载来实现原生指针的功能。
我们可以通过封装结点的指针，即

list_node<T>*

，来实现迭代器：

默认成员函数

对于默认成员函数，其实我们只需要实现构造函数即可，这个

__list_iterator

类的属性只有一个结构体指针，并不存在类中申请的资源，所以编译器生成的析构函数与赋值运算符重载就够用了，不需要再实现了。

1. 默认构造 对于默认构造函数，我们可以使用缺省参数，即**参数类型为结构体指针，缺省值为nullptr**。 直接在初始化列表中用参数初始化类属性即可：

__list_iterator(Node* pNode =nullptr):_pNode(pNode){}

1. 拷贝构造 对于拷贝构造，参数必须是类类型的引用，可以加上const修饰（我们可以在类中将类类型__list_iterator<T, Ref, Ptr>重命名为self，以方便书写） 在函数中直接赋值即可：

__list_iterator(const self& it){
        _pNode = it._pNode;}

operator* 与 operator->

迭代器使用时应该是与指针基本类似的，所以也需要重载

*

与

->

。

1. 重载 * 指针当然可以进行解引用的操作，指向容器中元素的指针。对这个指针进行解引用操作结果就应该是该指针指向的元素。**对于list的迭代器而言，解引用该迭代器的结果就应该是结点中的_data元素的引用，类型为&T**： （我们可以为模板参数加上一个参数，即Ref，它表示T&）

    Ref operator*(){return _pNode->_date;}

1. 重载->*当T是自定义类型时，其指针还可以通过->直接访问到T类型对象_data中的元素，起指针作用的迭代器自然也需要实现这个功能。 但是对于这个运算符重载而言，它并不知道要返回T类型对象中的什么元素，所以*这个operator->函数可以直接返回该迭代器对应的结点中的_data元素的指针，然后在调用的时候再通过->来访问其中元素：it->->a;（通过迭代器it访问T类型对象中的a元素）。 但是，这样的形式访问又与指针的用法不一致，所以这里有一个特殊的规定，即规定需要使用it->a;的方式通过迭代器访问T类型对象中的元素，以获得与原生指针相同的使用方式： （我们可以为模板参数加上一个参数，即Ptr，它表示T*）

    Ptr operator->(){return&(_pNode->_date);}

operator++ 与 operator–

1. 重载 ++ ++操作即实现迭代器的指向向后移动一个元素，list的迭代器底层是一个结构体指针，所以只需要将当前_pNode->_next 赋值给_pNode即可 且++分为前置++与后置++，在区别这两个的实现时，前面类和对象时已经详细介绍过了，即给后置++增加一个参数int，但是不传参，只用于区分前置与后置。 另外后置++需要创建临时对象，在*this++后必须要返回临时对象而非引用：

    self&operator++(){
        _pNode = _pNode->_next;return*this;}
    self operator++(int){
        self temp(*this);
        _pNode = _pNode->_next;return temp;}

1. 重载 -- 重载--与前面的++类似，即将_pNode->_prev 赋值给_pNode即可：

    self&operator--(){
        _pNode = _pNode->_prev;return*this;}
    self operator--(int){
        self temp(*this);
        _pNode = _pNode->_prev;return temp;}

operator== 与 operator!=

对于

==

与

!=

重载，即判断两个迭代器对象的属性是否相等即可：

booloperator==(const self& it){return _pNode == it._pNode;}booloperator!=(const self& it){return _pNode != it._pNode;}

迭代器实现概览

template<classT,classRef,classPtr>struct__list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;

        Node* _pNode;__list_iterator(Node* pNode =nullptr):_pNode(pNode){}__list_iterator(const self& it){
            _pNode = it._pNode;}

        Ref operator*(){return _pNode->_date;}
        Ptr operator->(){return&(_pNode->_date);}

        self&operator++(){
            _pNode = _pNode->_next;return*this;}
        self operator++(int){
            self temp(*this);
            _pNode = _pNode->_next;return temp;}
        self&operator--(){
            _pNode = _pNode->_prev;return*this;}
        self operator--(int){
            self temp(*this);
            _pNode = _pNode->_prev;return temp;}booloperator==(const self& it){return _pNode == it._pNode;}booloperator!=(const self& it){return _pNode != it._pNode;}};

list主要接口实现

在实现list之前，我们可以对一些较为麻烦的类型进行重命名以方便书写：

typedef list_node<T>Node;typedef __list_iterator<T,T&,T*> iterator;typedef __list_iterator<T,constT&,constT*> const_iterator;

默认成员函数

构造函数

实现构造函数时，我们需要实现无参构造、n个指定元素构造、迭代器区间构造以及拷贝构造：

无参构造：
由于我们模拟实现的list底层为带头双向循环链表，所以在无参构造时虽然没有在list中放入元素，但是还使需要先放入一个空结点作为头节点。
创建头节点的操作在任何构造函数中都要先进行，所以我们将其封装为一个

init_empty_list

函数。这个初始化空list的函数需要

new

一个结点，然后使节点中的

_prev

与

_next

都指向它自身，最后将

_size

赋值为0：

voidinit_empty_list(){            
        _pHead =newNode();
        _pHead->_prev = _pHead;
        _pHead->_next = _pHead;
        _size =0;}list(){init_empty_list();}

n个指定元素构造：
使用

n

个指定元素构造有两个参数，第一个就是

int

，第二个是

const T&

，缺省值为

T()

函数中，首先调用

init_empty_list

构建一个头结点；
再循环，使用

push_bake

尾插

n

个指定元素

value

即可（push_back后面会实现）：

list(int n,const T& value =T()){init_empty_list();while(n--){push_back(value);}}

迭代器区间构造：
是用迭代器区间构造函数是一个函数模板，可以使用任何容器的迭代器区间来构造list
函数中，首先调用

init_empty_list

构建一个头结点；
然后再循环，使用

push_bake

尾插

first

迭代器的解引用出的元素，当

first

与

last

相等时出循环：

template<classIterator>list(Iterator first, Iterator last){init_empty_list();while(first != last){push_back(*first);++first;}}

拷贝构造：
拷贝构造函数的参数是一个

const list<T>&

实现时，首先调用

init_empty_list

构建一个头结点；
然后范围for，使用

push_bake

将l中的元素逐一尾插到list中：

list(const list<T>& l){init_empty_list();for(auto el : l){push_back(el);}}

析构函数

析构函数需要实现释放list中的资源。
首先复用

clear

，清空list中的元素。

clear

中会实现释放结点中的资源，后面部分会实现；
再

delete _pHead;

，释放头节点中的资源，它会调用结点结构体的析构函数：

~list(){clear();delete _pHead;}

赋值重载

对于赋值运算符重载，我们直接使用新写法，即先使用参数

l

创建一个临时对象；
然后使用

swap

将临时对象与

*this

交换（后面会实现

swap

函数）；
最后**返回

*this

即可，创建的临时对象就会在函数栈帧销毁时自动释放**：

    list<T>&operator=(const list<T>& l)//list& operator=(const list l) 对于赋值重载，这样也可{
        list<T>temp(l);swap(temp);return*this;}

迭代器

在前面已经实现了list的迭代器，它是结点指针的封装；

这里暂时只实现

begin

与

end

，关于反向迭代器的实现在后面会详细介绍。

begin

返回首元素的地址，即头结点的下一个结点的地址；

end

返回尾元素下一个位置的地址，即头节点的地址，他们分别重载有const版本：

    iterator begin(){returniterator(_pHead->_next);}
    iterator end(){returniterator(_pHead);}
    
    const_iterator begin()const{returnconst_iterator(_pHead->_next);}
    const_iterator end()const{returnconst_iterator(_pHead);}

容量

在容器部分，由于list并没有容量的概念，所以我们只需要实现

size

与

empty

即可；

我们在list的属性中，**我们设置了

_size

，在插入元素时

_size++

，删除元素时

_size--

，所以这里只需要返回

_size

的值即可；**
当

_size == 0

时，list为空，

empty

返回

true

，否者返回

false

：

    size_t size()const{return _size;}boolempty()const{if(_size ==0)returntrue;elsereturnfalse;}

元素访问

由于list在任意位置访问元素的成本较高，就没有提供

operator[]

的接口，所以我们只需要实现

front

与

back

即可。分别返回首尾的元素，有普通对象与const对象两个重载版本：

在实现时，我们**可以借助list的属性

_pHead

，即头结点的指针来访问首尾元素：
我们模拟实现list的底层是带头双向循环链表，所以list中的第一个元素就是

_pHead->_next

指向的结点中的元素；list中的

_pHead->_prev

指向的结点中的元素**：

front

只需要返回

_pHead->_next->_date

即可；
back返回

_pHead->_prev->_date

即可，返回值类型为

T&

，const版本就返回

const T&

即可：

    T&front(){return _pHead->_next->_date;}const T&front()const{return _pHead->_next->_date;}
    
    T&back(){return _pHead->_prev->_date;}const T&back()const{return _pHead->_prev->_date;}

数据修改

insert

list 的结构使在任意位置插入数据的效率是较高的，**只需要创建结点，再链接到

pos

位置前即可**：

在实现

insert

时，首先

new

一个结点，类型为

Node

，并用

val

初始化（这个Node类型是前面重命名后的类型）；
这时我们需要记录

pos

位置的结点指针为

cur

，

pos

位置前面的结点指针为

prev

，以方便后续链接；
然后将

pos

结点的前一个结点与新结点链接，即

newnode

与

prev

链接；
再将

pos

结点与新结点链接，即

newnode

与

cur

链接；

最后，更新

_size

，并返回新结点的迭代器：

// 在pos位置前插入值为val的节点
    iterator insert(iterator pos,const T& val){
        Node* newnode =newNode(val);

        Node* cur = pos._pNode;
        Node* prev = cur->_prev;

        newnode->_prev = prev;
        prev->_next = newnode;

        newnode->_next = cur;
        cur->_prev = newnode;++_size;returniterator(newnode);}

erase

**

erase

实现时，只需要释放

pos

位置的结点，并链接剩余的结点即可：**

首先

assert

判断list是否为空；
这时我们需要记录

pos

位置的结点指针为

cur

，

pos

位置前面的结点指针为

prev

，

pos

的后一个结点指针为

next

，以方便后续链接；
然后直接链接

pos

位置的前一个结点与后一个结点，即链接

prev

与

next

即可；

最后，释放

cur

指向的结点，更新

_size

，并返回

next

：

// 删除pos位置的节点，返回该节点的下一个位置
    iterator erase(iterator pos){assert(!empty());
        Node* cur = pos._pNode;
        Node* prev = cur->_prev;
        Node* next = cur->_next;

        prev->_next = next;
        next->_prev = prev;delete cur;--_size;returniterator(next);}

push_back 与 push_front

**对于头插与尾插的实现，复用

insert

即可：**

push_front

，即在首结点的前面一个位置插入一个元素，即**在

begin()

迭代器位置插入**；

push_back

，即在尾结点的后一个位置插入一个元素，即**在

end()

位置插入**：

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

pop_back 与 pop_front

**对于头删尾删的实现，复用

erase

即可**：

pop_front

，即删除头节点，即 **

erase

删除

begin()

位置的结点** 即可；

pop_back

，删除尾结点，即 **

erase

删除

end()

前面一个结点即可，但是由于list迭代器不支持-操作，所以这里传参为

--end()

**：

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

clear

clear

用于清理list中的所有元素，**可以直接复用

erase

来实现清理**：

我们可以通过遍历迭代器的方式逐一释放结点：
令

it

的初始值为

begin()

，循环逐一

erase

删除，当

it

等于

end()

的时候终止循环，就可以实现删除所有结点并保留头节点；
另外，由于

erase

删除某节点后，会返回删除节点的下一个位置，所以**只要把返回值载赋值给

it

就实现了迭代器的向后移动**：

voidclear(){
        iterator it =begin();while(it !=end()){
            it =erase(it);//erase返回删除的结点的下一个位置的迭代器}}

swap

实现list的交换函数时，**只需要使用库

swap

交换list的属性即可，即交换

_pHead

与

_size

**：

voidswap(list<T>& l){
        std::swap(_pHead, l._pHead);
        std::swap(_size, l._size);}

源码概览

（关于反向迭代器的实现在后面会详细介绍，现在可以暂时忽略）

#include<iostream>#include<cassert>#include"my_reverse_iterator.h"namespace qqq
{template<classT>structlist_node{
        list_node<T>* _prev;
        list_node<T>* _next;
        T _date;list_node(const T& date =T())//匿名对象:_prev(nullptr),_next(nullptr),_date(date){}};template<classT,classRef,classPtr>struct__list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;

        Node* _pNode;__list_iterator(Node* pNode =nullptr):_pNode(pNode){}__list_iterator(const self& it){
            _pNode = it._pNode;}

        Ref operator*(){return _pNode->_date;}
        Ptr operator->(){return&(_pNode->_date);}

        self&operator++(){
            _pNode = _pNode->_next;return*this;}
        self operator++(int){
            self temp(*this);
            _pNode = _pNode->_next;return temp;}
        self&operator--(){
            _pNode = _pNode->_prev;return*this;}
        self operator--(int){
            self temp(*this);
            _pNode = _pNode->_prev;return temp;}booloperator==(const self& it){return _pNode == it._pNode;}booloperator!=(const self& it){return _pNode != it._pNode;}};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;typedef ReverseIterator<iterator, T&, T*> reverse_iterator;typedef ReverseIterator<const_iterator,const T&,const T*> const_reverse_iterator;public:/ constructor and destructor voidinit_empty_list(){            
            _pHead =newNode();
            _pHead->_prev = _pHead;
            _pHead->_next = _pHead;

            _size =0;}list(){init_empty_list();}list(int n,const T& value =T()){init_empty_list();while(n--){push_back(value);}}template<classIterator>list(Iterator first, Iterator last){init_empty_list();while(first != last){push_back(*first);++first;}}list(const list<T>& l){init_empty_list();for(auto el : l){push_back(el);}}
        list<T>&operator=(const list<T>& l)//list& operator=(const list l) 对于赋值重载，这样也可{
            list<T>temp(l);swap(temp);return*this;}~list(){clear();delete _pHead;}// List Iterator///
    
        iterator begin(){returniterator(_pHead->_next);}
        iterator end(){returniterator(_pHead);}
        const_iterator begin()const{returnconst_iterator(_pHead->_next);}
        const_iterator end()const{returnconst_iterator(_pHead);}
        reverse_iterator rbegin(){returnreverse_iterator(end());}
        reverse_iterator rend(){returnreverse_iterator(begin());}/List Capacity//
        size_t size()const{return _size;}boolempty()const{if(_size ==0)returntrue;elsereturnfalse;}///List Access///
        T&front(){return _pHead->_next->_date;}const T&front()const{return _pHead->_next->_date;}
        T&back(){return _pHead->_prev->_date;}const T&back()const{return _pHead->_prev->_date;}List Modify//voidpush_back(const T& val){insert(end(), val);}voidpop_back(){erase(--end());}voidpush_front(const T& val){insert(begin(), val);}voidpop_front(){erase(begin());}// 在pos位置前插入值为val的节点
        iterator insert(iterator pos,const T& val){
            Node* newnode =newNode(val);

            Node* cur = pos._pNode;
            Node* prev = cur->_prev;

            newnode->_prev = prev;
            prev->_next = newnode;

            newnode->_next = cur;
            cur->_prev = newnode;++_size;returniterator(newnode);}// 删除pos位置的节点，返回该节点的下一个位置
        iterator erase(iterator pos){assert(!empty());
            Node* cur = pos._pNode;
            Node* prev = cur->_prev;
            Node* next = cur->_next;

            prev->_next = next;
            next->_prev = prev;delete cur;--_size;returniterator(next);}voidclear(){
            iterator it =begin();while(it !=end()){
                it =erase(it);//erase返回删除的结点的下一个位置的迭代器}}voidswap(list<T>& l){
            std::swap(_pHead, l._pHead);
            std::swap(_size, l._size);}private:
        Node* _pHead;
        size_t _size;};};

总结

到此，关于list的模拟实现就到此结束了
模拟实现容器并不是为了造一个更好的轮子，而是为了更好的理解与使用容器

如果大家认为我对某一部分没有介绍清楚或者某一部分出了问题，欢迎大家在评论区提出

如果本文对你有帮助，希望一键三连哦

希望与大家共同进步哦