list列表

• cppreference

list

头文件

• #include ＜list＞

底层数据结构

• list同样是一个模板类，它底层数据结构为双向循环链表。因此，它支持任意位置常数时间的插入/删除操作，不支持快速随机访问。
• 双向链表的每个元素中都有一个指针指向后一个元素，也有一个指针指向前一个元素

内存分配策略

• list的空间配置策略，自然是像我们普通双向链表那样，有多少元素申请多少内存。它不像vactor那样需要预留空间供新元素的分配，也不会因找不到连续的空间而引起整个容器的内存迁移。

迭代器失效问题

• list 有一个重要性质：插入操作（insert）与接合操作（splice）都不会造成原有的list迭代器失效。这在vector是不成立的，因为vactor的插入可能引起空间的重新配置，导致原来的迭代器全部失效。list的迭代器失效，只会出现在删除的时候，指向删除元素的那个迭代器在删除后失效。
  通常来说，forward_list在使用灵活度上比不上list，因为它只能单向迭代元素，且提供的接口没有list多。然而，在内存的使用上，它是比list占优势的。当对内存的要求占首要位置时，应该选择forward_list。

构造函数

• list<int> c;空链表

• list<int> c1(3); 建一个含三个默认值是0的元素的链表 　

• list<int> c2(5,2); 建一个含五个元素的链表，值都是2 　
• list<int> c4(c2); 建一个c2的copy链表

• list<int> c5(c1.begin(),c1.end()); c5含c1一个区域的元素[_First, _Last)。

• list 容器不支持根据下标随机存取元素

• list 的成员函数 front() 和 back()，可以各自返回第一个和最后一个元素的引用。在空 list 中调用它们中的任意一个，结果是未知的，因此不要这样使用。可以通过迭代器的自增或自减来访问 list 的内部元素。

List常用操作函数

list 的特点

• (1) 不使用连续的内存空间这样可以随意地进行动态操作；
• (2) 可以在内部任何位置快速地插入或删除，当然也可以在两端进push 和pop 。
• (3) 不能进行内部的随机访问，即不支持[ ] 操作符和vector.at() ；
• (4) 相对于verctor 占用更多的内存。
• 有自身的sort函数
• STL 中的算法 sort 可以用来对 vector 和 deque ，string排序，它需要随机访问迭代器的支持。因为 list 不支持随机访问迭代器，所以不能用算法 sort 对 list 容器排序。因此，list 容器引入了 sort 成员函数以完成排序。
• 注意
  std::sort 要求随机访问迭代器且不能用于 list 。此函数与 std::sort 的区别在于，它不要求 list 的元素类型可交换，保留所有迭代器的值，并进行稳定排序。