如何用c++实现一个简单的LRU缓存淘汰算法【算法实战】

LRU缓存用unordered_map+list实现：哈希表O(1)查key，链表O(1)维护时序；get时命中则移至头部并更新迭代器，未命中返回-1；put时存在则更新并前置，不存在且满容则删尾部再头插。

用C++实现LRU缓存，核心是让“最近最少使用”的元素自动被淘汰，关键在于快速查找 + 快速移动到最新位置。标准做法是：哈希表（unordered_map） + 双向链表（list）组合——哈希表提供O(1)查找，链表维护访问时序，且支持O(1)头插、尾删和任意节点摘除。

数据结构选型与设计逻辑

不能只用map或vector：map按key排序不反映访问顺序；vector删除中间元素是O(n)。而list是双向链表，erase一个迭代器是O(1)；unordered_map存key→list迭代器，就能在查到节点的同时，立刻把它移到链表头部（表示最新访问）。

缓存结构通常包含：

• 一个std::list<:p style="color:#f60; text-decoration:underline;" href="https://www.php.cn/zt/17539.html" target="_blank">air>：存(key, value)，头部为最新访问，尾部为最久未用
• 一个std::unordered_map::iterator>：通过key快速定位链表中对应节点
• 一个int capacity：最大容量，超限时删尾部节点

关键操作的实现要点

get(int key)：查map，存在则把对应节点移到list头部，更新map中该key的新迭代器，返回value；不存在返回-1。

立即学习“C++免费学习笔记（深入）”；

put(int key, int value)：

标签： ai c++ red