LeetCode hot 力扣100 LRU 缓存
splice 是 C++ STL 的 std::list 提供的一个成员函数，用于高效地将一个或多个元素从一个链表移动到另一个链表，或在同一链表内重新排列元素。它不涉及数据的拷贝，而是直接修改链表节点的指针，因此操作非常高效。
splice 的功能
splice 可以在以下场景中使用：
1. 从同一个链表中移动元素到目标位置。
2. 从另一个链表中移动元素到当前链表。
函数签名
splice 有以下几种重载形式：
1. 移动整个链表：
void splice(iterator pos, list& other);
• pos: 要插入的位置。
• other: 将整个链表 other 插入到当前链表的 pos 位置。
2. 移动单个元素：
void splice(iterator pos, list& other, iterator it);
• pos: 要插入的位置。
• other: 元素来自的链表。
• it: 要移动的元素的迭代器。
3. 移动多个元素（范围）：
void splice(iterator pos, list& other, iterator first, iterator last);
• pos: 要插入的位置。
• other: 元素来自的链表。
• first 和 last: 范围 [first, last) 中的元素将被移动。
你的代码中的 splice
在以下代码中：
v.splice(v.begin(), v, idx[key]);
含义：
1. 参数含义：
• v.begin(): 当前链表 v 的起始位置（头部）。
• v: 当前链表本身。
• idx[key]: 指向 key 对应的链表节点的迭代器。
2. 操作：
将链表中 key 对应的节点从当前位置移动到链表头部。
为什么使用 splice：
• 这是一个 O(1) 的操作，因为 splice 不会创建或销毁节点，只会修改链表中节点的指针，直接完成移动。
• 这使得 LRU 缓存能够高效地调整最近使用元素的位置，而不需要拷贝或重建节点。
示例代码
移动单个元素：
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> l = {1, 2, 3, 4, 5};
auto it = next(l.begin(), 2); // 指向第三个元素（值为 3）
// 将第三个元素移动到链表的头部
l.splice(l.begin(), l, it);
for (int x : l) {
cout << x << " "; // 输出：3 1 2 4 5
}
return 0;
}
移动范围：
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> l1 = {1, 2, 3, 4, 5};
list<int> l2 = {10, 20, 30};
// 将 l1 中第 2 到第 4 个元素（[2, 3, 4]）移动到 l2 的尾部
l2.splice(l2.end(), l1, next(l1.begin(), 1), next(l1.begin(), 4));
for (int x : l2) {
cout << x << " "; // 输出：10 20 30 2 3 4
}
return 0;
}
总结
• splice 是 std::list 专有的成员函数，用于高效地移动链表节点。
• 它适用于重排链表元素或在不同链表之间移动数据。
• 在你的 LRU 缓存代码中，splice 将最近访问的元素（key）移动到链表头部，表示其是“最新使用”的。class LRUCache {
// 用于存储缓存数据的双向链表，存储键值对 (key, value)
list<pair<int, int>> v;
// 用于存储 key 对应在链表中的迭代器的哈希表
unordered_map<int, list<pair<int, int>>::iterator> idx;
// 缓存的最大容量
int capacity;
public:
// 构造函数，初始化缓存容量
LRUCache(int capacity) : capacity(capacity) {}
// 获取 key 对应的值
int get(int key) {
// 如果 key 不存在，返回 -1
if (idx.count(key) == 0) return -1;
// 将 key 对应的元素移动到链表的头部（表示最近使用）
v.splice(v.begin(), v, idx[key]);
// 返回 key 对应的值（位于链表头部）
return v.front().second;
}
// 插入或更新 key-value 对
void put(int key, int value) {
// 如果 key 已经存在
if (idx.count(key)) {
// 将 key 对应的元素移动到链表头部
v.splice(v.begin(), v, idx[key]);
// 更新链表头部的值
v.front().second = value;
} else {
// 如果 key 不存在，直接在链表头部插入新的 key-value 对
v.emplace_front(key, value);
// 将 key 与链表头部的迭代器关联
idx[key] = v.begin();
}
// 如果链表大小超过容量，移除最久未使用的元素（链表尾部）
if (v.size() > capacity) {
// 从哈希表中移除对应的 key
idx.erase(v.back().first);
// 从链表中移除尾部元素
v.pop_back();
}
}
};以下是注释版代码以及每行的解释：
代码解析
1. 成员变量：
• list<pair<int, int>> v：
• 一个双向链表，用来存储缓存中的数据对 (key, value)。
• 双向链表允许高效地在任意位置插入或删除元素。
• unordered_map<int, list<pair<int, int>>::iterator> idx：
• 用哈希表存储每个 key 在链表中的位置（迭代器）。
• 通过哈希表，get 和 put 操作可以快速定位链表中的元素。
• int capacity：
• 缓存的最大容量。
2. 构造函数：
• 初始化缓存的容量 capacity。
3. get 方法：
• 检查 key 是否存在于缓存中：
• 如果不存在，返回 -1。
• 如果存在，将对应的元素移动到链表头部，表示最近使用：
• 使用 v.splice 方法实现，时间复杂度为 。
• 返回该元素的值。
4. put 方法：
• 如果 key 已存在：
• 通过 idx[key] 快速定位到链表中的元素，将其移动到链表头部。
• 更新链表头部的值。
• 如果 key 不存在：
• 在链表头部插入新的 (key, value) 对。
• 将 key 和链表头部的迭代器存入 idx。
• 如果链表大小超过了缓存容量：
• 移除链表尾部的元素（最久未使用的元素）。
• 从 idx 中删除对应的 key。
5. 时间复杂度：
• get 操作：，因为哈希表定位和链表操作都是常数时间。
• put 操作：，同理。
6. 核心思想：
• 使用链表维护元素的使用顺序，头部是最近使用的，尾部是最久未使用的。
• 使用哈希表快速定位 key 在链表中的位置，从而高效实现 get 和 put 操作。
这段代码实现了一个 LRU (Least Recently Used) Cache，并且给出了一个输入序列和期望的输出序列。以下是整个程序的执行过程以及输出结果的计算逻辑。
输入
• 操作序列：
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
• 对应参数：
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
• 缓存容量为 2。
输出
• 预期结果：
[null, null, null, 1, null, -1, null, -1, 3, 4]
执行过程分析
操作 1：LRUCache(2)
• 初始化一个容量为 2 的 LRU 缓存。
• 输出：null（构造函数无返回值）。
操作 2：put(1, 1)
• 插入键值对 (1, 1)。
• 缓存状态：[(1, 1)]（最近使用的在前，容量未满）。
• 输出：null。
操作 3：put(2, 2)
• 插入键值对 (2, 2)。
• 缓存状态：[(2, 2), (1, 1)]（最近使用的在前，容量已满）。
• 输出：null。
操作 4：get(1)
• 访问键 1，值为 1。
• 将键 1 移动到链表头部，表示它是最近使用的。
• 缓存状态：[(1, 1), (2, 2)]。
• 输出：1。
操作 5：put(3, 3)
• 插入键值对 (3, 3)。
• 缓存已满，移除最久未使用的键 (2, 2)。
• 插入键 (3, 3) 到链表头部。
• 缓存状态：[(3, 3), (1, 1)]。
• 输出：null。
操作 6：get(2)
• 访问键 2，发现它不在缓存中。
• 输出：-1。
操作 7：put(4, 4)
• 插入键值对 (4, 4)。
• 缓存已满，移除最久未使用的键 (1, 1)。
• 插入键 (4, 4) 到链表头部。
• 缓存状态：[(4, 4), (3, 3)]。
• 输出：null.
操作 8：get(1)
• 访问键 1，发现它不在缓存中。
• 输出：-1。
操作 9：get(3)
• 访问键 3，值为 3。
• 将键 3 移动到链表头部，表示它是最近使用的。
• 缓存状态：[(3, 3), (4, 4)]。
• 输出：3。
操作 10：get(4)
• 访问键 4，值为 4。
• 将键 4 移动到链表头部，表示它是最近使用的。
• 缓存状态：[(4, 4), (3, 3)]。
• 输出：4。
总结
最终输出结果为：
[null, null, null, 1, null, -1, null, -1, 3, 4]
每一步操作严格按照 LRU 缓存的定义执行，符合期望结果。