🔥个人主页： 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_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 <class Iterator>list(Iterator first, Iterator last);list(const list<T>& l);list<T>& operator=(list<T> l);~list();// List Iteratoriterator begin();iterator end();const_iterator cbegin();const_iterator cend();// List Capacitysize_t size()const;bool empty()const;// List AccessT& front();const T& front()const;T& back();const T& back()const;// List Modifyvoid 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 Iterator
iterator 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 Capacity
size_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 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 = 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已经完全抛弃了下标访问，只支持迭代器区间了，我们需要渐渐习惯迭代器的使用。
博主后续还会分享更多有趣的内容，感谢大家的支持。♥
)
