实现一个 LRU 风格的缓存类

embedded/2025/2/7 13:47:48/

实现一个缓存类

    • 需求描述
    • 豆包
      • 解决思路：
      • 实现代码：
      • 优化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/embedded/160313.html

相关文章

2023年总结感悟

2023年总结感悟

农民用铁锹挖土&#xff0c;和工程师用电流表测试电流其实是一样的。肌肉力量是男孩信息的源泉74岁时一个门槛&#xff0c;老人看一面就少看一面对于老人来说可以自己吃饭&#xff0c;自己走路已经很不错了&#xff0c;若是由于疾病预后很差&#xff0c;不如有尊严的离开世界护…
阅读更多...
HarmonyOS：给您的应用添加通知

HarmonyOS：给您的应用添加通知

一、通知介绍 通知旨在让用户以合适的方式及时获得有用的新消息&#xff0c;帮助用户高效地处理任务。应用可以通过通知接口发送通知消息&#xff0c;用户可以通过通知栏查看通知内容&#xff0c;也可以点击通知来打开应用&#xff0c;通知主要有以下使用场景&#xff1a; 显示…
阅读更多...
【Redis】主从模式，哨兵，集群

【Redis】主从模式，哨兵，集群

主从复制 单点问题&#xff1a; 在分布式系统中&#xff0c;如果某个服务器程序&#xff0c;只有一个节点&#xff08;也就是一个物理服务器&#xff09;来部署这个服务器程序的话&#xff0c;那么可能会出现以下问题&#xff1a; 1.可用性问题&#xff1a;如果这个机器挂了…
阅读更多...
C语言switch case语句详解（非常详细）

C语言switch case语句详解（非常详细）

在C语言中&#xff0c;switch case 语句是一种多分支选择结构&#xff0c;用于根据变量的值执行不同的代码块。 相比于if else语句&#xff0c;switch case在处理多个固定值的条件判断时更加简洁和高效。本文将详细讲解switch case语句的用法、语法格式、实例代码、注意事项&a…
阅读更多...
Hive修复分区

Hive修复分区

Hive修复分区 简介 Hive的MSCK REPAIR TABLE命令用于修复&#xff08;即添加丢失的&#xff09;表分区。通常用于那些已在HDFS中存在&#xff0c;但尚未在Hive元数据中注册的分区。 当你在HDFS文件系统中手动添加或删除分区目录&#xff0c;Hive并不会自动识别这些更改。为同步…
阅读更多...
网络安全——Span 安全监控

网络安全——Span 安全监控

SPAN释义&#xff1a; SPAN技术我们可以把交换机上某些想要被监控端口&#xff08;以下简称受控端口&#xff09;的数据流COPY或MIRROR一 份&#xff0c;发送给连接在监控端口上的流量分析仪&#xff0c;比如CISCO的IDS或是装SNIFFE工具的PC受控端口和 监控端口可以在同一台交…
阅读更多...
（2024|Nature Medicine，生物医学 AI，BiomedGPT）面向多种生物医学任务的通用视觉-语言基础模型

（2024|Nature Medicine，生物医学 AI，BiomedGPT）面向多种生物医学任务的通用视觉-语言基础模型

BiomedGPT: A generalist vision–language foundation model for diverse biomedical tasks 目录 1. 摘要 2. 引言 3. 相关研究 3.1 基础模型与通用生物医学 AI 3.2 生物医学 AI 的局限性 3.3 BiomedGPT 的创新点 4. 方法 4.1 架构及表示 4.1.1 模型架构选择 4.1.2 …
阅读更多...
LabVIEW自定义测量参数怎么设置?

LabVIEW自定义测量参数怎么设置?

以下通过一个温度采集案例&#xff0c;说明在 LabVIEW 中设置自定义测量参数的具体方法&#xff1a; 案例背景 ​ 假设使用 NI USB-6009 数据采集卡 和 热电偶传感器 监测温度&#xff0c;需自定义以下参数&#xff1a; 采样率&#xff1a;1 kHz 输入量程&#xff1a;0~10 V&a…
阅读更多...
最新文章

Copyright @ 2022~2023