实现一个 LRU 风格的缓存类

server/2025/2/9 2:03:25/

实现一个缓存类

    • 需求描述
    • 豆包
      • 解决思路：
      • 实现代码：
      • 优化1
        • 1. `std::list::remove` 的时间复杂度问题
        • 2. 代码复用
        • 优化后的代码
        • 优化说明
      • 优化2
        • 1. 边界条件检查
        • 2. 异常处理
        • 3. 代码封装性
        • 4. 线程安全
        • 优化后的代码示例
        • 优化说明
    • DeepSeek（深度思考R1）：
      • 代码实现
        • 实现说明：
      • 优化方案一：基础互斥锁版本
      • 优化方案二：读写锁版本（C++17+）
      • 优化分析说明：

需求描述

类似于Windows系统的 win 菜单最近打开功能模块，使用最近最少使用（LRU）的缓存淘汰策略，缓存可以设置最大容量。
get：获取缓存数据，不存在时返回 -1
put：新增或者更新缓存，当容量已满时，删除最早的数据，再插入

class UpdateCaching {public:UpdateCaching(int capacity){}int get(int key){}void put(int key ,int value){}
}

豆包

解决思路：

  1. 使用 std::unordered_map 存储键值对，以便快速查找和更新数据。（为啥使用 unordered_map 而不是 map）

  2. 使用 std::list 存储键的访问顺序，以便在容量满时删除最早的数据。

  3. 在 put 操作中：

    • 检查缓存是否已满，如果已满，删除 list 中的第一个元素，并从 unordered_map 中移除对应的键值对。
    • 将新元素添加到 unordered_map 中，并将键添加到 list 的末尾。

  4. 在 get 操作中：

    • 使用 unordered_map 查找键是否存在，如果存在，将键移到 list 的末尾，表示最近访问过。

实现代码：

#include <iostream>
#include <unordered_map>
#include <list>class UpdateCaching {
private:std::unordered_map<int, int> cache;std::list<int> keyOrder;int capacity;public:UpdateCaching(int cap) : capacity(cap) {}int get(int key) {if (cache.count(key) == 0) {return -1;}// 将访问的键移到列表末尾，表示最近使用过keyOrder.remove(key);keyOrder.push_back(key);return cache[key];}void put(int key, int value) {if (cache.count(key) > 0) {// 键已存在，更新值并将其移到列表末尾cache[key] = value;keyOrder.remove(key);keyOrder.push_back(key);return;}if (cache.size() >= capacity) {// 缓存已满，移除最久未使用的元素int oldestKey = keyOrder.front();keyOrder.pop_front();cache.erase(oldestKey);}// 插入新元素cache[key] = value;keyOrder.push_back(key);}
};int main() {UpdateCaching cache(3);cache.put(1, 10);cache.put(2, 20);cache.put(3, 30);std::cout << cache.get(2) << std::endl;  // 输出 20cache.put(4, 40);  // 缓存已满，删除最早的元素 (1, 10)std::cout << cache.get(1) << std::endl;  // 输出 -1return 0;
}

优化1

1. std::list::remove 的时间复杂度问题

在 get 和 put 方法中，使用 keyOrder.remove(key) 来移动元素到列表末尾。std::list::remove 的时间复杂度是 O ( n ) O(n) O(n)，因为它需要遍历整个列表来找到要删除的元素。可以通过维护一个指向每个键在列表中位置的映射，将这一操作的时间复杂度优化到 O ( 1 ) O(1) O(1)。

2. 代码复用

get 和 put 方法中都有将键移到列表末尾的操作，可以将这一操作提取成一个单独的方法，提高代码的复用性。

优化后的代码
#include <iostream>
#include <unordered_map>
#include <list>class UpdateCaching {
private:std::unordered_map<int, int> cache;std::unordered_map<int, std::list<int>::iterator> keyIterators;std::list<int> keyOrder;int capacity;// 将键移到列表末尾void moveToBack(int key) {auto it = keyIterators[key];keyOrder.erase(it);keyOrder.push_back(key);keyIterators[key] = --keyOrder.end();//更新映射容器中key对应的迭代器}public:UpdateCaching(int cap) : capacity(cap) {}int get(int key) {if (cache.count(key) == 0) {return -1;}// 将访问的键移到列表末尾，表示最近使用过moveToBack(key);return cache[key];}void put(int key, int value) {if (cache.count(key) > 0) {// 键已存在，更新值并将其移到列表末尾cache[key] = value;moveToBack(key);return;}if (cache.size() >= capacity) {// 缓存已满，移除最久未使用的元素int oldestKey = keyOrder.front();keyOrder.pop_front();cache.erase(oldestKey);keyIterators.erase(oldestKey);}// 插入新元素cache[key] = value;keyOrder.push_back(key);keyIterators[key] = --keyOrder.end();}
};int main() {UpdateCaching cache(3);cache.put(1, 10);cache.put(2, 20);cache.put(3, 30);std::cout << cache.get(2) << std::endl;  // 输出 20cache.put(4, 40);  // 缓存已满，删除最早的元素 (1, 10)std::cout << cache.get(1) << std::endl;  // 输出 -1return 0;
}
优化说明
  1. 引入 keyIterators 映射：用于存储每个键在 keyOrder 列表中的迭代器，这样在移动元素到列表末尾时，就可以直接通过迭代器删除元素，时间复杂度为 O ( 1 ) O(1) O(1)。
  2. 提取 moveToBack 方法：将将键移到列表末尾的操作提取成一个单独的方法，提高了代码的复用性和可读性。

