一、介绍
官方给的 list的文档介绍
简单来说就是：
list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素。
这个时候大家可能觉得，都是有序列表，那么和vector有什么区别和对比吗？实际上和我们学习数据结构时对链表和数组的对比很像，我来介绍一下：
| std::list
| std::vector
|
那么list到底长什么样子呢？上图片，是不是就好理解了
二、list的使用
作为STL(标准模板库)中的一个类，我们这篇blog的任务就是学习其的使用。
构造函数
| 构造函数 | 接口说明 |
| list() | 构造空的list |
| list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
| list (const list& x) | 拷贝构造函数 |
| list (InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造list |
上面虽然用了不少代名词，我们直接上代码例子分析自然就清楚了，分析在代码中。
（如果迭代器看不懂可以看这一篇【C++】C++中的vector-CSDN博客，里面详细介绍了）
#include <iostream>
#include <list>
using namespace std;
int main()
{//list<int> l1; // 构造空的l1list<int> l2(4, 100); // l2中放4个值为100的元素list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构造l3list<int> l4(l3); // 用l3拷贝构造l4// 以数组为迭代器区间构造l5int array[] = { 16,2,77,29 };std::list<int> l5(array, array + sizeof(array) / sizeof(int));// 用迭代器方式打印l5中的元素for (std::list<int>::iterator it = l5.begin(); it != l5.end(); it++)std::cout << *it << " ";std::cout << endl;// C++11范围for的方式遍历for (auto& e : l5)std::cout << e << " ";std::cout << endl;return 0;
}其实我们可以看出来，list这个类和之前的使用类的方法是基本一致的，不过他需要一个<int>来确定这个序列容器的类型，比如int，char....，就是list<int>可以当成一个整体，和vector很像。
list iterator的使用
| 函数声明 | 接口说明 |
| begin + end | 获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置 的iterator/const_iterator |
| rbegin + rend | 获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的 reverse_iterator |
PS：
#include <iostream>
#include <list>
using namespace std;void print_list(const list<int>& l)
{// 注意这里调用的是list的 begin() const，返回list的const_iterator对象// 保护数据通过将l声明为常量引用，我们保证了在print_list函数内部无法修改列表l的内容。// 这意味着无法添加、删除或修改列表中的任何元素。这是一种良好的编程实践，// 特别是当函数的目的仅仅是读取数据而不修改数据时。for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it){cout << *it << " ";//如果不同const 就通过//*it = 10; 编译不通过}cout << endl;
}
int main()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));// 使用正向迭代器正向list中的元素for (list<int>::iterator it = l.begin(); it != l.end(); ++it)cout << *it << " ";cout << endl;// 使用反向迭代器逆向打印list中的元素for (list<int>::reverse_iterator it = l.rbegin(); it != l.rend(); ++it)cout << *it << " ";cout << endl;return 0;
}
常用的成员方法
list capacity
| 函数声明 | 接口说明 |
| empty | 检测 list 是否为空，是返回 true ，否则返回 false |
| size | 返回 list 中有效节点的个数 |
列表元素访问
| 函数声明 | 接口说明 |
| empty | 检测 list 是否为空，是返回 true ，否则返回 false |
| size | 返回 list 中有效节点的个数 |
list modifiers
| 函数声明 | 接口说明 |
| push_front | 在list首元素前插入值为val的元素 |
| pop_front | 删除list中第一个元素 |
| push_back | 在list尾部插入值为val的元素 |
| pop_back | 删除list中最后一个元素 |
| insert | 在list position 位置中插入值为val的元素 |
| erase | 删除list position位置的元素 |
| swap | 交换两个list中的元素 |
| clear | 清空list中的有效元素 |
#include <iostream>
#include <list>
#include <vector>
using namespace std;
void PrintList(list<int>& l)
{for (auto& e : l)cout << e << " ";cout << endl;
}
//===============================================================
// push_back/pop_back/push_front/pop_front
void TestList1()
{cout << "TestList1()" << endl;int array[] = { 1, 2, 3 };list<int> L(array, array + sizeof(array) / sizeof(array[0]));// 在list的尾部插入4，头部插入0L.push_back(4);L.push_front(0);PrintList(L);// 删除list尾部节点和头部节点L.pop_back();L.pop_front();PrintList(L);
}
//================================================================
// insert /erase
void TestList2()
{cout << "TestList2()" << endl;int array1[] = { 1, 2, 3 };list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));// 获取链表中第二个节点auto pos = ++L.begin();cout << *pos << endl;// 在pos前插入值为4的元素L.insert(pos, 4);PrintList(L);// 在pos前插入5个值为5的元素L.insert(pos, 5, 5);PrintList(L);// 在pos前插入[v.begin(), v.end)区间中的元素vector<int> v {7, 8, 9 };L.insert(pos, v.begin(), v.end());PrintList(L);// 删除pos位置上的元素L.erase(pos);PrintList(L);// 删除list中[begin, end)区间中的元素，即删除list中的所有元素L.erase(L.begin(), L.end());PrintList(L);
}
// resize/swap/clear
void TestList3()
{cout << "TestList3()" << endl;// 用数组来构造listint array1[] = { 1, 2, 3 };list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));PrintList(l1);// 交换l1和l2中的元素list<int> l2;l1.swap(l2);PrintList(l1);PrintList(l2);
//使用resize将l2的大小先增加到5个元素，所有新添加的元素都将被赋值为99l2.resize(5, 99);PrintList(l2);// 将l2中的元素清空l2.clear();cout << l2.size() << endl;
}int main()
{TestList1();TestList2();TestList3();return 0;
}
好了，目前通过上面这一段精简的代码，我们把常用的成员方法基本解决了，但是list的成员方法实在太多，很多操作都是很特殊，不常见的，但是如果刚好需要又非常方便，所以就是可以在需要的时候查官方文档。
list的迭代器失效
在之前我们学习过vector的迭代器会有失效的情况，原因很简单，指针失效了，那么list会不会有这种情况呢？答案是有的，前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。所以影响相对vector来说比较小。
理解了吗？两段代码来检测一下大家
#include <iostream>
#include <list>
using namespace std;void TestListIterator1()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));auto it = l.begin();while (it != l.end()){l.erase(it);++it;}
}void TestListIterator2()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));auto it = l.begin();while (it != l.end()){l.erase(it++); // it = l.erase(it);}
}int main()
{TestListIterator1();TestListIterator2();return 0;
}是 TestListIterator1 出错 还是 TestListIterator2 出错？
如果你一眼就看出了，那么恭喜你，你掌握了。
其实很简单，第一个当调用erase(it)后，it被删除，使得it失效。尝试在失效的迭代器上进行操作（比如递增++it）是未定义行为。
第二个，l.erase(it++)：这里使用了“后置递增”运算符，它创建了it的一个副本，然后将副本传递给erase方法。erase删除了当前迭代器指向的元素，然后it被递增，指向下一个元素。因为it在递增前已经复制给erase，所以即使在删除当前元素后，递增操作是在一个新的、未被修改的迭代器上进行的，这保证了迭代器的有效性。或者可以这样写，等价的：it = l.erase(it);：erase函数返回下一个有效的迭代器，然后将其赋值给it。这样，it始终保持有效，且指向当前元素的下一个元素。
三、结语
到此为止，我们已经把list的基本使用方法学习结束了，list的成员方法十分丰富，这篇文章就是介绍了常用的，让大家基本会使用，目前你也可以用这种双向列表来实现一些复杂的算法，我在下面了可以给大家写一个。等我有时间再出一篇，模拟实现list的blog，理解他的底层实现，有缘再见，朋友！
实现的经典算法
约瑟夫环问题（Josephus Problem）。这个问题的一个版本可以描述如下：N个人围成一圈，从第一个人开始报数，每报到M时，该人被淘汰，接着从下一个人开始继续报数，直到所有人都被淘汰。任务是按顺序输出被淘汰人的编号。
#include <iostream>
#include <list>
using namespace std;void JosephusProblem(int N, int M) {// 初始化人员列表，编号从1到Nlist<int> people;for (int i = 1; i <= N; ++i) {people.push_back(i);}auto it = people.begin(); // 迭代器指向第一个人while (!people.empty()) {// 模拟报数，M-1次移动迭代器（因为从当前人开始报数）for (int count = 1; count < M; ++count) {++it;// 如果迭代器超过了末尾，重新从头开始if (it == people.end()) {it = people.begin();}}// 报到M，移除当前人，并输出编号cout << *it << " ";it = people.erase(it); // erase返回下一个元素的迭代器// 如果列表不为空，但迭代器已经到达末尾，需要重新指向开头if (it == people.end() && !people.empty()) {it = people.begin();}}cout << endl;
}int main() {int N = 7; // 人数int M = 3; // 报数淘汰JosephusProblem(N, M);return 0;
}
