《白话C++》第10章 Page126 常用容器 10.6.4 std::list

1. 基本概念与本质特性

std::list实现双向列表（也称链表），每一个节点，都有一个指针，指向后一节点和前一节点（都可为空，比如首节点的“上一节点”）。

因为，采用额外的指针维护前后关系，所以列表节点的内存完全不需要连续，这就让节点的插入，删除，甚至链表的合并操作，变得简单。要合并两个vector，需要在第一个vector开辟一大块连续内存，而合并两个列表，只需要让前一列表最后一个节点的“下一节点指针”，指向第二个列表的首指针，再让后者的“前一节点指针”，指向前者即可。

 上图演示了两个vector合并最悲惨的一种情况：合并目标vector1后续可用的连续内存空间不足，只好另开新界，然后复制待合并的两份数据。list合并就永远不会有这种情况发生，如下图所示：

改变两个指针的指向，list2就全部归顺list1了。

【课堂作业】：图解list操作

请读者画出list插入一个节点与删除一个节点的操作过程。

在节点增删操作的性能上，list完胜vector和deque，但在定位节点的速度上，list不支持随机访问。如果要修改列表中第9个节点的内容，需要从前面爬起，连爬8次到达，或者考虑从后面倒着爬，如果总节点数没超过17个的话。

在内存占用上，list和vector各有千秋，表面上list的每个节点都要至少多占用2个指针，但由于vector提出的是占用“连续内存”这样苛刻的要求，相比之下，list的要求更好满足。

更重要的是，list不需要“预分配”内存机制，所以不会占用多余内存。

另外一点，list胜出的是：vector和deque由于内存是连续的，当变化之后，容易造成所有数据移位，结果原来代码中使用的迭代器，指针，引用等，很多情况下会失效，需要重新指向。list插入或删除某一节点，除了被删除的节点之外，其他迭代器起，指针，引用等还有效。

某些算法在不支持随机访问的数据结构上执行，会慢许多，但某些算法如果针对list的结构做特点优化，又会快不少。

2.常规的队列接口

尽管deque是相对整齐的队列，而list往往是歪来歪去的长蛇阵，但好歹是都是队列，还都双向，因此list的一些操作接口，和deque是类似的：

//取第一个元素，不判断是否为空
T const& front();
//取最后一个元素，不判断是否为空
T const& back();//在前端或后端加入新元素
void push_front(t);
void push_back(t);//弹出前端或后端的1个元素，并不返回
void pop_front();
void pop_back();

其他标准容器所需要的：

//正向迭代器始末
begin(); //返回正向迭代器
end(); //返回正向迭代器结束位置//逆向迭代器始末
rbegin();
rend();/*C++ 11提供，返回常量迭代器（const_iterator）*/
cbegin();
cend();//是否为空，高效，判断begin() == endl()
bool empty();
//返回个数，需遍历，效率一般
size_t size();
//将元素个数变成num个，如有新增元素，采用默认构造
void resize(num);
//将元素变成num个，如有新增元素，复制elem
void resize(num, elem);

【课堂作业】：证明容器删除元素时，对象被析构

写一个list <S> 调用resize的例子，其中S是用户自定义class/struct类型，证明当resize(num)所传入的num比当前元素个数少时，被扔出容器的元素对象将析构。

3.高效的插入与删除

（1）插入操作

std::list提供三个insert的重载版本：

//在迭代器pos指定位置上，插入一个新元素elem
//返回插入后，同一位置上的有效迭代器
iterator & insert(pos, elem);//在迭代器pos指定位置上，插入n个新元素elem
//无返回值，原pos迭代器通常已经失效
void insert(pos, n, elem);//在迭代器pos指定位置上，插入外来的[beg, end)区间的元素
//无返回值，原pos迭代器通常已经失效
void insert(pos, beg, end);

演示例子：

#include <list>
...list <int> li;li.insert(li.begin(), 11);
li.insert(li.begin(), 2, 22);list <int> li2;
/* 把[++li.begin(), li.end()) 区间的元素
，插入li2的begin()位置*/
li2.insert(li2.begin(), ++li.begin(), li.end());

入参beg和end也可以是指向裸数组的指针，下面演示这种情况，并同时演示使用advance调整插入位置：

list <int>::iterator pos = li2.begin();
advance(pos, 2);int arr[] = {0, 1, 2, 3, 4, 5};
li2.insert(pos, arr, arr + sizeof(arr)/sizeof(arr[0]));

（2）删除操作

list提供erase和remove两种删除接口：

//删除指定迭代器位置的元素，返回删除后，同一位置上的有效迭代器
iterator & erase(pos);//删除指定迭代器区间的所有元素[beg, end),没有返回值
void erase(beg, end);//删除与指定值相等的所有元素
void remove(val);//删除符合指定判断条件的所有元素
void remove_if(Pred);

erase还是按迭代器位置删，remove则是删除所有指定值的元素，而remove_if则是删除符合判断式Pred的数据：

//判断v是不是偶数
bool is_even_number(int v)
{return (v % 2) == 0;
}void test_list_remove()
{list <int> li;for(int i = 0; i < 10; ++ i){li.push_back(i/2);}li.remove(3); //删除list中，值等于3的元素cout << li.size() << endl; //8li.remove_if(is_even_number);for(list<int>::const_iterator it = li.begin(); it != li.end(); ++ it){cout << *it << ',';}cout << endl;
}

【课堂作业】：测试list、vector、deque的插入与删除性能

参考之前的例子，将deque加入测试。

4. 其他变动性操作

变动性操作是list的优势项目，所以它提供了许多这类操作，下面是几个较常用的操作：

//将所有元素，倒个序儿存储，
//提醒：别和reserve混了
reverse();//元素大小排序，元素之间需要支持使用 < 作比较
sort();
//采用comp方法比较两个元素，然后排序
sort(Compare comp);//将当前list和传入的list中的元素进行有序合并
//注意：两个list中的元素在合并前必须已经有序，
//合并后仍然有序
merge(list& other);//将当前list和传入的list中的元素根据
//给定的比较方法进行有序合并
//注意:两个list中的元素在合并前必须
//已经是按comp方法排序，合并后仍然有序
merge(list& other, Compare comp);

参数中的“Compare”同样是一种判断式，判断原则是：对给定的两个入参比较大小，如果第一个入参比较小，就返回真，否则返回假。我们以第二个版本sort示例：

list还提供unique和splice函数，需自学。

【小提示】：为什么list的接口功能“一枝独秀”？

这里提一个问题：list提供的这么多特定操作（在STL中也称算法），难到别的容器不需要吗？比如说“sort(排序)”，难道vector中，deque中的元素就没有排序的需求？真相是，vector和deque都可直接使用全局版本的sort()等算法，因为它们支持随机访问。