通过这些优化，get 和 put 方法的时间复杂度都可以优化到 O ( 1 ) O(1) O(1)。

优化2

1. 边界条件检查

在构造函数中可以添加对 capacity 参数的检查，避免传入不合法的值（如负数），增强代码的健壮性。

2. 异常处理

在实际应用中，std::unordered_map 和 std::list 的操作可能会抛出异常（如内存分配失败），可以考虑添加异常处理机制，让代码在异常情况下能有更好的表现。

3. 代码封装性

可以提供一些额外的接口方法，如获取缓存当前大小、检查缓存是否为空等，方便调用者使用。

4. 线程安全

如果该缓存类要在多线程环境下使用，需要添加同步机制，保证线程安全。

优化后的代码示例
#include <iostream>
#include <unordered_map>
#include <list>
#include <mutex>class UpdateCaching {
private:std::unordered_map<int, int> cache;std::unordered_map<int, std::list<int>::iterator> keyIterators;std::list<int> keyOrder;int capacity;mutable std::mutex mtx;  // 用于线程安全的互斥锁// 将键移到列表末尾void moveToBack(int key) {std::lock_guard<std::mutex> lock(mtx);  // 加锁，在get或put中被调用时已经加锁了，且是同一个锁 mtx，不会再次进行真正的加锁操作auto it = keyIterators[key];keyOrder.erase(it);keyOrder.push_back(key);keyIterators[key] = --keyOrder.end();}public:// 构造函数添加边界检查UpdateCaching(int cap) : capacity(cap) {if (cap <= 0) {throw std::invalid_argument("Capacity must be a positive integer.");}}int get(int key) {std::lock_guard<std::mutex> lock(mtx);  // 加锁if (cache.count(key) == 0) {return -1;}// 将访问的键移到列表末尾，表示最近使用过moveToBack(key);return cache[key];}void put(int key, int value) {std::lock_guard<std::mutex> lock(mtx);  // 加锁if (cache.count(key) > 0) {// 键已存在，更新值并将其移到列表末尾cache[key] = value;moveToBack(key);return;}if (cache.size() >= capacity) {// 缓存已满，移除最久未使用的元素int oldestKey = keyOrder.front();keyOrder.pop_front();cache.erase(oldestKey);keyIterators.erase(oldestKey);}// 插入新元素cache[key] = value;keyOrder.push_back(key);keyIterators[key] = --keyOrder.end();}// 获取缓存当前大小size_t size() const {std::lock_guard<std::mutex> lock(mtx);  // 加锁return cache.size();}// 检查缓存是否为空bool empty() const {std::lock_guard<std::mutex> lock(mtx);  // 加锁return cache.empty();}
};int main() {try {UpdateCaching cache(3);cache.put(1, 10);cache.put(2, 20);cache.put(3, 30);std::cout << cache.get(2) << std::endl;  // 输出 20cache.put(4, 40);  // 缓存已满，删除最早的元素 (1, 10)std::cout << cache.get(1) << std::endl;  // 输出 -1std::cout << "Cache size: " << cache.size() << std::endl;std::cout << "Is cache empty? " << (cache.empty() ? "Yes" : "No") << std::endl;} catch (const std::exception& e) {std::cerr << "Exception: " << e.what() << std::endl;}return 0;
}

在多线程环境下使用：

// 线程函数，用于向缓存中插入数据
void insertData(UpdateCaching& cache, int start, int end) {for (int i = start; i < end; ++i) {cache.put(i, i * 10);}
}// 线程函数，用于从缓存中获取数据
void getData(UpdateCaching& cache, int start, int end) {for (int i = start; i < end; ++i) {int value = cache.get(i);if (value != -1) {std::cout << "Key: " << i << ", Value: " << value << std::endl;}}
}int main() {try {UpdateCaching cache(10);// 创建插入数据的线程std::thread insertThread1(insertData, std::ref(cache), 0, 5);std::thread insertThread2(insertData, std::ref(cache), 5, 10);// 创建获取数据的线程std::thread getThread1(getData, std::ref(cache), 0, 5);std::thread getThread2(getData, std::ref(cache), 5, 10);// 等待所有线程完成insertThread1.join();insertThread2.join();getThread1.join();getThread2.join();std::cout << "Cache size: " << cache.size() << std::endl;} catch (const std::exception& e) {std::cerr << "Exception: " << e.what() << std::endl;}return 0;
}
优化说明
  1. 边界条件检查：在构造函数中添加了对 capacity 参数的检查，如果传入的值不合法，会抛出 std::invalid_argument 异常。
  2. 异常处理：通过 try-catch 块捕获可能抛出的异常，并进行相应的处理，提高了代码的健壮性。
  3. 代码封装性：添加了 size() 和 empty() 方法，方便调用者获取缓存的当前大小和检查缓存是否为空。
  4. 线程安全：使用 std::mutex 实现了简单的线程安全机制，在关键操作（如 get、put、size、empty 等）前加锁，确保多线程环境下的操作安全。

DeepSeek（深度思考R1）：

代码实现

#include <list>
#include <unordered_map>
#include <algorithm>using namespace std;class UpdateCaching {
private:int max_capacity;list<pair<int, int>> cache_list;unordered_map<int, list<pair<int, int>>::iterator> cache_map;public:UpdateCaching(int capacity) {max_capacity = max(0, capacity); // 处理非法容量值}int get(int key) {auto it = cache_map.find(key);if (it == cache_map.end()) {return -1;}// 将访问的节点移动到链表头部cache_list.splice(cache_list.begin(), cache_list, it->second);return it->second->second;}void put(int key, int value) {if (max_capacity <= 0) return; // 容量为0时不操作auto it = cache_map.find(key);if (it != cache_map.end()) {// 更新已有值并移到头部it->second->second = value;cache_list.splice(cache_list.begin(), cache_list, it->second);return;}// 插入新数据if (cache_map.size() >= max_capacity) {// 删除最久未使用的数据int last_key = cache_list.back().first;cache_map.erase(last_key);cache_list.pop_back();}// 插入新数据到头部cache_list.emplace_front(key, value);cache_map[key] = cache_list.begin();}
};
实现说明：

  1. 数据结构选择：

    • 使用双向链表list维护访问顺序，最近访问的节点保持在链表头部
    • 使用哈希表unordered_map实现O(1)时间复杂度的查找操作

  2. 核心操作：

    • get操作：
      • 查找存在时，将节点移动到链表头部并返回值
      • 不存在时返回-1
    • put操作：
      • 已存在时更新值并移动到头部
      • 不存在时先检查容量，满时删除链表尾部元素
      • 插入新元素到链表头部并更新哈希表

  3. 边界处理：

    • 构造函数处理非法容量值（负数自动设为0）
    • 容量为0时缓存不可用
    • 正确处理链表空时的删除操作

  4. 时间复杂度：

    • get和put操作的时间复杂度均为O(1)
    • 链表操作使用splice实现节点移动，保证O(1)时间复杂度

在原有LRU缓存实现基础上，可以通过以下方案优化线程安全问题：

优化方案一：基础互斥锁版本

#include <list>
#include <unordered_map>
#include <mutex>class UpdateCaching {
private:int max_capacity;list<pair<int, int>> cache_list;unordered_map<int, list<pair<int, int>>::iterator> cache_map;mutable mutex cache_mutex; // 可变的互斥锁public:UpdateCaching(int capacity) : max_capacity(max(0, capacity)) {}int get(int key) {lock_guard<mutex> lock(cache_mutex); // 自动加锁if (auto it = cache_map.find(key); it != cache_map.end()) {cache_list.splice(cache_list.begin(), cache_list, it->second);return it->second->second;}return -1;}void put(int key, int value) {lock_guard<mutex> lock(cache_mutex);if (max_capacity <= 0) return;if (auto it = cache_map.find(key); it != cache_map.end()) {it->second->second = value;cache_list.splice(cache_list.begin(), cache_list, it->second);return;}if (cache_map.size() >= max_capacity) {cache_map.erase(cache_list.back().first);cache_list.pop_back();}cache_list.emplace_front(key, value);cache_map[key] = cache_list.begin();}
};

优化方案二：读写锁版本（C++17+）

#include <shared_mutex>class UpdateCaching {// ...其他成员同基础版...mutable shared_mutex rw_mutex; // 读写锁public:int get(int key) {shared_lock<shared_mutex> lock(rw_mutex); // 共享锁// ...原有逻辑...}void put(int key, int value) {unique_lock<shared_mutex> lock(rw_mutex); // 独占锁// ...原有逻辑...}
};

