C++实现LRU缓存的思路与代码示例
LRU缓存通过哈希表和双向链表结合实现，get和put操作均O(1)时间复杂度，最近访问节点置于链表头部，满时淘汰尾部最久未用节点。
LRU缓存通过哈希表和双向链表结合实现，get和put操作均O(1)时间复杂度，最近访问节点置于链表头部，满时淘汰尾部最久未用节点。
LRU（Least Recently Used）缓存淘汰算法的核心思想是：当缓存满时，优先淘汰最久未使用的数据。为了高效实现，通常结合哈希表和双向链表，C++中可以用 unordered_map 和自定义的双向链表来完成。
基本思路
使用一个双向链表维护访问顺序，最近访问的节点放在链表头部，最久未访问的在尾部。同时用哈希表快速定位节点位置：
- get(key)：若存在，返回值并将该节点移到链表头；否则返回 -1
- put(key, value)：若已存在，更新值并移到头部；若不存在且缓存已满，删除尾部节点，插入新节点到头部
关键数据结构设计
定义双向链表节点和缓存容量：
struct ListNode {
int key, value;
ListNode *prev, *next;
ListNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
成员变量包括：
- 头尾指针：方便插入删除
- 哈希表：unordered_map
- 当前大小与最大容量
核心操作实现
封装两个辅助函数简化逻辑：
void removeNode(ListNode* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void addToHead(ListNode* node) {
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}
这两个函数用于调整节点位置，保证 O(1) 时间复杂度。
完整示例代码
#include#include using namespace std; class LRUCache { private: struct ListNode { int key, value; ListNode prev, next; ListNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {} };
int capacity; unordered_map<int, ListNode*> cache; ListNode *head, *tail; void removeNode(ListNode* node) { node->prev->next = node->next; node->next->prev = node->prev; } void addToHead(ListNode* node) { node->next = head->next; node->prev = head; head->next->prev = node; head->next = node; } void moveToHead(ListNode* node) { removeNode(node); addToHead(node); } ListNode* popTail() { ListNode* last = tail->prev; removeNode(last); return last; }public: LRUCache(int cap) { capacity = cap; head = new ListNode(0, 0); tail = new ListNode(0, 0); head->next = tail; tail->prev = head; }
int get(int key) { if (cache.find(key) == cache.end()) return -1; ListNode* node = cache[key]; moveToHead(node); return node->value; } void put(int key, int value) { if (cache.find(key) != cache.end()) { ListNode* node = cache[key]; node->value = value; moveToHead(node); } else { ListNode* newNode = new ListNode(key, value); cache[key] = newNode; addToHead(newNode); if (cache.size() > capacity) { ListNode* removed = popTail(); cache.erase(removed->key); delete removed; } } } ~LRUCache() { for (auto& pair : cache) { delete pair.second; } delete head; delete tail; }};
使用示例
int main() {
LRUCache lru(2);
lru.put(1, 1);
lru.put(2, 2);
cout << lru.get(1) << endl; // 输出 1
lru.put(3, 3); // 淘汰 key=2
cout << lru.get(2) << endl; // 输出 -1
return 0;
}
基本上就这些。用哈希表加双向链表，能保证 get 和 put 都是 O(1) 时间复杂度，符合 LRU 的高效要求。注意手动管理内存或改用智能指针避免泄漏。
详解如何在 Windows 电脑上通过 Microsoft Store 安装 Codex 桌面应用，包括启动登录、切换 Codex 模式、关联本地代码项目及终端环境配置的界面操作指引。
本文详解如何在Windows环境中使用PowerShell生成SSH密钥对，配置ssh-agent自动加载私钥，并将公钥安全添加至GitHub账户，最后通过git remote set-url切换为SSH地址，解决每次操作需输入账号密码的问题。
深入解析backdrop与background在网页开发及视觉设计中的区别。通过CSS代码示例，展示如何正确使用background设置元素背景，以及利用backdrop-filter创建弹窗遮罩模糊效果，避免概念混用。
详解 Windsurf IDE 在 Windows 系统的下载来源、安装步骤及首次启动界面。指导用户如何导入编辑器设置、打开项目文件夹及使用终端与 AI 功能，适合初次接触该工具的开发者阅读。
新手入门 ServBay 本地开发环境，详解安装包下载、Dashboard 状态监控、Packages 组件安装、Services 服务控制及 Websites 项目配置。掌握 .servbay.config 版本管理与日志排查技巧，快速搭建稳定的 PHP、Node.js 等多语言开发环境。
详解 CodeKit 在 macOS 下的安装步骤、项目导入方法、Sass与JavaScript编译设置及浏览器自动刷新功能，助您快速搭建高效的前端开发环境。
详解Windows环境下安装OpenAI Codex CLI的步骤，包括WSL环境检查、Node.js/npm配置、npm全局安装命令及首次启动验证，适合开发者快速上手。
学习如何配置 NativeRest REST API 客户端。涵盖 Windows/macOS/Linux 安装后的工作区创建、环境变量管理、请求编辑及响应查看步骤，帮助开发者快速完成基础环境搭建与连通性测试。
深入解析CSS中设置透明度的核心属性opacity，剖析子元素继承、事件穿透、层叠上下文等关键注意事项，并提供与rgba、hsla的实用选型对比。
WPS Office是一款面向macOS用户的综合办公套件，将文字处理、电子表格、演示文稿、PDF工具、模板与云协作整合在同一应用中。它兼容常见Microsoft Office格式，支持Intel及Apple芯片Mac，基础功能可免费使用，
Shapr3D是一款面向工业设计、机械工程、建筑概念和三维打印工作流的CAD软件。Mac版采用Parasolid建模内核，支持草图约束、实体建模、工程图、可视化渲染及常见CAD格式交换，并可通过账户在多台设备之间同步项目。
REAPER是Cockos开发的数字音频工作站，提供多轨音频与MIDI录制、剪辑、处理、混音和母带制作工具。Mac版兼容Intel与Apple芯片，支持AU、VST、VST3、CLAP等插件格式，并提供高度可定制的工作流程。
Adobe Photoshop 是面向摄影师、设计师和内容创作者的专业图像处理工具，可在 Windows 上完成照片修饰、选区抠图、图层合成、文字排版、绘画及生成式编辑。软件采用订阅授权，由 Creative Cloud 管理安装、更新与许
Adobe InDesign 是面向印刷与数字出版的专业页面排版工具，可制作书籍、杂志、宣传册、海报、交互式 PDF 和电子书。它提供精细的文字样式、多页面管理、印前检查及多格式输出能力，并能与 Photoshop、Illustrator
Adobe Illustrator 是用于绘制矢量图形、插画、图标、徽标和版式的专业设计工具。它以路径和锚点为核心，作品放大后仍能保持清晰，并提供画板、文字、渐变、图像描摹及精确变换等功能，适合品牌视觉、印刷物料、数字界面和商业插画创作。