一、list底层结构
list底层是带头节点的双向循环链表
- 双向：可以从前往后，也可以从后往前遍历
- 循环：找尾节点的时间复杂度为O( 1 )
- 带头节点：代码实现简单，不用考虑链表为空等特殊情况，可令end()迭代器指向头节点的位置
二、构造方法
构造函数
list<int> l1;
list<int> l2(5, 3);
//迭代器
vector<int> v{ 1,2,3,4,5 };
list<int> l3(v.begin(), v.end());
//C++11
list<int> l4{ 1,2,3,4,5 };
拷贝构造函数
利用l1拷贝构造l2
list<int> l1{ 1,2,3,4,5 };
list<int> l2(l1);
三、元素访问和迭代器
back&front
list<int> l1{ 1,2,3,4,5 };
cout << l1.front() << endl;
cout << l1.back() << endl;
三种遍历方式
list<int> l1{ 1,2,3,4,5 };采用下面三种方式对下面这个list<int>类型的对象进行遍历打印：
1.迭代器
list<int>::iterator it = l1.begin();
for (it; it != l1.end(); it++)
{
cout << *it << " ";
}
cout << endl;
打印结果：
2.范围for
注意这里e是int类型，不用再进行解引用
//范围for
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
打印结果：
3.反向迭代器
list<int>::reverse_iterator rit = l1.rbegin();
for (rit; rit != l1.rend(); rit++)
{
cout << *rit << " ";
}
cout << endl;
打印结果：
四、元素修改
尾插、头插、尾删、头删
insert、erase
list支持任意位置的插入，注意list对象的迭代器不支持加减数字，因为其底层空间不连续，如图：
如果要往一个位置进行插入，可以通过find函数返回位置进行，find是一个通用的函数模板，返回值是传入参数的迭代器类型，
list<int> l1{ 1,2,3,4,5 };
l1.insert(find(l1.begin(), l1.end(), 3), 10);//任意位置插入
l1.erase(find(l1.begin(), l1.end(), 10), l1.end());//任意位置的删除
swap
list内置的交换函数
list<int> l1{ 1,2,3,4,5 };
list<int> l2{ 5,6,7,8,9 };
l1.swap(l2);
resize
resize改变有效元素的个数，多的元素用第resize二个参数填充，如果没有给第二个参数，则默认用T()。
list<int> l1{ 0,1,2 };
l1.resize(5, 3);
五、特殊操作
remove
删除值为value的元素
list<int> l1{ 3,0,1,3,2,3 };
l1.remove(3);
remove_if
remove_if的参数是一个判断条件，可以是函数指针或者函数对象
//判断5的倍数
bool MultipleFive(int n)
{
return 0 == n % 5;
}
void Test10()
{
//此处传递函数指针
list<int> l1{ 10,0,1,3,5,7,20 };
l1.remove_if(MultipleFive);
}
unique、sort
unique，去重，删除所有重复元素，使用unique之前要先调用sort进行排序，这里的sort是list内置的sort，不是标准库中的sort
void Test()
{
list<int> l1{ 1,3,3,5,4,0,2,5,4 };
l1.sort();//默认升序
l1.unique();//删除重复元素
}
结果：
对于sort的使用，还可以自定义函数，并将函数指针作为参数传递给sort函数进行排序：
reverse
对链表进行逆置
void Test()
{
list<int> l1{ 1,3,5,7,9 };
l1.reverse();
}
结果：
六、list迭代器失效问题
list底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
erase导致的迭代器失效
如图所示，it迭代器所指向的位置被删除后，迭代器失效：
改正方法：
while (it != l1.end())
{
//it=l1.erase(it);
l1.erase(it++);
}
这里 l1.erase(it++)语句也能达到效果，因为后置++会将自增后的结果保存在临时变量中，而前置则不可以。
resize导致的迭代器失效
resize减少有效元素个数也会导致迭代器失效：
list<int> l1{ 1,3,5,7,9 };
auto it = l1.end();
l1.resize(3);
上面这个程序中，reseze减少有效元素个数后，it指向的位置元素已经被删除，迭代器失效，如果再使用该迭代器，则会出错。
七、vector与list对比
vector（动态顺序表）
list（带头结点的双向循环链表）
| 对比 | vector | list |
|---|---|---|
| 底层结构 | 动态顺序表，连续空间 | 带头结点的双向循环链表 |
| 访问 | 支持随机访问，首地址+下标 | 不能随机访问，可通过find查找，访问随即元素时间复杂度O(N) |
| 插入删除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低 | 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1) |
| 空间利用率 | 底层为连续空间，不容易造成内存碎片，空间利用率较高，缓存利用率高。可以一次将一个数据附近的空间都加载到缓存，不用频繁地从内存读取数据 | 底层节点动态开辟，容易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭代器 | 原生态指针 | 对指针进行了封装 |
| 迭代器失效 | 容量相关的操作都有可能导致迭代器失效，如插入引起的扩容，删除元素等 | 插入元素不会导致迭代器失效，删除节点会导致，且只影响当前迭代器，其他迭代器不受影响 |
| 使用场景 | 不关心插入和删除效率，支持随机访问 | 大量插入和删除操作，不关心随机访问的场景 |
总结
以上为个人经验，希望能给大家一个参考，也希望大家多多支持编程网。
