C++ List 基本使用
基本概念
list 是一个序列容器，它内部维护了一个双向链表结构。与 vector 或 deque 等基于数组的容器不同，list 在插入和删除元素时不需要移动大量数据，因此在这些操作上具有较高的效率。然而，访问列表中的特定元素通常需要线性时间，因为 list 不提供随机访问迭代器。
list 动态分配内存，每个元素作为一个独立的节点，节点之间通过指针链接，这种结构使得插入和删除操作非常高效。
插入和删除操作
list 提供了多种插入和删除元素的方法，如 push_front, push_back, pop_front, pop_back, insert, erase 等，这些操作通常具有常数时间复杂度 O(1)。
list<int> lst;
lst.push_front(1); // 在列表前端插入元素
lst.push_back(2); // 在列表尾端插入元素
lst.insert(lst.begin(), 0); // 在迭代器指定位置插入元素
lst.erase(lst.begin()); // 删除迭代器指向的元素
lst.pop_front(); // 删除并返回列表前端的元素
lst.pop_back(); // 删除并返回列表尾端的元素
迭代器
list 提供双向迭代器，允许从任意方向遍历列表，而且在插入或删除元素时迭代器保持有效，这是与基于数组的容器如 vector 的主要区别之一。
典型用法
创建和初始化
#include <list>
#include <iostream>
int main() {
list<int> lst; // 创建一个空列表
list<int> lst2{1, 2, 3}; // 列表初始化
list<int> lst3(lst2.begin(), lst2.end()); // 区间初始化
list<int> lst4 = {4, 5, 6}; // 嵌入式初始化
return 0;
}
遍历列表
list<int> lst = {1, 2, 3};
for (auto it = lst.begin(); it != lst.end(); ++it) {
cout << *it << ' ';
}
// 或者使用范围for循环
for (const auto& elem : lst) {
cout << elem << ' ';
}
常用操作
| 方法 | 描述 |
|---|---|
| insert() | 它将新元素插入到迭代器指向的位置之前。 |
| push_back() | 它在容器的末尾添加了一个新元素。 |
| push_front() | 它在前面增加了一个新元素。 |
| pop_back() | 删除最后一个元素。 |
| pop_front() | 删除第一个元素。 |
| empty() | 它检查列表是否为空。 |
| size() | 它查找列表中存在的元素数。 |
| max_size() | 它找到列表的最大大小。 |
| front() | 它返回列表的第一个元素。 |
| back() | 它返回列表的最后一个元素。 |
| swap() | 当两个列表的类型相同时，它将交换两个列表。 |
| reverse() | 它反转了列表的元素。 |
| sort() | 它以递增的顺序对列表中的元素进行排序。 |
| merge() | 它合并两个排序的列表。 |
| splice() | 它将新列表插入到调用列表中。 |
| unique() | 它从列表中删除所有重复的元素。 |
| resize() | 它更改列表容器的大小。 |
| assign() | 它将一个新元素分配给列表容器。 |
| emplace() | 它将在指定位置插入一个新元素。 |
| emplace_back() | 它将在容器的末尾插入一个新元素。 |
| emplace_front() | 它将在列表的开头插入一个新元素。 |
性能考量
虽然 list 在插入和删除方面表现出色，但由于不支持随机访问，因此在需要频繁随机访问元素的场景中，vector 或 deque 可能是更佳选择。
vector vs list 深入解析与对比
内部结构
vector: 基于动态数组实现，优点：支持快速地通过索引随机访问任何元素很好的支持排序、二分查找、堆算法，时间复杂度为O(1)。缺点：插入或删除头部元素时效率较低最坏时间复杂度为O(n)，且空间不够后增容的代价较大。list: 是一个带头双向循环链表，优点：每个元素都是链表中的一个节点，节点之间通过指针连接。使得插入和删除操作在任何位置都非常高效，时间复杂度为O(1)；缺点：不支持随机访问，访问列表中的特定元素需要从头或尾遍历，最坏时间复杂度为O(n)。
迭代器行为
vector：当vector容量不足以容纳新的元素时，它会重新分配内存，将所有元素复制到新的内存空间。这个过程会使得之前所有指向vector的迭代器失效。list：迭代器在大多数情况下保持有效。只有当列表中的元素被删除或迭代器被显示重置时，受影响的迭代器才会失效。因为list中的元素都是独立的节点，插入删除操作只需要更新指针指向，不会影响其他节点的地址。
选择场景
vector：适用于需要频繁随机访问元素，且主要在容器尾部进行插入和删除操作的场景。list：适用于需要在容器任意位置高效插入和删除元素的场景，特别是在插入和删除操作频率高于随机访问的情况下。
vector和list是两个相辅相成互补的容器。
汇总
| vector | list | |
|---|---|---|
| 底层结构 | 动态顺序表，一段连续空间 | 带头结点的双向循环链表 |
| 随机访问 | 支持随机访问，访问某个元素效率O(1) | 不支持随机访问，访问某个元素效率O(N) |
| 插入和删除 | 任意位置插入和删除效率低，需要移位，时间复杂度为O(N)，插入时可能需要增容。增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低 | 任意位置插入和删除效率高，不需要移位元素，时间复杂度为O(1) |
| 空间利用率 | 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 | 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭代器 | 原生态指针 | 对原生态指针(节点指针)进行封装 |
| 迭代器失效 | 在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩展，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效 | 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响 |
| 使用场景 | 需要高效存储，支持随机访问，不关心插入删除率 | 大量插入和删除操作，不关心随机访问 |
实际应用示例
vector示例：
#include <vector>
#include <iostream>
using namespace std;
int main() {
std::vector<int> vec = { 1, 2, 3 };
vec.push_back(4); // 在末尾插入元素
cout << vec[2] << endl; // 随机访问元素
auto it = vec.begin() + 2; // 创建指向第3个元素的迭代器
cout << "头插前：" << *it << endl;
// 在向量开始插入元素
vec.insert(vec.begin(), 0);
// 此时，原先的迭代器it已失效，因为所有的元素都向后移动了一位
// 下面的代码将触发未定义的行为
// cout << "头插后：" << *it << std::endl;
// 正确的做法是重新定位迭代器
it = vec.insert(vec.begin(), 9); // 利用函数返回值重新指向有效迭代器
cout << "头插后：" << *it << endl;
return 0;
}
list示例：
#include <list>
#include <iostream>
using namespace std;
int main() {
list<int> lst = {1, 2, 3};
lst.push_front(0); // 在开头插入元素，迭代器有效
// 让迭代器指向第一个元素
auto it = lst.begin();
cout << "插入前：" << *it << endl;
lst.insert(lst.begin(), 4); // 在任意位置插入元素，迭代器有效
cout << "插入前：" << *it << endl;
return 0;
}
