大家好，很高兴又和大家见面了！接下来我将模拟实现list
let's go!
前言
list是C++中STL库里面实现的一个双向循环链表
不同于在c语言中的链表实现，c++中的list通过封装面向对象编程，使得代码更加便捷，使用更加方便。
一、list实现接口概略
size、swap、begin、end、insert、
push_back、push_front、
erase、pop_back、pop_front、
构造函数、拷贝构造函数、析构函数
operator=、clear、
二、大体框架
#include <iostream>
#include <assert.h>
namespace zcy
{
template<class T>
struct list_node
{
};
template<class T>
class list
{
typedef list_node<T> Node;
public:
list()
{
}
private:
Node* _head;
size_t _size;
};
}我们通过list_node这个类来维护节点信息，通过list来维护这些节点的增删查改
在list中我们需要维护一个_head指针这个来帮助我们的查找，但是_head里面不去存储值
_size去记录有效节点的个数
我们还要去实现一下我们list_node：
struct list_node
{
list_node<T>* _prev;
list_node<T>* _next;
T _val;
list_node(const T& val = T())
: _prev(nullptr)
, _next(nullptr)
, _val(val)
{}
};我们去实现两个指针，一个指向该节点的前方，一个指向该节点的后方
还有一个_val去维护该节点里面的值
其中实现了一个默认构造函数
给了一个缺省值：T()
这个东西我在前面的文章中有提到，我这里又提一下
由于我们不知道T到底是什么类型，我们给初始值怎么给呢？我们就给它的一个匿名对象（调用构造函数）
但是对于内置类型可以吗？
是可以的，因为内置类型在c++中被升级成了类，这样就可以去方便我们实现这个了
三、iterator迭代器的实现
对于iterator来讲，我们需要通过它来遍历链表，通过它来访问数据，但是我们的链表中由于数据不是连续的，我们就无法找到一个对应适合的指针去作为我们的迭代器。
我们的迭代器还要实现++ 、--、*之类的操作所以我们就需要通过一个类来实现这个迭代器了
template<class T>
struct __list_iterator
{
typedef list_node<T> Node;
Node* _node;//维护一个节点
__list_iterator(Node* node)
: _node(node)
{}
};我们通过这么一个类，在里面对对应节点指针进行操作，然后重载运算符，就可以实现迭代器的功能。
我们在其中要实现这么几个功能：
前置++，后置++，前置--，后置--
*，->
!= 、==
我们再思考一下？对于++，--这些在const类型的迭代器中也是可以进行的，只是将迭代器移动到其他节点而已，但是*和->我们是在const类型的迭代器中是不可以进行修改的，所以我们为了能够让const类型的迭代器可以使用这个类，我们就得加上其他的模版参数
对于普通类型的迭代器，在->中返回的是T*，对于const类型的迭代器，我们返回的是const T*
对于普通类型的迭代器，在*中返回的是T&，对于const类型的迭代器，我们返回的是const T&
我们只需要再来两个模版参数Ref和Ptr去接收即可：
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef __list_iterator<T, Ref, Ptr> self;
typedef list_node<T> Node;
Node* _node;//维护一个节点
__list_iterator(Node* node)
: _node(node)
{}
}3.1.operator*、operator->实现
Ref operator*()
{
return _node->_val;
}
Ptr operator->()
{
return &(_node->_val);//如果T是结构体呢？
//那么我们就得将对应的T val的地址返回去
//便于直接访问其中内容
}对于第一个*比较好理解，我们直接将对应的值返回去即可。
但是对于第二个->不太好理解，我们为什么要返回对应节点的_val的地址呢？
因为我们对应T是什么类型并不知道，如果T是一个结构体这样的自定义类型，我们就会遇到去访问这个结构体里面的内容。而不是单单拿到一个结构体类型。
通过返回的地址我们就可以去->拿取其中内容了。
我们使用的时候发现我们难道通过一个->拿到对应的地址，要访问内容我们还有用一个->去访问吗？
那样不就成了->->?
其实并不需要，因为需要可读性，编译器会帮助我们省略一个->
3.2.++、--实现
self& operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
self tmp = new self(_node);
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)
{
self tmp = new self(_node);
_node = _node->_prev;
return tmp;
}这里的self我在前面有typedef重命名，本质为:__list_iterator<T, Ref, Ptr>
对于++和--，实现还是比较简单，只需要让对应的指针向后或者向前去走动即可
3.3.!= 、==实现
bool operator!=(const self& t) const
{
return _node != t._node;
}
bool operator==(const self& t) const
{
return _node == t._node;
}我们每个节点所对应的地址都是不同的，我们只用比较一下节点的地址即可
实现不难，大家可以好好看看代码，记得在后面加上const，不然会出现错误，因为很可能会出现和const类型的迭代器去比较！
四、list接口实现
4.1.迭代器
template<class T>
class list
{
typedef list_node<T> Node;
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
public:
list()
{
}
private:
Node* _head;
size_t _size;
};我们重命名类型，形成迭代器iterator，现在iterator就是结构体类型了
4.2.构造函数
void empty_init()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
_size = 0;
}
list()
{
empty_init();
}由于后面还会使用empty_init函数，我将它实现在外面
通过创建节点，然后让节点指向自己，形成循环链表，再让_size = 0；就初始化整个链表了
4.3.size函数
size_t size()
{
return _size;
}我们有对应的_size参数去记录，直接返回这个_size即可，实现很简单
4.4.swap函数
swap函数可以交换两个类的信息
void swap(list<T>& t)
{
std::swap(t._head, _head);
std::swap(t._size, _size);
}
这个的话，也很简单，我们调用一下库里面的swap交换函数，交换一下对应的_head和_size就交换完了两个类的信息。
4.5.begin、end函数
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;//末尾节点的下一个节点
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}由于我的_head是一个无效的值，我们_head的下一个位置才是begin有效节点的开始
那么又由于是一个双向循环链表，这里的_head可以理解为最后一个有效节点的下一个位置。
我们就可以让end()去指向_head了。
4.6.insert函数
iterator insert(iterator pos, const T& x)
{
//在pos位置插入x
Node* tmp = new Node(x);
Node* cur = pos._node;//pos是一个结构
tmp->_next = cur;
tmp->_prev = cur->_prev;
cur->_prev->_next = tmp;
cur->_prev = tmp;
_size++;
return tmp;
}我们的插入函数是在pos指针指向的位置进行插入，插入值为x的元素
首先就需要一个新的节点去放置该元素，所以我们就一来先new Node(x)去创建了这么一个节点
现在就是需要将节点链接起来。
对于新节点的链接大家可以照我的思路来就避免出现错误了！
首先，先处理新节点的前后指针，将新节点链接到当前指针指向节点的前一个位置
然后，再处理原来指针指向节点cur的链接关系，先让cur的前置节点指向新节点，再修改cur的前置节点为新节点。
这样我们就将这几条链接不出错的整好了！
我们插入完后一定要返回插入节点的地址，以免出现迭代器失效。
4.7.push_back、push_front函数
我们有了insert函数后，这两个函数就简单了
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
我们去附用前面的代码即可。
4.8.erase函数
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* next = cur->_next;
Node* prev = cur->_prev;
prev->_next = next;
next->_prev = prev;
delete cur;
_size--;
return next;
}对于erase函数首先就得判断一下删除节点的正确与否，避免出现问题
现在就是删除的逻辑了
我们将要删除的节点用cur标记
首先就是需要将cur前后节点先链接起来
cur的前置节点的下一个节点就可以先指向cur的后置节点
cur的后置节点的前一个节点就可以指向cur的前置节点
这样就将cur的前后节点链接起来，后面就是删除cur节点，并--_size
最后需要返回删除节点的下一个节点的地址，避免出现迭代器失效的问题！
4.9.pop_back、pop_front函数
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}有了erase函数后，这里就可以直接附用erase
4.10.拷贝构造函数
list(const list<T>& t)
{
//拷贝构造函数
empty_init();
for (auto e : t)
{
push_back(e);
}
}拷贝构造函数，我们先将自己给初始化一下，然后通过push_back函数将数据拷贝过来就行。
这里实现也是全部利用了前面的代码
也避免了这里的复杂操作，一举多得
4.11.operator=函数
list<T>& operator=(const list<T> t)
{
swap(t);
return *this;
}我们这里还是使用的现代写法，我们通过传值调用，传入的时候就创建出来临时变量t
通过临时变量将原来的数据进行交换，返回自己。
出了函数后，就使得对应的临时变量带着自己的那份数据销毁掉了。！
4.12.clear函数
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
_size = 0;
}clear清空里面的数据，通过迭代器，挨个进行删除，最后将_size置为0.
这样我们就可以清空数据
4.13.析构函数
~list()
{
clear();
delete _head;
_head = nullptr;
}析构函数，首先就需要清空数据，我们就可以直接附用clear函数了，最后将_head指针进行析构即可，置空即可。
总结
很高兴大家对我的支持，这部分的list最主要的还是迭代器那里，跟之前的几个容器并不相同，由于其数据结构的不同，我们必须使用类来封装它，大家要仔细看看！
多多点赞 + 收藏 + 关注！谢谢大家