STL list 容器，又称双向链表容器，即该容器的底层是以双向链表的形式实现的。这意味着，list 容器中的元素可以分散存储在内存空间里，而不是必须存储在一整块连续的内存空间中。
list 容器中各个元素的前后顺序是靠指针来维系的，每个元素都配备了 2 个指针，分别指向它的前一个元素和后一个元素。其中第一个元素的前向指针总为 null，因为它前面没有元素；同样，尾部元素的后向指针也总为 null。
list 容器具有一些其它容器（array、vector 和 deque）所不具备的优势，即它可以在序列已知的任何位置快速插入或删除元素（时间复杂度为O(1)）。并且在 list 容器中移动元素，也比其它容器的效率高。
使用 list 容器的缺点是，它不能像 array 和 vector 那样，通过位置直接访问元素。举个例子，如果要访问 list 容器中的第 6 个元素，它不支持容器对象名[6]这种语法格式，正确的做法是从容器中第一个元素或最后一个元素开始遍历容器，直到找到该位置。
实际场景中，如何需要对序列进行大量添加或删除元素的操作，而直接访问元素的需求却很少，这种情况建议使用 list 容器存储序列。
#include<list>
template<
class T,
class Allocator = std::allocator<T>
> class list;
| 成员函数 | 功能 |
|---|---|
| begin() | 同array容器 |
| end() | 同array容器 |
| rbegin() | 同array容器 |
| rend() | 同array容器 |
| cbegin() | 同array容器 |
| cend() | 同array容器 |
| crbegin() | 同array容器 |
| crend() | 同array容器 |
| 成员函数 | 功能 |
|---|---|
| front() | 同array容器 |
| back() | 同array容器 |
| 成员函数 | 功能 |
|---|---|
| size() | 同array容器 |
| max_size() | 同array容器 |
| empty() | 同array容器 |
| 成员函数 | 功能 |
|---|---|
| clear() | 同vector容器 |
| insert() | 同vector容器 |
| emplace() | 同vector容器 |
| erase() | 同vector容器 |
| push_back() | 同vector容器 |
| emplace_back() | 同vector容器 |
| pop_back() | 同vector容器 |
| push_front() | 同vector容器 |
| emplace_front() | 同vector容器 |
| pop_front() | 同vector容器 |
| resize() | 同vector容器 |
| swap() | 同vector容器 |
| 成员函数 | 功能 |
|---|---|
| merge() | 合并两个事先已排好序的 list 容器，并且合并之后的 list 容器依然是有序的。 |
| splice() | 将一个 list 容器中的元素插入到另一个容器的指定位置。 |
| remove(val) | 删除容器中所有等于 val 的元素。 |
| remove_if() | 删除容器中满足条件的元素。 |
| reverse() | 反转容器中元素的顺序。 |
| unique() | 删除容器中相邻的重复元素，只保留一个。 |
| sort() | 通过更改容器中元素的位置，将它们进行排序。 |
前面章节已经详细介绍了 array、vector、deque 容器的迭代器，和它们相比，list 容器迭代器最大的不同在于，其配备的迭代器类型为双向迭代器，而不再是随机访问迭代器。
这意味着，假设 p1 和 p2 都是双向迭代器，则它们支持使用 ++p1、 p1++、 p1–、 p1++、 *p1、 p1==p2 以及 p1!=p2 运算符，但不支持以下操作（其中 i 为整数）：
#include <iostream>
#include <list>
using namespace std;
int main()
{
//创建 list 容器
std::list<char> values{ 'h','e','l','l','o' };
//使用begin()/end()迭代器函数对输出list容器中的元素
for (std::list<char>::iterator it = values.begin(); it != values.end(); ++it) {
std::cout << *it;
}
cout << endl;
//使用 rbegin()/rend()迭代器函数输出 lsit 容器中的元素
for (std::list<char>::reverse_iterator it = values.rbegin(); it != values.rend(); ++it) {
std::cout << *it;
}
return 0;
}
输出
hello
olleh
#include <iostream>
#include <list>
using namespace std;
int main()
{
//创建 list 容器
std::list<char> values{ 'h','e','l','l','o' };
//创建 begin 和 end 迭代器
std::list<char>::iterator begin = values.begin();
std::list<char>::iterator end = values.end();
//头部和尾部插入字符 '/'
values.insert(begin, '/');
values.insert(end, '/');
while (begin != end)
{
std::cout << *begin;
++begin;
}
return 0;
}
输出
hello/
#include <iostream>
#include <list>
using namespace std;
int main()
{
//创建 list 容器
std::list<char> values{ 'h','e','l','l','o' };
//使用begin()/end()迭代器函数对输出list容器中的元素
values.unique();
for (std::list<char>::iterator it = values.begin(); it != values.end(); ++it) {
std::cout << *it;
}
cout << endl;
return 0;
}
输出
helo
#include <iostream>
#include <list>
std::ostream& operator<<(std::ostream& ostr, const std::list<int>& list)
{
for (auto& i : list) {
ostr << " " << i;
}
return ostr;
}
int main()
{
std::list<int> list1 = { 5,9,0,1,3 };
std::list<int> list2 = { 8,7,2,6,4 };
list1.sort();
list2.sort();
std::cout << "list1: " << list1 << "\n";
std::cout << "list2: " << list2 << "\n";
list1.merge(list2);
std::cout << "merged: " << list1 << "\n";
}
输出
list1: 0 1 3 5 9
list2: 2 4 6 7 8
merged: 0 1 2 3 4 5 6 7 8 9
通过将自定义的谓词函数（不限定参数个数）传给 remove_if() 成员函数，list 容器中能使谓词函数成立的元素都会被删除。
#include <iostream>
#include <list>
using namespace std;
bool func(int x)
{
if (x < 10)
return 1;
else
return 0;
}
int main()
{
std::list<int> mylist{ 15, 36, 7, 17, 20, 39, 4, 1 };
//删除 mylist 容器中能够使 lamba 表达式成立的所有元素。
//mylist.remove_if([](int value) {return (value < 10); }); //{15 36 17 20 39}
mylist.remove_if(func);
for (auto it = mylist.begin(); it != mylist.end(); ++it)
std::cout << ' ' << *it;
return 0;
}
输出
15 36 17 20 39
forward_list 是 C++ 11 新添加的一类容器，其底层实现和 list 容器一样，采用的也是链表结构，只不过 forward_list 使用的是单链表，而 list 使用的是双向链表。
使用链表存储数据最大的特点在于，其并不会将数据进行集中存储（向数组那样），换句话说，链表中数据的存储位置是分散的、随机的，整个链表中数据的线性关系通过指针来维持。
因此，forward_list 容器具有和 list 容器相同的特性，即擅长在序列的任何位置进行插入元素或删除元素的操作，但对于访问存储的元素，没有其它容器（如 array、vector）的效率高。
那么，既然 forward_list 容器具有和 list 容器相同的特性，list 容器还可以提供更多的功能函数，forward_list 容器有什么存在的必要呢？
当然有，forward_list 容器底层使用单链表，也不是一无是处。比如，存储相同个数的同类型元素，单链表耗用的内存空间更少，空间利用率更高，并且对于实现某些操作单链表的执行效率也更高。
效率高是选用 forward_list 而弃用 list 容器最主要的原因，换句话说，只要是 list 容器和 forward_list 容器都能实现的操作，应优先选择 forward_list 容器。
参考：
1、C++ STL 容器库 中文文档
2、STL教程：C++ STL快速入门
3、https://www.apiref.com/cpp-zh/cpp/header.html
4、https://en.cppreference.com/w/cpp/container