LRU缓存通过哈希表和双向链表结合实现，get和put操作均O(1)：哈希表映射key到链表节点，链表维护访问顺序，最近使用置头，满时删尾。
实现一个LRU（Least Recently Used）缓存的核心思路是：当缓存满时，优先淘汰最久未使用的数据。为了高效地完成插入、查找和更新操作，c++中通常结合哈希表（unordered_map）和双向链表（list）来实现。
1. LRU缓存的基本要求
一个LRU缓存需要支持以下两个核心操作：
- get(key)：如果键存在，返回对应的值，并将该键移到最近使用位置；否则返回 -1。
- put(key, value)：插入或更新键值对。如果超出容量，删除最久未使用的条目。
这两个操作的时间复杂度都应为 O(1)。
2. 数据结构选择
要达到 O(1) 的时间复杂度，可以这样设计：
立即学习“C++免费学习笔记（深入）”；
- unordered_map<int, list<pair<int, int>>::iterator>：用于快速定位某个 key 是否存在及其在链表中的位置。
- list<pair<int, int>>：双向链表存储键值对，最近使用的放在链表头部，最久未使用的在尾部。
这种组合既能快速查找，又能高效地移动和删除节点。
3. 实现代码示例
#include <iostream> #include <unordered_map> #include <list> class LRUCache { private: int capacity; std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cache; std::list<std::pair<int, int>> used; public: LRUCache(int cap) : capacity(cap) {} int get(int key) { auto it = cache.find(key); if (it == cache.end()) { return -1; } // 将当前访问的节点移到链表头部 used.splice(used.begin(), used, it->second); return it->second->second; } void put(int key, int value) { auto it = cache.find(key); if (it != cache.end()) { // 更新值并移到头部 it->second->second = value; used.splice(used.begin(), used, it->second); return; } // 插入新元素到链表头部 used.emplace_front(key, value); cache[key] = used.begin(); // 如果超过容量，删除尾部元素 if (cache.size() > capacity) { int lastKey = used.back().first; cache.erase(lastKey); used.pop_back(); } } };
4. 关键点说明
splice 是关键操作：它可以把链表中的某个迭代器指向的节点“剪切”并粘贴到另一个位置，不会导致迭代器失效，且时间复杂度为 O(1)。
- 每次 get 或 put 已存在的 key 时，都要调用 splice 将其移到链表头部。
- 新插入的元素直接加到头部，淘汰时从尾部移除。
- 哈希表保存的是 list 的 iterator，可以直接访问对应节点。
基本上就这些。这个实现简洁、高效，适合面试和实际项目中使用。注意边界情况处理，比如容量为 0 或重复插入等情况即可。不复杂但容易忽略细节。