C++STL之List的实现

首先我们要实现List的STL,我们首先要学会双向带头链表的数据结构。那么第一步肯定是要构建我们的节点的数据结构。

首先要有数据域，前后指针域即可。

再通过模板类进行模板化。

然后再写List的构造函数，这个地方用T&,通过引用就可以减少一次形参拷贝的发生，提高性能。

其次const可以提高安全性和扩展性，这样const T&和T&就都能传引用，但是又保证了数据的不可修改。

然后我们再写List类和迭代器。

迭代器的作用其实就是将容器内容的访问与修改进行包装，使得使用的程序员可以不直接对底层数据进行修改，这样不仅提高了数据的安全性，并且提高了使用者的规范性和代码的可读性。也通过屏蔽底层实现增加了移植性。

首先我们先分析迭代器和List的类的基本成员和模板的使用。

迭代器中实际的成员仍然是我们的原生节点指针，但通过迭代器的包装，就避免了我们直接使用节点，更避免了我们直接操控节点的数据域和指针域，起到多重包装的作用。

List本质是一个对节点操作的工具，所以只需要携带一个size统计数量和锁定头节点（这里是哨兵卫节点）就可以了，本身不携带数据节点的内容。

然后就是分析模板的使用，先对List进行分析。

首先定义出我们的模板T，然后为了实现const迭代器和普通迭代器，正常情况下我们要实现两遍，但是由于存在模板我们可以将这个重复的工作交给编译器。

本质就是通过List<>先锁定T模板是什么类型再通过：：域限定符去调用里面的常量迭代器的类模板参数列表并且通过（）调用构造函数。

于是我们通过模板实现了两个类型的迭代器，借助编译器进行实现。

理清楚了我们的模板用法，剩下的工作就驾轻就熟了

首先实现插入，这样我们的头插，尾插就可以复用insert了。

、

同样我们可以先写erase，这样后面头删，尾删就可以复用erase了。

其他实现也非常简单，主要要讲的就是list的析构函数和=的运算符重载。

析构函数就是先清除数据再抹掉头节点即可，没有很大难度。但是一定要分清楚顺序，不要先抹除头节点或者忘记抹除。

运算符重载的写法是现代写法，主要可以方便，形参的lt会被编译器自动回收，而不用自己去操作内存，减少代码量。

然后我们来研究list的构造函数，首先我们要写一个空链表的构造，也就是头节点的构造函数，可以为我们的无参构造和初始化提供方便。那么无参构造就可以直接复用了，而有参构造也可以直接利用其进行头节点的初始化。

当我们完善了List,接下来我们就可以继续完善我们迭代器。

主要就是实现各个运算符的重载，难度不大。

但是我们要注意的是各个重载的返回类型！

首先对于+,-这种移动显然返回类型应该也是相应的迭代器类。

然后就是对迭代器解引用显然就是要获取对应的数据，所以返回的是其数据内容（数据的引用）

而->其实外层会有一个->所以我们实现的时候不能直接把数据内容传出去，而是要返回数据的地址，不然就是错误的。本质可以写出（&（-node->data））->data。

==和!=显然返回bool值就没有其他内容了。