LRU缓存用unordered_map加list实现：get查哈希表并splice移至头部，put更新或插入并超容时删尾部；时间复杂度均为O(1)。

用 C++ 实现 LRU（Least Recently Used）缓存，核心是快速查找 + 快速移动“最近使用”项。标准做法是结合 std::unordered_map（O(1) 查找）和 std::list（O(1) 头尾插入/删除，支持手动调整顺序），避免手写双向链表的复杂性。

数据结构设计：哈希表 + 双向链表

LRU 要求：
- get(key)：存在则返回值，并将该 key 移到“最近使用”位置（头部）；不存在返回 -1。
- put(key, value)：若 key 已存在，更新 value 并移到头部；若不存在，插入新节点；若容量满，先淘汰尾部（最久未用）节点。

关键点：
- std::list> 存键值对，头部为最近访问，尾部为最久未用。
- std::unordered_map>::iterator> 映射 key 到链表中对应节点的迭代器，实现 O(1) 定位。

put 操作：插入或更新 + 容量控制

执行步骤：
- 若 key 已存在：用 map 找到对应 list 迭代器，用 splice() 把该节点移到 list 开头，更新 value。
- 若 key 不存在：
  • 先检查是否超容（map.size() == capacity）：是则删掉 list 尾节点，并从 map 中移除其 key。
  • 然后在 list 头部插入新节点（push_front({key, value})），并将新节点迭代器存入 map。

get 操作：查表 + 提升热度

执行步骤：
- 在 map 中查找 key：
  • 找不到 → 返回 -1。
  • 找到 → 获取对应 list 迭代器，调用 splice(list.begin(), list, it) 将该节点移到开头，返回 value。

注意：不要用 erase + push_front，那样会额外分配内存；splice 是常数时间、原地移动，更高效。

完整可运行示例（C++11+）

不依赖外部库，仅用 STL：

class LRUCache {
    int cap;
    list> cache;
    unordered_map>::iterator> map;
public:
LRUCache(int capacity) : cap(capacity) {}
int get(int key) {
    if (map.find(key) == map.end()) return -1;
    auto it = map[key];
    cache.splice(cache.begin(), cache, it); // 移至头部
    return it->second;
}

void put(int key, int value) {
    if (map.find(key) != map.end()) {
        auto it = map[key];
        it->second = value;
        cache.splice(cache.begin(), cache, it);
        return;
    }
    if (cache.size() == cap) {
        auto last = cache.back();
        map.erase(last.first);
        cache.pop_back();
    }
    cache.push_front({key, value});
    map[key] = cache.begin();
}
};
立即学习“C++免费学习笔记（深入）”；
使用示例：
LRUCache lru(2);

lru.put(1, 1); // 缓存: [(1,1)]

lru.put(2, 2); // 缓存: [(2,2),(1,1)]

lru.get(1);    // 返回 1，缓存: [(1,1),(2,2)]

lru.put(3, 3); // 淘汰 2，缓存: [(3,3),(1,1)]
          


# ai 
# c++ 
# 键值对 
# red 
# int 
# 数据结构 
# map 
# 算法 
# 移到 
# 迭代 
# 不存在 
# 链表 
# 将该 
# 移至 
# 最久 
# 找不到 
# 均为 
# 并将 
 




相关栏目：
    【
        网站优化151355    】
    【
        网络推广146373    】
    【
        网络技术251813    】
    【
        AI营销90571    】




相关推荐：
Laravel如何实现API速率限制？（Rate Limiting教程） 
 弹幕视频网站制作教程下载,弹幕视频网站是什么意思？ 
Laravel怎么处理异常_Laravel自定义异常处理与错误页面教程 
 历史网站制作软件,华为如何找回被删除的网站？ 
php打包exe后无法访问网络共享_共享权限设置方法【教程】 
Laravel如何配置和使用队列处理异步任务_Laravel队列驱动与任务分发实例 
Angular 表单中正确绑定输入值以确保提交与验证正常工作 
Laravel事件和监听器如何实现_Laravel Events & Listeners解耦应用的实战教程 
如何用虚拟主机快速搭建网站？详细步骤解析 
Laravel模型关联查询教程_Laravel Eloquent一对多关联写法 
iOS中将个别页面强制横屏其他页面竖屏 
Laravel中DTO是什么概念_在Laravel项目中使用数据传输对象(DTO) 
如何在服务器上三步完成建站并提升流量？ 
微信小程序 canvas开发实例及注意事项 
高配服务器限时抢购：企业级配置与回收服务一站式优惠方案 
 西安专业网站制作公司有哪些,陕西省建行官方网站？ 
 ,网页ppt怎么弄成自己的ppt？ 
laravel怎么配置Redis作为缓存驱动_laravel Redis缓存配置教程 
Python结构化数据采集_字段抽取解析【教程】 
Laravel如何使用Guzzle调用外部接口_Laravel发起HTTP请求与JSON数据解析【详解】 
html文件怎么打开证书错误_https协议的html打开提示不安全【指南】 
绝密ChatGPT指令：手把手教你生成HR无法拒绝的求职信 
 合肥制作网站的公司有哪些,合肥聚美网络科技有限公司介绍？ 
laravel怎么用DB facade执行原生SQL查询_laravel DB facade原生SQL执行方法 
如何为不同团队 ID 动态生成多个独立按钮 
 潮流网站制作头像软件下载,适合母子的网名有哪些？ 
Android实现代码画虚线边框背景效果 
教你用AI将一段旋律扩展成一首完整的曲子 
如何在阿里云虚拟主机上快速搭建个人网站？ 
 公司门户网站制作公司有哪些,怎样使用wordpress制作一个企业网站？ 
php 三元运算符实例详细介绍 
Android自定义listview布局实现上拉加载下拉刷新功能 
Mybatis 中的insertOrUpdate操作 
Laravel怎么实现软删除SoftDeletes_Laravel模型回收站功能与数据恢复【步骤】 
用yum安装MySQLdb模块的步骤方法 
如何在VPS电脑上快速搭建网站？ 
黑客如何利用漏洞与弱口令入侵网站服务器？ 
进行网站优化必须要坚持的四大原则 
网站建设整体流程解析，建站其实很容易！ 
手机软键盘弹出时影响布局的解决方法 
宙斯浏览器怎么屏蔽图片浏览 节省手机流量使用设置方法 
如何自定义建站之星模板颜色并下载新样式？ 
UC浏览器如何切换小说阅读源_UC浏览器阅读源切换【方法】 
 深圳网站制作的公司有哪些,dido官方网站？ 
Python企业级消息系统教程_KafkaRabbitMQ高并发应用 
Python进程池调度策略_任务分发说明【指导】 
javascript中的try catch异常捕获机制用法分析 
Laravel如何使用Telescope进行调试？（安装和使用教程） 
百度浏览器网页无法复制文字怎么办 百度浏览器复制修复 
Laravel安装步骤详细教程_Laravel环境搭建指南