一、std::list
（1）list与其适用场景
std::list 是 C++的STL（标准模板库）中的双向链表容器，支持高效的插入、删除操作，适用于频繁在容器中间插入或删除元素的场景。
特点：
- 双向链表（Doubly Linked List），支持双向迭代。
- 任意位置插入/删除效率高（
O(1)）。 - 不支持随机访问（
O(n)查找）。 - 遍历比
vector慢（由于链表节点分散存储）。
适用场景：
- 频繁插入/删除
- 不需要随机访问
- 链表结构（如 LRU 缓存）
（2）list vs vector
| 特性 | list（链表） | vector（动态数组） |
|---|---|---|
| 存储结构 | 双向链表（分散存储） | 连续内存（数组） |
| 插入/删除 | O(1) 任意位置插入/删除 | O(n) 位置插入/删除（尾部 O(1)） |
| 随机访问 | O(n)（不支持 [] 访问） | O(1)（支持 [] 访问） |
| 遍历性能 | 较慢（跳转指针） | 较快（CPU缓存友好） |
| 适用场景 | 频繁插入/删除 | 快速随机访问 |
list 在需要高效插入/删除的情况下比 vector 更合适，但如果需要频繁访问元素，vector 更优。
二、std::list 的常用函数
| 函数 | 作用 |
|---|---|
push_back(val) | 尾部插入元素 |
push_front(val) | 头部插入元素 |
pop_back() | 删除尾部元素 |
pop_front() | 删除头部元素 |
insert(pos, val) | 在指定位置插入元素 |
erase(pos) | 删除指定位置元素 |
remove(val) | 删除所有匹配的元素 |
size() | 获取链表大小 |
front() | 获取链表首元素 |
back() | 获取链表尾元素 |
clear() | 清空链表 |
empty() | 判断链表是否为空 |
sort() | 对链表排序 |
reverse() | 反转链表 |
unique() | 删除连续重复元素 |
merge(other_list) | 合并两个有序链表 |
| 迭代器函数 | 作用 |
begin() | 指向首元素 |
end() | 指向尾后位置 |
rbegin() | 指向末元素（反向遍历） |
rend() | 指向首元素前的位置（反向遍历） |
三、std::list的基本使用
(1) 插入与删除
示例：
#include <iostream>
using namespace std;
#include <list>int main() {list<int> myList;myList.push_back(10); // 尾部插入myList.push_front(5); // 头部插入myList.insert(++myList.begin(), 7); // 在第二个位置插入 7cout << "链表内容: ";for (int val : myList){cout << val << " "; // 5 7 10}cout << endl;myList.pop_back(); // 删除尾部元素myList.pop_front(); // 删除头部元素cout << "删除后: ";for (int val : myList){cout << val << " "; // 7}cout << endl;system("pause");return 0;
}
注意：
push_back(val)—— 尾部插入元素；pop_back()—— 删除尾部元素。push_front(val)—— 头部插入元素；pop_front()—— 删除头部元素。
(2) 删除特定值
示例：
#include <iostream>
using namespace std;
#include <list>int main() {list<int> myList = { 1, 2, 2, 3, 4, 2, 5 };myList.remove(2); // 删除所有 2for (int val : myList){cout << val << " "; // 1 3 4 5}cout << endl;system("pause");return 0;
}
(3) 排序与反转
示例：
#include <iostream>
using namespace std;
#include <list>void printList(list<int> L)
{for (int val : L){cout << val << " ";}cout << endl;
}int main() {list<int> myList = { 3, 1, 4, 1, 5, 9 };myList.sort(); // 默认升序printList(myList);myList.reverse(); // 反转printList(myList);system("pause");return 0;
}
注意：
sort()默认为升序排列，再执行reverse()后为逆序排列；
(4) 去重
示例：
#include <iostream>
using namespace std;
#include <list>void printList(list<int> L)
{for (int val : L){cout << val << " ";}cout << endl;
}int main() {list<int> myList = {1, 1, 2, 3, 2, 4, 5, 5, 6};printList(myList);myList.unique(); // 仅删除相邻的重复元素printList(myList);system("pause");return 0;
}
注意：
myList.unique()删除链表myList中的连续重复元素（连续重复时，只保留一个副本）。
四、std::list 的应用
(1) LRU（最近最少使用）缓存
LRU（Least Recently Used） 是一种基于访问时间排序的缓存淘汰策略，
其核心思想是：最近被访问的数据在未来被访问的概率更高，因此当缓存容量满时，优先淘汰最久未被使用的数据。
示例：
#include <iostream>
using namespace std;
#include <list>
#include <unordered_map>class LRUCache {
public:LRUCache(int cap) : capacity(cap) {}void access(int key){if (cacheMap.find(key) != cacheMap.end()){cacheList.erase(cacheMap[key]); // 若重复访问，删除最早访问记录，保留最近访问记录}else if (cacheList.size() == capacity){int last = cacheList.back();cacheList.pop_back(); // 若达到容量限制，删除最近最少使用的数据cacheMap.erase(last);}cacheList.push_front(key);cacheMap[key] = cacheList.begin();}void print(){for (int val : cacheList){cout << val << " ";}cout << endl;}private:int capacity; // 缓存空间的最大容量list<int> cacheList; // 缓存数据unordered_map<int, list<int>::iterator> cacheMap; // 访问记录
};int main() {LRUCache cache(3);cache.access(1);cache.access(2);cache.access(3);cache.access(4); // 1 被淘汰cache.access(2);cache.print(); // 2 4 3system("pause");return 0;
}
注意：
LRUCache cache(3);中链表最大容量为3。- 连续访问数据1，2，3后，达到最大容量，继续访问数据4时，删除最近最少使用的数据1。