优化分析说明：

  1. 线程安全实现：

    • 使用std::mutex保护所有缓存操作
    • 通过lock_guard自动管理锁的生命周期
    • 读写分离版本采用shared_mutex提升读多写少场景性能

  2. 性能影响评估：

    方案读并发写并发适用场景
    普通互斥锁串行串行低并发通用场景
    读写锁并行读串行写读多写少的高并发场景

  3. 异常安全：

    • 所有容器操作保证基本异常安全
    • 使用RAII风格的锁管理确保不会死锁

  4. 扩展优化建议：

    // 示例：分段锁优化（适用于超高并发场景）
class SegmentedLRUCache {constexpr static int SEGMENTS = 16;array<mutex, SEGMENTS> segment_mutexes;array<UpdateCaching, SEGMENTS> segments;size_t get_segment(int key) {return hash<int>{}(key) % SEGMENTS;}
public:int get(int key) {auto seg = get_segment(key);lock_guard<mutex> lock(segment_mutexes[seg]);return segments[seg].get(key);}// 类似实现put方法...
};

建议根据实际使用场景选择优化方案：

  • 常规服务：基础互斥锁方案即可满足需求
  • 高频读取服务：升级到读写锁版本
  • 超大规模并发：考虑分段锁或无锁队列方案

需要特别注意：线程安全实现会带来约10%-30%的性能损耗，在单线程场景中可以通过编译选项禁用锁机制（通过条件编译或模板策略）。


