【C++】list模拟实现

🔥个人主页： Forcible Bug Maker
🔥专栏： STL || C++

目录

前言

本篇博客主要内容：STL库中list的模拟实现。

实现

list

就和之前的

vector

和

string

大不相同了，

vector

和

string

的底层结构是顺序表，而

list

的底层是链表，学习

list

的底层实现，了解顺序表和链表的区别是至关重要的，如果对这部分内容不太了解，可以参考这篇博客：初阶数据结构-顺序表和链表（C语言）
本篇的

list

实现中，迭代器的实现是重难点，它不再和以前的实现一样，只是单纯的原生指针，而是一个迭代器模板类。希望大家在了解

list

迭代器的实现之后，能对STL库中容器的迭代器有着更深的认识。

🌈list需要实现的结构和接口函数

list建议在vector的实现基础上进行，同样涉及到了模板的使用，而且更为复杂。本篇list的模拟实现并不会将接口函数的声明和定义分离，函数体统一实现在模板类内部。我们在定义链表list之前需要两个结构体内容，一个是结点

Node

，另一个是迭代器

ListIterator

。
先来看看需要实现的接口函数：

#pragmaonce#include<iostream>#include<cassert>usingnamespace std;namespace ForcibleBugMaker
{// List的结点类template<classT>structListNode{ListNode(const T& val =T());
        ListNode<T>* _pPre;
        ListNode<T>* _pNext;
        T _val;};//List的迭代器类template<classT,classRef,classPtr>classListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;public:ListIterator(PNode pNode =nullptr);ListIterator(const Self& l);
        Ref operator*();
        Ptr operator->();
        Self&operator++();
        Self operator++(int);
        Self&operator--();
        Self&operator--(int);booloperator!=(const Self& l);booloperator==(const Self& l);
        PNode _pNode;};//list类template<classT>classlist{// typedef结点为Node// 不然每次类型都写ListNode<T>会比较麻烦typedef ListNode<T> Node;typedef Node* PNode;public:// 下面两个typedef使编译器分别构造了两个类型的迭代器// iterator和const_iteratortypedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T,const T&,const T*> const_iterator;public:// List的默认成员函数list();list(int n,const T& value =T());template<classIterator>list(Iterator first, Iterator last);list(const list<T>& l);
        list<T>&operator=(list<T> l);~list();// List Iterator
        iterator begin();
        iterator end();
        const_iterator cbegin();
        const_iterator cend();// List Capacity
        size_t size()const;boolempty()const;// List Access
        T&front();const T&front()const;
        T&back();const T&back()const;// List Modifyvoidpush_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);// 删除pos位置的节点，返回该节点的下一个位置
        iterator erase(iterator pos);voidclear();voidswap(list<T>& l);private:
        PNode _pHead;};};

整个list可以被分为三个部分，List结点类（用于构造List类的结点），List的迭代器类（用于构造和操作List类的迭代器）以及List类（维护list链表，支持对链表的一系列操作）。
接下来我们将它们一一实现：

🔥List结点类

此结点类是一个模板类，模板参数T表示结点的数据类型。主要是实现其构造函数，便于后面List类中结点的创建。

// List的节点类template<classT>structListNode{ListNode(const T& val =T()):_pPre(nullptr),_pNext(nullptr),_val(val){}
    ListNode<T>* _pPre;
    ListNode<T>* _pNext;
    T _val;};

构造函数部分初始化变量使用了初始化列表，并在参数列表中提供了了缺省值，同时实现了无参和传参的结点构造。

🔥List迭代器类

此迭代器类同样是一个模板类，包含三个模板参数，T（表示迭代器指向元素的数据类型），Ref（类型为

T&

或

const T&

，表示

operator*()

操作符重载的返回值类型），Ptr（类型为

T*

或

const T*

，表示

operator->()

操作符重载的返回值类型）。

typedef类型说明：PNode（表示一个结点的指针，简化书写），Self（表示此迭代器类型

