标题：[C++] 模拟实现list

@水墨不写bug

目录

一、list简介

二、铺垫

 I，分离编译模式的选择

II，数据结构分析

（1）命名空间

 （2）类的设计分析

正文开始：

一、list简介

        C++ STL（Standard Template Library，标准模板库）中的list容器是一个双向链表，它支持常数时间的元素插入和删除操作，而不需要重新分配整个容器或移动容器中的元素（除了插入或删除点附近的元素可能会移动）。

list容器的主要特点包括：

1. 双向链表：list内部实现为一个双向链表，每个元素都包含数据和指向列表中前后元素的指针。这允许快速向前和向后遍历链表。

2. 动态大小：list的大小可以根据需要动态增长或缩小，这是通过插入或删除元素来实现的。

3. 随机访问不支持：与vector或deque等容器不同，list不支持随机访问，即不能使用下标来直接访问元素。要访问元素，必须使用迭代器或者成员函数如front(), back(), begin(), end()等。

4. 高效的插入和删除：在list的任何位置插入或删除元素都是高效的，因为只需要调整相关元素的指针即可，不需要移动或复制其他元素。

5. 迭代器：list提供双向迭代器，允许向前和向后遍历列表。然而，这些迭代器不是随机访问迭代器，因此不支持+、-或数组下标操作符 [] 。

6. 成员函数：list提供了丰富的成员函数来管理容器中的元素，包括push_front(), push_back(), pop_front(), pop_back(), insert(), erase(), clear(), size(), empty()等。

7. 内存分配：list中的每个元素都是动态分配的，list会有比连续存储（如vector）更高的内存使用率。

二、铺垫

 I，分离编译模式的选择

         本文我们要实现的是与STL功能基本一致的list，通过实现一个list类模板从而可以指定存入数据的类型，由此实现的list具有更高的实用性和灵活性。

        但是在前面的文章《C++：模板进阶》中我们知道：在编译时期，模板不会实例化出对象，那么在链接时，编译器在寻找对象的地址时找不到，所以报错。解决方法就是需要将生命和定义放在一个 .h 文件中。        于是，我们实现的list也是将类模板直接放在一个.h文件中。

II，数据结构分析

（1）命名空间

        我们在实现list的时候，由于我么起的名字和STL中的名字完全相同，所以为了保险起见，我们需要将我们实现的项目放在自己的命名空间中，防止命名冲突。(命名空间的名称可以自己决定，但是不要和STL冲突)

namespace ddsm{  //....... };

 （2）类的设计分析

        我们想要实现一个链表结构，首先需要是实现一个链表的节点类，于是，我们可以将链表的节点类实现如下：

template struct ListNode { 	ListNode* _prev; 	ListNode* _next; 	T _data;  	ListNode(const T& val = T()) 		:_prev(nullptr) 		,_next(nullptr) 		,_data(val) 	{} };

         对于链表的一个节点，并没有需要特殊实现的功能。

        唯一需要注意的是，我们实现的是一个模板类，在构造函数中，缺省参数我们给了一个匿名对象，这是一个明智的选择：

        如果T是内置类型，假如是int，则对于如下代码：

int a = int();

        a会被初始化为0；

        如果T是自定义类型，则会在匿名对象实例化时，调用这个自定义类型的构造函数，也会得到初始化。

        然而仅仅有了list的一个节点是不够的，这只是第一步，接下来我们需要将链表的一个一个耳朵节点链接起来，这就需要另一个类来维护整个链表。 

         我们把将要实现的维护一整个链表的类命名为list（此命名在命名空间ddsm中不必担心命名冲突问题），一般我们通过首节点的指针来维护这一整个链表，于是list类框架如下：

template class list { 	typedef ListNode Node;  private: 	Node* _pHead; };

        但是我们发现：

        STL的list的迭代器是可以进行自增，自减操作并实现链表迭代器的移动的，如果我们就只按照上面的方式来实现链表，就会发现我们的迭代器（ListNode* 指针）是没有办法进行自增自减来达到迭代器移动的目的的。为了尽可能贴近STL的实现方法，同时更底层的了解STL内部的实现方式，我们可以这样选择：

        对迭代器进行封装，把迭代器类型（ListNode* 指针）封装为包含（ListNode* 指针）的类，一样一来，一旦有了类，我们就可以对其对象操作符进行重载，这样我们就可以在重载函数内实现自己想要的操作！

---

        总结来说：原来的Node*不符合我想要的行为，我们可以通过对Node*封装为ListIterator，在ListIterator内重载操作符来控制Node*的行为。

        于是，第三个类就是对指针的封装，将（ListNode* 指针）封装为包含（ListNode* 指针）的类，目的是对（ListNode* 指针）的操作符进行重载，这里我们把类名定为ListIterator，防止与其他容器的迭代器类型混淆。

template struct ListIterator {     typedef ListNode Node;  	 Node* _node; };

未经作者同意禁止转载