http://www.ppmy.cn/server/166084.html

相关文章

力扣240 搜索二维矩阵 ll

力扣240 搜索二维矩阵 ll

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性&#xff1a; 每行的元素从左到右升序排列。每列的元素从上到下升序排列。 示例 1&#xff1a; 输入&#xff1a;matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,…
阅读更多...
C语言的物联网

C语言的物联网

C语言在物联网中的应用 物联网&#xff08;Internet of Things&#xff0c;IoT&#xff09;是一个通过网络将各种物理设备连接起来的系统&#xff0c;使其能够收集和交换数据。随着技术的进步&#xff0c;物联网已经走入了我们的日常生活&#xff0c;并在智能家居、智能城市、…
阅读更多...
使用Jenkins、K8S、Docker一键部署SpringCloud微服务

使用Jenkins、K8S、Docker一键部署SpringCloud微服务

集成Jenkins、Kubernetes&#xff08;K8S&#xff09;和Docker&#xff0c;实现一键部署SpringCloud微服务。以下是具体的步骤&#xff1a; 步骤一&#xff1a;配置Jenkins 首先&#xff0c;我们需要安装并配置Jenkins。Jenkins是一个开源的持续集成/持续部署工具&#xff0c;…
阅读更多...
C链表的一些基础知识

C链表的一些基础知识

一、链表的基本概念 链表是一种常见的线性数据结构&#xff0c;它由一系列节点组成&#xff0c;每个节点包含数据部分和指向下一个节点的指针&#xff08;单链表情况&#xff09;。通过指针将各个节点连接起来&#xff0c;与数组不同&#xff0c;链表在内存中的存储不是连续的…
阅读更多...
每日Attention学习21——Cascade Multi-Receptive Fields

每日Attention学习21——Cascade Multi-Receptive Fields

模块出处 [MICCAI 24] [link] TinyU-Net: Lighter Yet Better U-Net with Cascaded Multi-receptive Fields 模块名称 Cascade Multi-Receptive Fields (CMRF) 模块作用 轻量感受野块 模块结构 模块特点 起点使用PWConv(PointWise Convolution, 11卷积)压缩通道&#xff0c…
阅读更多...
PHP 调用 DeepSeek API 完整指南

PHP 调用 DeepSeek API 完整指南

简介 本文将介绍如何使用 PHP 调用 DeepSeek API&#xff0c;实现流式对话并保存对话记录。PHP 版本使用面向对象的方式实现&#xff0c;代码结构清晰&#xff0c;易于维护。 1. 环境准备 1.1 系统要求 PHP 7.0 或更高版本PHP cURL 扩展文件写入权限 1.2 项目结构 deepse…
阅读更多...
MySQL数据库入门到大蛇尚硅谷宋红康老师笔记 基础篇 part 7

MySQL数据库入门到大蛇尚硅谷宋红康老师笔记 基础篇 part 7

第07章_单行函数 函数在计算机语言的使用中贯穿始终&#xff0c;函数的作用是什么呢&#xff1f;它可以把我们经常使用的代码封装起来&#xff0c; 需要的时候直接调用即可。这样既 提高了代码效率&#xff0c;又 提高了可维护性。在 SQL 中我们也可以使用函数 对检索出来的数…
阅读更多...
deepseek API 调用-python

deepseek API 调用-python

【1】创建 API keys 【2】安装openai SDK pip3 install openai 【3】代码&#xff1a; https://download.csdn.net/download/notfindjob/90343352
阅读更多...
最新文章

Copyright @ 2022~2023