ListIterator<T, Ref, Ptr>

的别名，简化书写）

下面来看看迭代器具体的代码实现，同时理解一下这些模板参数的用途。

//List的迭代器类template<classT,classRef,classPtr>classListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;public:// 默认成员函数，初始化结点指针的指向ListIterator(PNode pNode =nullptr):_pNode(pNode){}ListIterator(const Self& l):_pNode(l._pNode){}// 解引用访问T类型的对象
    Ref operator*(){return _pNode->_val;}// 箭头实现访问T类型对象中的成员// 此处为C++特定语法，下面会展开讲
    Ptr operator->(){return&(_pNode->_val);}// 让迭代器指向下一结点
    Self&operator++(){// 虽然外部重载的是++// 但内部已经是链表的移动方式
        _pNode = _pNode->_pNext;return*this;}
    Self operator++(int){
        Self tmp(*this);
        _pNode = _pNode->_pNext;return tmp;}// 让迭代器指向上一结点
    Self&operator--(){
        _pNode = _pNode->_pPre;return*this;}
    Self&operator--(int){
        Self tmp(*this);
        _pNode = _pNode->_pPre;return tmp;}// 判断迭代器是否相等booloperator!=(const Self& l){return _pNode != l._pNode;}booloperator==(const Self& l){return _pNode == l._pNode;}// 唯一的成员变量，一个结点的指针
    PNode _pNode;};

我们可以单独将operator->()重载拿出来看：

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

此接口函数返回值的类型为结点元素的地址，当你使用这样的重载访问元素成员的时候，本质上是这样的（

it.operator->()->_a1

）或这样的（

it->->_a1

）。很明显，这样的写法看起来太不美观，用起来也太不舒适了。所以，C++增加了语法规定，使编译器不支持

it->->_a1

这种写法，而单独支持

it->_a1

这种。提高了C++使用的方便性和代码的可读性。

🔥List类

进入到咱们的重头戏，List类，它也是一个模板类，包含一个模板参数T（表示List类的数据类型）。其中也是只有一个成员变量，指向链表头节点的指针

_pHead

。List类的链表为带头双向循环链表，可以很轻易的通过头节点访问到链表头和链表尾。

typedef类型说明：Node（链表的结点类型

ListNode<T>

的别名），PNode（指向Node类型元素的指针），iterator（迭代器类型

ListIterator<T, T&, T*>

的别名），const_iterator（迭代器类型

ListIterator<T, const T&, const T*>

的别名）。

接下来我们逐一实现其成员函数：

默认成员函数

主要还是那几样，构造函数，拷贝构造，赋值运算符重载以及析构函数。

