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;
}