1. list概述
std::list是C++标准模板库(STL)中的一个双向链表容器。与vector和deque不同，list不支持随机访问，但它在任何位置插入和删除元素都非常高效，时间复杂度为O(1)。
2. list的基本特性
-
双向链表结构：每个元素都包含指向前驱和后继的指针
-
高效插入删除：在任意位置插入/删除元素都很快
-
不支持随机访问：不能像数组一样通过下标直接访问元素
-
额外的内存开销：每个元素需要存储前后指针
3. 基本用法
3.1 包含头文件和声明
#include <list>// 声明一个int类型的list
std::list<int> myList;// 声明并初始化
std::list<int> initList = {1, 2, 3, 4, 5};3.2 常用构造函数
std::list<int> l1; // 空list
std::list<int> l2(5); // 包含5个元素，每个都是0
std::list<int> l3(5, 10); // 包含5个元素，每个都是10
std::list<int> l4(l3); // 拷贝构造
std::list<int> l5(l4.begin(), l4.end()); // 范围构造4. 常用操作
4.1 元素访问
std::list<int> nums = {1, 2, 3, 4, 5};// 访问首尾元素
std::cout << "第一个元素: " << nums.front() << std::endl;
std::cout << "最后一个元素: " << nums.back() << std::endl;// 注意：list没有operator[]和at()方法，不能随机访问4.2 添加元素
std::list<int> nums;// 在末尾添加
nums.push_back(10);
nums.emplace_back(20); // C++11, 更高效// 在开头添加
nums.push_front(5);
nums.emplace_front(1); // C++11, 更高效// 在指定位置插入
auto it = nums.begin();
advance(it, 2); // 将迭代器移动到第3个位置
nums.insert(it, 15);4.3 删除元素
std::list<int> nums = {1, 2, 3, 4, 5};// 删除首尾元素
nums.pop_front();
nums.pop_back();// 删除指定位置的元素
auto it = nums.begin();
advance(it, 1); // 移动到第2个元素
nums.erase(it); // 删除该元素// 删除所有值为3的元素
nums.remove(3);// 删除满足条件的元素
nums.remove_if([](int n) { return n > 4; }); // 删除大于4的元素4.4 大小和容量
std::list<int> nums = {1, 2, 3};std::cout << "大小: " << nums.size() << std::endl;
std::cout << "是否为空: " << (nums.empty() ? "是" : "否") << std::endl;
nums.resize(5); // 将大小改为5，新增元素为0
nums.resize(2); // 将大小改为2，删除多余元素5. 迭代器操作
std::list<int> nums = {1, 2, 3, 4, 5};// 正向遍历
for (auto it = nums.begin(); it != nums.end(); ++it) {std::cout << *it << " ";
}
std::cout << std::endl;// 反向遍历
for (auto it = nums.rbegin(); it != nums.rend(); ++it) {std::cout << *it << " ";
}
std::cout << std::endl;// C++11范围for循环
for (int num : nums) {std::cout << num << " ";
}
std::cout << std::endl;6. 特殊操作
6.1 排序
std::list<int> nums = {5, 3, 1, 4, 2};// 升序排序
nums.sort();// 降序排序
nums.sort(std::greater<int>());// 自定义排序
nums.sort([](int a, int b) {return a % 3 < b % 3; // 按模3的结果排序
});6.2 合并和拼接
std::list<int> list1 = {1, 3, 5};
std::list<int> list2 = {2, 4, 6};// 合并两个已排序的list
list1.sort();
list2.sort();
list1.merge(list2); // list1现在包含1,2,3,4,5,6，list2为空// 拼接list
std::list<int> list3 = {7, 8, 9};
list1.splice(list1.end(), list3); // 将list3的所有元素移动到list1末尾6.3 去重
std::list<int> nums = {1, 2, 2, 3, 3, 3, 4};nums.unique(); // 删除连续的重复元素，结果为1,2,3,4// 自定义去重条件
nums.unique([](int a, int b) {return abs(a - b) < 2; // 如果两元素差值小于2，视为相同
});7. 性能考虑
-
插入/删除：O(1)时间复杂度
-
访问元素：O(n)时间复杂度，需要遍历
-
排序：list有内置的sort方法，比通用算法std::sort更高效，因为它利用了链表特性
-
内存：每个元素需要额外存储两个指针，内存开销比vector大
8. 适用场景
-
需要频繁在中间位置插入/删除元素
-
不需要随机访问元素
-
需要频繁对容器进行排序、合并等操作
-
元素较大，移动成本高（因为list不需要像vector那样重新分配内存和移动元素）
9. 示例代码
#include <iostream>
#include <list>
#include <algorithm>int main() {// 创建并初始化liststd::list<int> numbers = {7, 5, 16, 8};// 添加元素numbers.push_back(25);numbers.push_front(3);// 插入元素auto it = numbers.begin();std::advance(it, 2);numbers.insert(it, 10);// 删除元素numbers.remove(16); // 删除所有值为16的元素// 遍历liststd::cout << "List内容: ";for (int n : numbers) {std::cout << n << " ";}std::cout << std::endl;// 排序numbers.sort();std::cout << "排序后: ";for (int n : numbers) {std::cout << n << " ";}std::cout << std::endl;return 0;
}10. 总结
std::list是C++中一个强大的双向链表容器，特别适合需要频繁插入删除但不需要随机访问的场景。它提供了丰富的成员函数来操作链表，包括排序、合并、去重等特殊操作。正确使用list可以显著提高程序的效率，特别是在处理大型数据集时。
