C++ list介绍

1. list简介

list，即链表。
链表的种类有很多，是否带头结点，是否循环，是否双向——list是带头双向循环链表。
关于list的使用本文中不作介绍，本文将重点放在list的实现框架、list的迭代器和反向迭代器设计、list的迭代器失效上。

2. list的实现框架

list的实现，实质上实现了三个类。
对于链表而言，只需要一个指向头结点的指针，即可拿到整个链表。这句话中就包括了要实现的三个类：链表、链表的迭代器和链表的结点。

2.1 链表结点

首先，我们需要将链表的结点封装成一个类。C++中很少使用内部类，一般定义成struct(即class + public), 允许外部使用即可。

结点类是最基础的一个类，指向它实例化出对象的指针，既是链表迭代器类的成员变量，也是链表类的成员变量。

2.2 链表迭代器

在vector当中，迭代器是用原生指针即可实现，这是因为vector的底层实际上是一个具有连续存储空间的动态数组，迭代器的行为与原生指针的行为相同。

但对于链表，链表结点的存储空间不一定是连续的，因此原生指针的行为不一定能达到目的。而将链表的迭代器封装为一个类，即可通过运算符重载，实现想要的行为。

2.3 链表

链表类，是我们最终的主体。它仍然以指向结点的指针作为成员变量，但是这个成员变量是特殊的，其为指向链表头结点(即哨兵位)的指针。

3. list迭代器及反向迭代器设计

3.1 list迭代器

要设计list的迭代器，就会想到还要设计list的const迭代器。
需要说明的是，const迭代器并不是简单地在普通迭代器前加上const。

const iterator it;
//这里const实际修饰it,使得it本身不能改变
//const迭代器并不是迭代器本身不能改变，而是迭代器指向地对象不能被修改

因此，通过以上分析可得，如果要将迭代器封装成类，普通迭代器与const迭代器，实为两个不同的类。

但如果两种迭代器都分别实现的话，会发现代码只有很细微的差别，此时我们会想到将迭代器设计为类模板，普通迭代器与const迭代器都是这个模板的实例化。

那么，如何设计这个类模板呢？
考虑到，普通迭代器与const迭代器，只有在解引用运算符重载与成员访问运算符(即->)重载时有返回值上的区别（普通指针与const指针、普通引用与const引用），所以需要三个模板参数——确定节点数据类型的类型参数T，确定指针类型的参数Ptr和确定引用类型的参数Ref。

有几点需要说明：

1. list的迭代器是bidirectional iterator,即双向迭代器。双向迭代器只重载++和- -，不重载加减一个具体数字。双向迭代器，关系运算符也只重载 == 和 ! = 。
2. 关于解引用操作符与成员访问操作符的重载说明如下。

链表的结点是一个类，对迭代器解引用是为了拿到其中的数据

当迭代器是用 -> 这个操作符时，说明结点中所存储的数据应是一个自定义类型，通过->操作符去访问这个自定义类型允许外部访问的成员函数或成员变量

//使用代码示例如下所示
int main()
{list<string> l1;l1.push_back("abc");l1.push_back("efg");list<string>::iterator it = l1.begin();while(it != l1.end()){//以下两条语句打印出的结果相同cout << (*it).size() << endl;cout << it->size() << endl;//it->size()实则为it->->size()，有两个箭头，因为->运算符重载中返回的是&_node->_data,只不过通常只写一个箭头it++;}return 0;
}

3.2 list反向迭代器

反向迭代器是一种适配器，或者说是运用了适配器的设计模式实现的，本质上就是对普通迭代器的复用。具体实现时，将普通迭代器设置为反向迭代器的成员变量，实现反向迭代器的成员函数时，复用普通迭代器的成员函数即可。

3.3 list迭代器失效

相比于vector的迭代器失效，list迭代器失效的情况就要少得多。本质上，这是因为链表结构各节点间的插入删除并不会互相影响，不会出现vector中需要前移或后移的情况，而且链表也不需要像vector那样异地扩容。

所以，insert不会导致list迭代器失效，erase只会导致指向被删除结点的迭代器失效。

4. list与vector比较

在属性上，list与vector的差别，可以近似为链表与顺序表的差别，而且list的迭代器为双向迭代器，vector的迭代器是随机迭代器。

这个迭代器上的区别，使得vector对象可以使用算法库中的sort(这个函数要求传随机迭代器)，而list无法使用，因此list自身实现了一个sort作为成员函数，但是这个list的排序速度是很慢的，甚至慢于将list的数据拷贝到vector中，在vector中排序完后再拷贝会list的速度，因此慎用list的排序。

在功能上，如果想要在任意位置插入和删除数据，推荐使用list；如果想要在任意位置快速存取数据，推荐使用vector。