深度探索list

1.list的基本组成

list是一个双向链表，它的基本组成就是

成员	作用
prev指针	指向上一个元素
next指针	指向下一个元素
data	用来保存数据

2.list的迭代器

由于人们一般习惯于：迭代器++是找到下一个元素，迭代器–是找到上一个元素。在双向链表list中，我们可以知道下一个元素就是next所指元素，上一个元素就是prev所指元素。
如果我们想要实现迭代器++的操作，就需要访问list节点对应的next指针。所以迭代器是一个类，需要为我们封装这些操作，或者更准确的说，迭代器类是一个智能指针。

list的插入和接合操作都不会造成原有的list迭代器失效，对于删除操作，也只有”指向被删除元素“的那个迭代器失效，其它迭代器不受任何影响

1.++i 和 i++的重载

Q：在C++中，由于++i和i++都只有一个参数，那么如何对这两种分别进行重载呢？

A：在C++中，规定了带有参数的是后置++，没有参数的是前置++。比如说

operator++(int) {}; //对 i++ 进行重载
operator++() {};    //对 ++i 进行重载

注意

1.后置++的* 操作符不是解引用，而是调用了拷贝构造函数来制造一个副本
2.为了模拟C++的整数不能进行如下操作：

(i++)++;    //不允许
i++++;     //不允许
(++i)++;    //允许
++++i;      //允许

C++允许前置++连续，但是不允许后置++连续，所以迭代器中，对于前置++，返回的是引用。而后置++运算符返回的不是reference，而是值；

3.G4.9的list

1.G4.9对比G2.9的一些细节修正

1.list中指针的类型不再是void*
2.代器不再需要传一种类型的三个形式（T,* T,& T），而是传入T之后再typedef。

2.G4.9的list更加复杂

迭代器补充

1.迭代器的设计原则

迭代器是算法和容器之间的桥梁，所以算法会想知道迭代器的一些性质来辅助算法。
这些性质如下：

五种迭代器中必须typedef的性质	解释
iteratior_category	迭代器类型
value_type	迭代器所指对象的类型
difference_type	两个相邻的迭代器之间的距离
pointer	指向value type的指针
reference	对value type的引用

2.iterator traits的作用和设计

1.作用

由于上面的设计原则可以知道，迭代器必须typedef五个性质。但是如果这个指针不是一个class的指针，而就是一个普通的指针的话，这样的话，我们怎么分辨呢？iterator traits就用上了。

2.设计

设计一个中间层作在迭代器和算法中间作为媒介，这个中间层就是iterator traits

实际上就是利用了C++中模板的偏特化来进行一个区分。

注意即使是const指针，为了它能够创建一个非const变量，我们也应当返回一个非const的类型。

图1这里仅仅是举例，完整在图2