🔥个人主页： Forcible Bug Maker

🔥专栏： STL || C++

目录

前言🌈list需要实现的结构和接口函数🔥List结点类🔥List迭代器类🔥List类==默认成员函数====Iterators迭代器获取====容量接口====List Access元素获取====List对象修饰接口====swap== 结语

前言

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

实现list就和之前的vector和string大不相同了，vector和string的底层结构是顺序表，而list的底层是链表，学习list的底层实现，了解顺序表和链表的区别是至关重要的，如果对这部分内容不太了解，可以参考这篇博客：初阶数据结构-顺序表和链表（C语言）

本篇的list实现中，迭代器的实现是重难点，它不再和以前的实现一样，只是单纯的原生指针，而是一个迭代器模板类。希望大家在了解list迭代器的实现之后，能对STL库中容器的迭代器有着更深的认识。

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

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

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

#pragma once#include<iostream>#include<cassert>using namespace std;namespace ForcibleBugMaker{ // List的结点类 template<class T> struct ListNode { ListNode(const T& val = T()); ListNode<T>* _pPre; ListNode<T>* _pNext; T _val; }; //List的迭代器类 template<class T, class Ref, class Ptr> class ListIterator { 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); bool operator!=(const Self& l); bool operator==(const Self& l); PNode _pNode; }; //list类 template<class T> class list { // typedef结点为Node // 不然每次类型都写ListNode<T>会比较麻烦 typedef ListNode<T> Node; typedef Node* PNode; public: // 下面两个typedef使编译器分别构造了两个类型的迭代器 // iterator和const_iterator typedef 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 <class Iterator> 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; bool empty()const; // List Access T& front(); const T& front()const; T& back(); const T& back()const; // List Modify void push_back(const T& val) { insert(end(), val); } void pop_back() { erase(--end()); } void push_front(const T& val) { insert(begin(), val); } void pop_front() { erase(begin()); } // 在pos位置前插入值为val的节点 iterator insert(iterator pos, const T& val); // 删除pos位置的节点，返回该节点的下一个位置 iterator erase(iterator pos); void clear(); void swap(list<T>& l); private: PNode _pHead; };};

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

接下来我们将它们一一实现：

🔥List结点类

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

// List的节点类template<class T>struct ListNode{ 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<class T, class Ref, class Ptr>class ListIterator{ 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; } // 判断迭代器是否相等 bool operator!=(const Self& l) { return _pNode != l._pNode; } bool operator==(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 <class Iterator>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 Iteratoriterator begin(){ return iterator(_pHead->_pNext);}iterator end(){ return iterator(_pHead);}const_iterator cbegin(){ return const_iterator(_pHead->_pNext);}const_iterator cend(){ return const_iterator(_pHead);}

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

容量接口

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

// List Capacitysize_t size()const{ size_t digit = 0; PNode pcur = _pHead->_pNext; while (pcur != _pHead) { ++digit; pcur = pcur->_pNext; } return digit;}bool empty()const{ if (_pHead == _pHead->_pNext)return true; else return false;}

这里的size()接口函数我实现的相对草率，通过遍历List对象计算元素的个数，时间复杂度O(N)。当然，如果你有想法，完全可以实现一个复杂度为O(1)的size()接口。

List Access元素获取

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

// List AccessT& 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 = new Node(val); // 以下插入方式大家应该不陌生 newnode->_pNext = pos._pNode; newnode->_pPre = pos._pNode->_pPre; pos._pNode->_pPre->_pNext = newnode; pos._pNode->_pPre = newnode; // 返回指向插入元素的迭代器 return iterator(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;}

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

// 头插void push_front(const T& val) { insert(begin(), val); }// 头删void pop_front() { erase(begin()); }// 尾插void push_back(const T& val) { insert(end(), val); }// 尾删void pop_back() { erase(--end()); }

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

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

swap

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

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

结语

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

博主后续还会分享更多有趣的内容，感谢大家的支持。♥