// List的构造函数list(){// 创建头节点
    _pHead =new Node;
    _pHead->_pNext = _pHead;
    _pHead->_pPre = _pHead;}list(int n,const T& value =T()){
    _pHead =new Node;
    _pHead->_pNext = _pHead;
    _pHead->_pPre = _pHead;for(int i =0; i < n; i++){// push_back，链表尾插，后面会实现push_back(value);}}// 迭代器区间构造template<classIterator>list(Iterator first, Iterator last){
    _pHead =new Node;
    _pHead->_pNext = _pHead;
    _pHead->_pPre = _pHead;// 往链表中依次插入迭代器区间中的结点while(first != last){push_back(*first);++first;}}// 拷贝构造list(const list<T>& l){
    _pHead =new Node;
    _pHead->_pNext = _pHead;
    _pHead->_pPre = _pHead;
    PNode pcur =  l._pHead->_pNext;while(pcur != l._pHead){push_back(pcur->_val);
        pcur = pcur->_pNext;}}// 赋值运算符重载
list<T>&operator=(list<T> l){// swap交换链表函数，后面会实现swap(l);return*this;}// 析构函数，释放空间~list(){// clear，清空list对象结点，后面会实现clear();delete _pHead;
    _pHead =nullptr;}

有链表和顺序表基础的话，还是没什么难度的。

Iterators迭代器获取

由于迭代器不再是原生指针，而是一个

ListIterator

迭代器类，所以并不能直接返回元素的指针，而是构造出来的迭代器对象。
如下：

// List Iterator
iterator begin(){returniterator(_pHead->_pNext);}
iterator end(){returniterator(_pHead);}
const_iterator cbegin(){returnconst_iterator(_pHead->_pNext);}
const_iterator cend(){returnconst_iterator(_pHead);}

其中，迭代器类型使用匿名对象简化书写。当我们重载了这样几个迭代器接口之后，就可以像STL库里那样顺利的获取和使用迭代器了。

容量接口

获取当前List对象所包含的元素个数（size）或者是否为空（empty）。

// List Capacity
size_t size()const{
    size_t digit =0;
    PNode pcur = _pHead->_pNext;while(pcur != _pHead){++digit;
        pcur = pcur->_pNext;}return digit;}boolempty()const{if(_pHead == _pHead->_pNext)returntrue;elsereturnfalse;}

这里的

size()

接口函数我实现的相对草率，通过遍历List对象计算元素的个数，时间复杂度

O(N)

。当然，如果你有想法，完全可以实现一个复杂度为

O(1)

的

size()

接口。

List Access元素获取

List对象中的元素获取不存在下标访问这一说，只提供了获取头元素和尾元素的接口函数。

// List Access
T&front(){assert(!empty());return _pHead->_pNext->_val;}const T&front()const{assert(!empty());return _pHead->_pNext->_val;}
T&back(){assert(!empty());return _pHead->_pPre->_val;}const T&back()const{assert(!empty());return _pHead->_pPre->_val;}

同时重载了const类型和非const类型的两种接口。

List对象修饰接口

主要包含，List对象插入删除，头插头删，尾插尾删，链表元素的清空。在list对象的修饰中，统统使用迭代器来确定修饰位置及元素，大家需要慢慢习惯迭代器修饰方式。
我们可以先来实现结点的插入和删除：

// 在pos指向元素位置前插入值为val的节点
iterator insert(iterator pos,const T& val){// 创建并初始化新结点
    PNode newnode =newNode(val);// 以下插入方式大家应该不陌生
    newnode->_pNext = pos._pNode;
    newnode->_pPre = pos._pNode->_pPre;
    pos._pNode->_pPre->_pNext = newnode;
    pos._pNode->_pPre = newnode;// 返回指向插入元素的迭代器returniterator(newnode);}// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos){// 保存被删除结点下一位置，作为返回值
    iterator tmp(pos._pNode->_pNext);
    pos._pNode->_pPre->_pNext = pos._pNode->_pNext;
    pos._pNode->_pNext->_pPre = pos._pNode->_pPre;delete pos._pNode;
    pos._pNode =nullptr;return tmp;}

头插头删，尾插尾删其实就是对以上两个接口函数的复用，如下：

// 头插voidpush_front(const T& val){insert(begin(), val);}// 头删voidpop_front(){erase(begin());}// 尾插voidpush_back(const T& val){insert(end(), val);}// 尾删voidpop_back(){erase(--end());}

List对象结点的清除，创建一个迭代器依次删除元素，同时判断是否删除到尾就可以了：

voidclear(){
    iterator it =begin();while(it !=end()){
        it =erase(it);}}

swap

交换两个List对象**只需要交换它们的头节点指针变量

_pHead

**。

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

结语

本篇博客主要讲了list的模拟实现，可以简单将其分成三部分，List结点类，List迭代器类以及List类，最终将它们集合在一起组成了我们模拟实现的list。实现的功能还是元素插入元素删除，构造和析构那几套，但list相对于vector和string已经完全抛弃了下标访问，只支持迭代器区间了，我们需要渐渐习惯迭代器的使用。
博主后续还会分享更多有趣的内容，感谢大家的支持。♥