本文我们模拟实现STL中的list，为了模拟实现list，实际上我们需要实现三个类，分别为：_list_node , _list_iterator , list。
我们先看一下这三个类的基本组成，主要是看看每个类中包含的变量有什么：
namespace CYF
{
//模拟实现list当中的结点类
template<class T>
struct _list_node
{
//成员变量
T _val; //数据
_list_node<T>* _prev; //prev指针
_list_node<T>* _next; //next指针
};
//模拟实现list迭代器
//T表示结点内数据类型，Ref表示引用类型，Ptr表示指针类型
template<class T, class Ref, class Ptr>
struct _list_iterator
{
typedef _list_node<T> node;
typedef _list_iterator<T, Ref, Ptr> self;//self就是当前迭代器对象的类型
//成员变量
node* _pnode; //一个指向结点的指针
};
//模拟实现list
template<class T>
class list
{
public:
typedef _list_node<T> node;
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
private:
node* _head; //指向链表头结点的指针
};
}节点类的模拟实现
我们在上篇文章中讲过list的底层就是一个带头双向循环链表。所以我们就要先实现一个节点类，这个结点中要存储的信息有数据，前一个结点的地址和后一个结点的地址，也就是list_node中的三个成员变量。
而节点类实现的目的就是根据构造函数构造出来一个一个结点即可，构造出来的结点数据域存储传过来的数据，而两个指针都置为空即可：
//模拟实现list当中的结点类
template<class T>
struct _list_node
{
//成员函数
_list_node(const T& val = T())//构造函数
:_val(val)
,_next(nullptr)
,_prev(nullptr)
{}
//成员变量
T _val; //数据
_list_node<T>* _prev; //prev指针
_list_node<T>* _next; //next指针
};迭代器类的模拟实现
list迭代器类存在的意义
我们之前模拟实现过string和vector，他们俩都没说要实现一个迭代器类，为什么现在实现list的时候要实现一个迭代器类呢？
因为string和vector对象的数据都存储在一块连续的内存空间，我们可以通过指针进行++，--以及解引用等操作，就可以对相应的数据进行一系列操作，因此string和vector当中的指针就是原生指针。
但是对于list来说，其各个结点在内存中的位置是随机的，不是连续的，也就导致我们不能通过结点指针的++，--以及解引用对结点的数据进行操作。
而我们之前也说过，迭代器的意义就是让使用者可以不用关心容器的底层实现，可以用统一的方式对容器内的数据进行访问。
那么既然list的结点指针不能直接用于定义迭代器，那么我们可以对这个结点指针进行封装，对结点的各个运算符进行重载。例如，我们将++操作operator为p=p->_next;类似的，即可使用++，--，解引用等和vector这种容器一样的操作方法操作list的迭代器了。
对迭代器类模板参数的说明
我们首先要介绍一下，迭代器模板的三个参数：
template<class T,class Ref,class Ptr>而在list类中，我们也有类似的操作，我们typedef了两个迭代器类型，普通迭代器和const迭代器：
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;实际上定义这三个模板参数就是为了区分普通迭代器和const迭代器。
迭代器类的模板参数中的Ref和Ptr分别表示的就是数据的引用和指向数据的指针。
我们使用普通迭代器时，就会实例化出一个普通迭代器对象，使用const迭代器时，就会实例化出一个const迭代器对象，有关操作的参数和返回值都会加上const。
而我们还在迭代器类中typedef出来个self：
typedef _list_iterator<T, Ref, Ptr> self;//self就是当前迭代器对象的类型
而这个self就是当前迭代器对象的类型。
实现各类函数及运算符重载
构造函数
迭代器类中就一个成员变量——结点指针，我们只初始化一个结点指针就行：
_list_iterator(node* pnode)
:_pnode(pnode)
{}operator++(前置 && 后置)
++的作用就是让结点指针指向下一个结点，前置++就返回++后的结点，后置++就还返回原先的结点，代码如下：
self operator++()//前置
{
_pnode = _pnode->_next;
return *this;
}
self operator++(int)//后置
{
self tmp(*this);
_pnode = _pnode->_next;
return tmp;
}
//返回值类型self就是迭代器类型operator--(前置 && 后置)
--的作用就是让结点指针指向前一个结点，前置--就返回--后的结点，后置--就还返回原先的结点，代码如下：
self operator--()//前置
{
_pnode = _pnode->_prev;
return *this;
}
self operator--(int)//后置
{
self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}operator==
我们看两个list对象是否是同一个只需要看他们的头指针是否为同一个即可：
bool operator==(const self& s) const
{
return _pnode == s._pnode;
}operator!=
我们看两个list对象是否不是同一个只需要看他们的头指针是否不为同一个即可：
bool operator!=(const self& s) const
{
return _pnode != s._pnode;
}operator* (就是对*的重载)
我们使用迭代器的时候，就像使用指针一样使用，所以我们在使用*的时候是为了得到这个位置的数据，那么我们直接返回结点的数据即可：
//返回当前结点指针所指向的数据，这里的返回值是引用，因为可能会修改
Ref operator*()
{
return _pnode->_val;
}operator->
某些情况下，我们会用到->运算符：
当list对象中存储的不是内置类型，而是自定义类型时，例如日期类，当我们拿到一个位置的迭代器时，我们可能会使用->运算符访问日期类的某个成员：
list<Date> lt;
Date d(2024,6,5);
lt.push_back(d);
list<Date>::iterator it = d.begin();
cout<<it._day<<endl;提示：我们使用it->_day这种访问方式的时候，需要将Date类的成员变量设置为共有。
我们实现的时候返回结点中存储数据的地址即可：
//当list内存储的是自定义类型时候就需要使用->,我们直接返回结点中存储数据的地址即可
Ptr operator->()
{
return &_pnode->_val;//对于类似于Date这样的类这里本来是有两个->的，
//为了增强程序的可读性，省略了一个->
}我们这里要注意一点：拿Date类举例，我们想得到一个Date对象的一个成员变量_day。我们应该是有两个箭头，即：先it->去调用Date的operator->返回Date*的指针，然后再用返回的Date*的指针->去访问Date的成员变量_day。
但是这里为了增加程序的可读性，我们省略了一个箭头。
list的模拟实现
构造函数
构造时，我们直接申请一个头节点，并让该头节点_prev,_next指针都指向自己即可：
//默认成员函数
list()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}拷贝构造函数
我们先申请一个头节点，头节点的_prev,_next都指向自己，然后遍历要拷贝的list对象，将所有元素push_back。
list(const list<T>& lt)
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
for (const auto& e : lt)
{
push_back(e);
}
}赋值运算符重载函数
法一（传统写法）：
用clear()将容器清空，然后通过遍历将被赋值的list对象中的元素push_back。
list<T>& operator=(const list<T>& lt)
{
if (this != <)
{
clear();
const_iterator it = lt.begin();
//while (it != lt.end())
//{
// push_back(it._pnode->_val);
// it++;
//}
for(const auto& e : lt)//用范围for比较简洁
{
push_back(e);
}
}
return *this;
}法二（现代写法）：
与之前的string和vector现代写法相似，故意不使用引用传参接收参数，通过编译器自动调用list的拷贝构造函数构造出一个局部的list对象，然后使用swap函数交换两个list对象即可：
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}析构函数
先调用clear函数清空容器内数据，然后将头节点释放，置空：
~list()
{
clear();
delete _head;
_head = nullptr;
}begin() && end()
begin()函数返回第一个有效数据的迭代器，end()函数返回最后一个有效数据下一个的迭代器。
我们仔细想想，list是一个带头双向循环的链表，第一个有效数据就是_head->_next的迭代器，而最后一个有效数据下一个的迭代器就是_head的迭代器，因为最后一个结点的_next就是_head。
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator begin() const
{
return iterator(_head->_next);
}
const_iterator end() const
{
return iterator(_head);
}front() && back()
这两个函数分别用于获取第一个有效数据和最后一个有效数据。因此，我们直接返回第一个和最后一个有效数据的引用即可：
//访问容器相关函数
T& front()
{
return _head->_next->_val;
//或者这样写：return *begin();//返回第一个有效数据的引用
}
T& back()
{
return _head->_prev->_val;
//或者这样写：return *(--end());//返回最后一个有效数据的引用
}
const T& front() const
{
return _head->_next->_val;
}
const T& back() const
{
return _head->_prev->_val;
}insert
我们先创建一个新结点，然后建立新结点与前后结点的关系即可：
void insert(iterator pos, const T& x)
{
assert(pos._pnode);//检测pos的合法性
node* cur = pos->_pnode;//迭代器pos处的指针
node* prev = cur->_prev;//迭代器前一个位置的结点指针
node* newnode = new node(x);//创建的新结点指针
//构建新结点newnode和prev和cur结点的关系
newnode->_next = cur;
newnode->_prev = prev;
cur->_prev = newnode;
prev->_next = newnode;
}erase
我们需要先通过迭代器找到要删除的结点，然后记录要删除的结点的前后结点，然后释放这个该删除的结点，之后建立前后结点的双向关系：
iterator erase(iterator pos)
{
assert(pos._pnode);//检查pos的合法性
assert(pos != end());//删除的不能是头结点
node* cur = pos._pnode;
node* prev = cur->_prev;
node* next = cur->_next;
delete cur;
prev->_next = next;
next->_prev = prev;
return iterator(next);
}push_back
法一、我们可以创建并赋值新结点，然后记录_head->_next，最后录入新结点和_head->_next，_head的双向关系
法二、我们可以复用insert()函数
void push_back(const T& x)//法一
{
node* last = _head->_prev;
node* newnode = new node;
newnode->_val = x;
last->_next = newnode;
newnode->_prev = last;
newnode->_next = _head;
_head->_prev = newnode;
}
void push_back(const T& x)//法二
{
isnert(end(), x);
}pop_back && push_front && pop_front
我们都直接复用insert()和erase()函数：
void pop_back()
{
//注意end()是最后一个结点的下一个位置，我们这里要删除的是最后一个结点
//所以我们这里要--
erase(--end());
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}size
由于链表的每个元素在内存中的位置是随机的，所以我们只能通过遍历的方式统计有效数据的个数：
size_t size() const
{
size_t sz = 0;
const_iterator it = begin();
while (it != end())
{
sz++;
it++;
}
return sz;
}resize
resize函数我们需要分两种情况来讨论：
1.若当前容器的size小于所给n，则尾插结点，直到size等于n。
2.若当前容器的size大于所给n，只保留前n个有效数据。
我们这里要注意：当我们实现resize函数的时候，不能通过size函数获取当前list对象中的有效数据个数，因为当我们调用size函数后就遍历一遍容器了，若size>n，那么还要遍历容器，找到第n个有效结点并释放后面的结点。
所以我们要设置一个变量len，用于记录当前所遍历的数据个数，然后开始遍历数组，在遍历过程中：
1.当len大于或等于n时遍历结束，此时说明该结点后的结点都应该被释放，将之后的结点释放即可
2.当容器遍历完时遍历结束，说明此时容器容器中的有效数据小于n个，则需要尾插结点，直到容器中的有效数据个数为n。
void resize(size_t n, const T& val = T())
{
iterator i = begin();//获取第一个有效数据的迭代器
size_t len = 0;//记录当前所遍历的数据个数
while (i != end() && len < n)//遍历
{
i++;
len++;
}
if (len == n)//说明list中数据个数大于等于n，删除多出的数据
{
while (i != end())
{
//erase(i);
//i++;
//↑上面两行写的是错误的，迭代器失效，不要犯错误
i = erase(i);//每次删除后要接收下一个数据的迭代器
}
}
else//说明list中数据个数小于n，要尾插若干个数据为val的结点，直到容器中结点为n个
{
while (len != n)
{
push_back(val);
len++;
}
}
}clear
通过遍历的方式逐个删除结点，只保留头节点即可：
void clear()
{
iterator it = begin();
while (it != end())//去除其他结点，只保留头节点
{
it = erase(it);
}
}empty
判断容器是否为空，我们直接判断begin()和end()返回的迭代器是否为同一个位置即可：
bool empty() const
{
return begin() == end();
}swap
list容器中实际上就存了一个_head指针，我们将两个容器中的头指针交换位置即可：
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
}完整代码
最后贴上全部代码：
#pragma once
#include<iostream>
#include<cassert>
namespace CYF
{
//模拟实现list当中的结点类
template<class T>
struct _list_node
{
//成员函数
_list_node(const T& val = T())//构造函数
:_val(val)
,_next(nullptr)
,_prev(nullptr)
{}
//成员变量
T _val; //数据域
_list_node<T>* _next; //后继指针
_list_node<T>* _prev; //前驱指针
};
//模拟实现list迭代器
//T表示结点内数据类型，Ref表示引用类型，Ptr表示指针类型
template<class T, class Ref, class Ptr>
struct _list_iterator
{
typedef _list_node<T> node;
typedef _list_iterator<T, Ref, Ptr> self;//self就是当前迭代器对象的类型
//构造函数
_list_iterator(node* pnode)
:_pnode(pnode)
{}
//各种运算符重载函数
self operator++()
{
_pnode = _pnode->_next;
return *this;
}
self operator--()
{
_pnode = _pnode->_prev;
return *this;
}
self operator++(int)
{
self tmp(*this);
_pnode = _pnode->_next;
return tmp;
}
self operator--(int)
{
self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}
bool operator==(const self& s) const
{
return _pnode == s._pnode;
}
bool operator!=(const self& s) const
{
return _pnode != s._pnode;
}
//返回当前结点指针所指向的数据，这里的返回值是引用，因为可能会修改
Ref operator*()
{
return _pnode->_val;
}
//当list内存储的是自定义类型时候就需要使用->,我们直接返回结点中存储数据的地址即可
Ptr operator->()
{
return &_pnode->_val;//这里本来是有两个->的，为了增强程序的可读性，省略了一个->
}
//成员变量
node* _pnode; //一个指向结点的指针
};
//模拟实现list
template<class T>
class list
{
public:
typedef _list_node<T> node;
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
//默认成员函数
list()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
list(const list<T>& lt)
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
for (const auto& e : lt)
{
push_back(e);
}
}
list<T>& operator=(const list<T>& lt)//operator=传统写法
{
if (this != <)
{
clear();
const_iterator it = lt.begin();
while (it != lt.end())
{
push_back(it._pnode->_val);
it++;
}
}
return *this;
}
list<T>& operator=(list<T> lt)//operator=现代写法
{
swap(lt);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
//迭代器相关函数
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator begin() const
{
return iterator(_head->_next);
}
const_iterator end() const
{
return iterator(_head);
}
//访问容器相关函数
T& front()
{
return _head->_next->_val;
//或者这样写：return *begin();//返回第一个有效数据的引用
}
T& back()
{
return _head->_prev->_val;
//或者这样写：return *(--end());//返回最后一个有效数据的引用
}
const T& front() const
{
return _head->_next->_val;
}
const T& back() const
{
return _head->_prev->_val;
}
//插入、删除函数
void insert(iterator pos, const T& x)
{
assert(pos._pnode);//检测pos的合法性
node* cur = pos->_pnode;//迭代器pos处的指针
node* prev = cur->_prev;//迭代器前一个位置的结点指针
node* newnode = new node(x);//创建的新结点指针
//构建新结点和prev和cur结点的关系
newnode->_next = cur;
newnode->_prev = prev;
cur->_prev = newnode;
prev->_next = newnode;
}
iterator erase(iterator pos)
{
assert(pos._pnode);//检查pos的合法性
assert(pos != end());//删除的不能是头结点
node* cur = pos._pnode;
node* prev = cur->_prev;
node* next = cur->_next;
delete cur;
prev->_next = next;
next->_prev = prev;
return iterator(next);
}
//void push_back(const T& x)
//{
// node* last = _head->_prev;
// node* newnode = new node;
// newnode->_val = x;
// last->_next = newnode;
// newnode->_prev = last;
// newnode->_next = _head;
// _head->_prev = newnode;
//}
void push_back(const T& x)
{
isnert(end(), x);
}
void pop_back()
{
//注意end()是最后一个结点的下一个位置，我们这里要删除的是最后一个结点
//所以我们这里要--
erase(--end());
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}
//其他函数
size_t size() const
{
size_t sz = 0;
const_iterator it = begin();
while (it != end())
{
sz++;
it++;
}
return sz;
}
void resize(size_t n, const T& val = T())
{
iterator i = begin();//获取第一个有效数据的迭代器
size_t len = 0;//记录当前所遍历的数据个数
while (i != end() && len < n)//遍历
{
i++;
len++;
}
if (len == n)//说明list中数据个数大于等于n，删除多出的数据
{
while (i != end())
{
//erase(i);
//i++;
//↑上面两行写的是错误的，迭代器失效，不要犯错误
i = erase(i);//每次删除后要接收下一个数据的迭代器
}
}
else//说明list中数据个数小于n，要尾插若干个数据为val的结点，直到容器中结点为n个
{
while (len != n)
{
push_back(val);
len++;
}
}
}
void clear()
{
iterator it = begin();
while (it != end())//去除其他结点，只保留头节点
{
it = erase(it);
}
}
bool empty() const
{
return begin() == end();
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
}
private:
node* _head; //指向链表头结点的指针
};
}