目录
1. 基本结构的实现
2. list()
3. void push_back(const T& val)
4. 非 const 迭代器
4.1 基本结构
4.2 构造函数
4.3 T& operator*()
4.4 __list_iterator& operator++()
4.5 bool operator!=(const __list_iterator& it)
4.6 T* operator->()
5. const 迭代器
6. begin() && end()
编辑
7. iterator insert(iterator pos, const T& val)
8. iterator erase(iterator pos)
9. void push_front(const T& val)
10. void pop_front()
11. void pop_back()
12. size_t size() const
13. void clear()
14. ~list()
1. 基本结构的实现
在 list 的使用部分，我们已经知道了 list 其实就是一个带头的双向循环链表 (以下简称双链表)。结合我们在 C 语言写过的双链表的实现：C语言数据结构初阶(4)----带头双向循环链表_姬如祎的博客-CSDN博客
第一步要做的就是定义出链表的节点。和 C 语言不一样的是，list 可以存储任意类型的数据，因此必须定义成模板。 老规矩为了与库中的 list 做区分，我们还是会把自己模拟实现的 list 放到一个命名空间里面。
namespace Tchey
{
template<class T>
struct ListNode
{
T _val;
ListNode<T>* _prev;
ListNode<T>* _next;
ListNode(const T& val = T())
:_val(val)
,_prev(nullptr)
,_next(nullptr)
{}
};
}在 C++ 中结构体被提升成了类，因此在定义双链表的节点的时候，我们可以写一个节点的构造函数，这样在堆上申请节点的时候，就能够直接初始化节点的 val 值啦！
OK，既然双链表的节点定义好了，list 类中的成员变量应该如何定义呢？起始很简单，list 类想要维护一个双链表只需要维护头结点的指针就可以了。因为 list 是带头的双链表，因此，list 的成员变量就是那个哨兵位的头结点的指针。
namespace Tchey
{
template<class T>
class list
{
private:
ListNode<T>* _head;
};
}2. list()
这个是 list 的无参构造函数，他的任务就是做好初始化哨兵位的头结点的工作。你还记得双向带头循环链表的初始化应该怎么做吗？看下面的图你应该就会记得了吧！
因为哨兵位的头结点是不需要存储任何有效的数据的，他的 val 值填多少都无所谓！索性就不填了，用默认的 val 就行。
list()
{
_head = new ListNode<T>;
_head->_next = _head;
_head->_prev = _head;
}3. void push_back(const T& val)
这个是双链表的尾插，双链表的尾节点，就是哨兵位的头结点的 _prev。开辟新节点，找到尾节点，做好链接工作就行啦！不知道如何链接，请看 C 语言实现的双向链表中的 push_back 函数：
C语言数据结构初阶(4)----带头双向循环链表_姬如祎的博客-CSDN博客
void push_back(const T& val)
{
ListNode<T>* newNode = new ListNode<T>(val);
ListNode<T>* tail = _head->_prev;
tail->_next = newNode;
newNode->_prev = tail;
_head->_prev = newNode;
newNode->_next = _head;
}4. 非 const 迭代器
list 的迭代器是我们遇到的第一个不是原生指针的迭代器，我们来看看他的迭代器和 vector 迭代器的差别：
对于 vector 来说，他的迭代器是 int 类型的指针 (假设vector存储 int 数据)，解引用就直接能访问到真实的数据。如果 list 也是原生指针，那只能是结构体的指针，解引用得到的就是一个结构体，无法拿到真实的数据。list 拿到数据需要通过访问结构体的 _val 成员得到。
对于 vector 来说，他的迭代器是 int 类型的指针 (假设vector存储 int 数据)，并且 vector 的存储空间是连续的。迭代器加加就能直接跳过一个整形的空间，直接指向下一个有效的数据。
list 呢，物理空间不连续，如果 list 迭代器是结构体指针，加加之后访问到的空间并一定不属于你，可能会发生内存错误。实际上 list 的迭代加加之后，应该是指向节点的下一个节点，即需要通过 _next 找到下一个节点。
综上所述，list 的迭代器不可能是原生指针，需要对节点的指针进行封装。封装时，我们需要重载 *，++，等运算符，这样才能正确实现迭代器的效果。
4.1 基本结构
我们已经知道了，list 的迭代器就是对原生的结构体指针进行封装。然后通过运算符重载实现迭代器应有的功能。那这个迭代器的成员变量当然就是一个节点的指针啦！
namespace Tchey
{
template<class T>
struct __list_iterator
{
public:
private:
ListNode<T>* _node;
};
}4.2 构造函数
在 list 类里面，有 begin()，end() 之类的函数，用来返回一个迭代器对象，那么我们实现的迭代器就需要提供构造函数，支持使用节点的指针构造出来一个迭代器对象。
__list_iterator(ListNode<T>* node)
:_node(node)
{}4.3 T& operator*()
我们都使用过迭代器遍历一个容器，知道了迭代器的解引用解释返回真实有效的数据，因此 operator 就是返回节点的 _val 值。
T& operator*()
{
return _node->_val;
}4.4 __list_iterator<T>& operator++()
对于 list 来说迭代器加加实际上就是让迭代器的成员变量 _node 指向当前节点的下一个节点。
__list_iterator<T>& operator++()
{
_node = _node->_next;
return *this;
}4.5 bool operator!=(const __list_iterator<T>& it)
这个函数就是判断两个迭代器是否是一样的嘛，判断的逻辑就是判断两个迭代成员的节点指针是否相同。不能不写 const 因为 list 中的 begin()，end() 返回的都是一个迭代器的拷贝，当我们自己定义的迭代器变量与 end() 的返回值做 != 判断时就会调用 operator!= 如果没有 const，因为 end 的返回值具有常性，是无法用非 const 的迭代器类型来接收的。
bool operator!=(__list_iterator<T>& it)
{
return _node != it._node;
}4.6 T* operator->()
为什么要重载这种解引用的方式呢？emm，如果 list 容器存储的是一个结构体类型，或者其他自定义类型，那么重载了 -> 就能较为方便拿到我们的数据！
如果我没有重载 -> 那么当我们用迭代器区访问一个存储自定义类型的 list 的时候，你就需要这么写：
struct info
{
int a;
int b;
};
int main()
{
info in = { 10,20 };
list<info> lt;
lt.push_back(in);
auto it = lt.begin();
while (it != lt.end())
{
cout << (*it).a << " " << (*it).b << endl;
it++;
}
return 0;
}但是如果你重载了 -> 这个运算符，你就可以这么写：
struct info
{
int a;
int b;
};
int main()
{
info in = { 10,20 };
list<info> lt;
lt.push_back(in);
auto it = lt.begin();
while (it != lt.end())
{
cout << it->a << " " << it->b << endl;
it++;
}
return 0;
}我们下来看看怎么重载 -> 这个吧，其实重载 -> 就是返回 list 中的成员变量的 _val 的地址：
T* operator->()
{
return &(_node->_val);
}上面的例子中在使用迭代器遍历 list 的时候，it->a，本质上应该是先调用 operator-> 得到结构体的指针，再通过 -> 拿到数据，因此实际上应该这么写的：it->->a。但是这样写着实奇怪， 因此编译器会进行处理，我们只需要这么写就可以：it->a。
5. const 迭代器
首先，我们要理解 const 迭代器和非 const 迭代器的区别：
在 const 迭代器中解引用返回的数据是不能够更改的。
在 const 迭代器中 operator-> 返回的指针解引用得到的数据也是不能修改的！
也就是说在 const 迭代器中 operator* 的返回值应该是 const T&，operator-> 的返回值应该是 const T* 。然后，你一拍脑袋说，这好办哇！我们把非 const 迭代器的代码 copy 一份，改成 const 迭代器不就行了嘛！是的这样做完全没问题，但是，既然我们学了模板，这样的脏活累活自然得交给我们的编译器去做啦！
我们来看看怎么把 const 迭代器和非 const 迭代器融合成一个模板吧！const 迭代器和非 const 迭代器的不同就是右两个函数的返回值类型不同嘛，因此我们可以将函数的返回值的类型参数化，通过外部实例化的传递来决定是 const 迭代器还是非 const 迭代器！
因为有两个函数的返回值不相同，所以我们需要为我们封装的迭代器增加两个模板参数！
当我们传入 T&，T* 就是非 const 的 iterator，当我们传入 const T&，const T* 就是 const 的 iterator。是不是美妙绝伦！
__list_iterator 的模板参数改了，其他的函数也相应地改改嘛！因为给 __list_iterator 加上模板参数之后呢，这个类型写起来就比较复杂，我们可以使用 typedef 给他重新去一个名字
template<class T, class Ref, class Ptr>
struct __list_iterator
{
public:
typedef __list_iterator<T, Ref, Ptr> self;
__list_iterator(ListNode<T>* node)
:_node(node)
{}
self& operator++()
{
_node = _node->_next;
return *this;
}
bool operator!=(const self& it)
{
return _node != it._node;
}
Ref operator*()
{
return _node->_val;
}
Ptr operator->()
{
return &(_node->_val);
}
private:
ListNode<T>* _node;
};6. begin() && end()
上面的那张图已经解释了如何定义 const 迭代器和非 const 迭代器啦！那么 begin() 与 end() 的 const 版本和 非 const 版本就是信手拈来了！
begin 对应的迭代器起始就是用 _head->_next 构造一个迭代器返回！
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}为啥可以直接返回节点的指针呢 ？因为单参数的构造函数支持隐式类型转化嘛！
其实 list 的模拟实现，难的就是迭代器的部分，好的，我们的迭代器就已经实现完毕了！懂的都懂嘛！
7. iterator insert(iterator pos, const T& val)
我们先通过 pos 拿到节点的指针，申请节点，链接就行了，相当简单呢！最后返回新插入的节点的迭代器。
void insert(iterator pos, const T& val)
{
ListNode<T>* cur = pos._node;
ListNode<T>* prev = cur->_prev;
ListNode<T>* newNode = new ListNode<T>(val);
prev->_next = newNode;
newNode->_prev = prev;
newNode->_next = cur;
cur->_prev = newNode;
return newNode;
}8. iterator erase(iterator pos)
在 list 的使用哪一节，我们观察到了，erase 是不能删除 end() 位置的节点的，即不能删除哨兵位的头结点。我们可以使用断言检查。为了解决迭代器失效的问题呢，我们可以给 erase 增加一个返回值。
iterator erase(iterator pos)
{
ListNode<T>* cur = pos._node;
ListNode<T>* prev = cur->_prev;
ListNode<T>* next = cur->_next;
delete cur;
prev->_next = next;
next->_prev = prev;
return next;
}9. void push_front(const T& val)
在我们完成了 insert 接口和 erase 接口的实现之后，下面的插入删除可以完全复用啦！
void push_front(const T& val)
{
insert(begin(), val);
}10. void pop_front()
void pop_front()
{
erase(begin());
}11. void pop_back()
这里的 -- 需要在迭代器里面重载，原理和 ++ 差不多，就交给你来实现啦！
void pop_back()
{
erase(--end());
}12. size_t size() const
遍历一遍出结果，或者呢，你也可以在 list 里面维护一个表示 list 长度的变量。
size_t size() const
{
int sz = 0;
auto it = begin();
while (it != end())
{
sz++;
++it;
}
return sz;
}13. void clear()
这个函数是清空 list 存储有效数据的节点，也就是说 clear 之后呢，哨兵位的头结点还在！
切记不可以 ++it，因为迭代器失效的问题嘛！我们通过 erase 的返回值来清除节点就行啦。
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}14. ~list()
主打的就是一个复用。我们写完 clear 之后析构函数直接复用，然后再释放掉 _head 就可以啦！文章来源：https://www.toymoban.com/news/detail-719787.html
~list()
{
clear();
delete _head;
_head = nullptr;
}
文章来源地址https://www.toymoban.com/news/detail-719787.html
到了这里，关于C++ list 模拟实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[C++]:12:模拟实现list](https://imgs.yssmx.com/Uploads/2024/01/814378-1.png)
