实现一个 LRU 风格的缓存类

实现一个缓存类

    • 需求描述
    • 豆包
      • 解决思路:
      • 实现代码:
      • 优化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;  // 输出 20
    cache.put(4, 40);  // 缓存已满,删除最早的元素 (1, 10)
    std::cout << cache.get(1) << std::endl;  // 输出 -1
    return 0;
}

优化1

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

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

2. 代码复用

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

优化后的代码
#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;  // 输出 20
    cache.put(4, 40);  // 缓存已满,删除最早的元素 (1, 10)
    std::cout << cache.get(1) << std::endl;  // 输出 -1
    return 0;
}
优化说明
  1. 引入 keyIterators 映射:用于存储每个键在 keyOrder 列表中的迭代器,这样在移动元素到列表末尾时,就可以直接通过迭代器删除元素,时间复杂度为 O ( 1 ) O(1) O(1)
  2. 提取 moveToBack 方法:将将键移到列表末尾的操作提取成一个单独的方法,提高了代码的复用性和可读性。

通过这些优化,getput 方法的时间复杂度都可以优化到 O ( 1 ) O(1) O(1)

优化2

1. 边界条件检查

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

2. 异常处理

在实际应用中,std::unordered_mapstd::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;  // 输出 20
        cache.put(4, 40);  // 缓存已满,删除最早的元素 (1, 10)
        std::cout << cache.get(1) << std::endl;  // 输出 -1
        std::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 实现了简单的线程安全机制,在关键操作(如 getputsizeempty 等)前加锁,确保多线程环境下的操作安全。

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%的性能损耗,在单线程场景中可以通过编译选项禁用锁机制(通过条件编译或模板策略)。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/965403.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

w192中国陕西民俗网的设计与实现

&#x1f64a;作者简介&#xff1a;多年一线开发工作经验&#xff0c;原创团队&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339;赠送计算机毕业设计600个选题excel文…

2.6日学习总结

题目一&#xff1a; AC代码&#xff1a; #include <stdio.h>// 宏 _for 用于简化 for 循环 #define _for(i, a, b) for (int i (a); i < (b); i)// 最大节点数 #define MAXN 1000010// 树节点结构体 typedef struct {int left;int right; } Node;// 树节点数组 Nod…

【数据结构】(4) 线性表 List

一、什么是线性表 线性表就是 n 个相同类型元素的有限序列&#xff0c;每一个元素只有一个前驱和后继&#xff08;除了第一个和最后一个元素&#xff09;。 数据结构中&#xff0c;常见的线性表有&#xff1a;顺序表、链表、栈、队列。 二、什么是 List List 是 Java 中的线性…

工控机的主要功能有那些?

工控机的主要功能包括&#xff1a;数据采集与处理&#xff0c;工控机可以连接多种传感器和输入设备&#xff0c;实时采集数据&#xff0c;并进行必要的处理和分析。其次 就是控制执行&#xff1a;在自动化生产线或机器人控制系统中&#xff0c;工控机根据预设的程序或实时数据执…

链式结构二叉树(递归暴力美学)

文章目录 1. 链式结构二叉树1.1 二叉树创建 2. 前中后序遍历2.1 遍历规则2.2 代码实现图文理解 3. 结点个数以及高度等二叉树结点个数正确做法&#xff1a; 4. 层序遍历5. 判断是否完全二叉树 1. 链式结构二叉树 完成了顺序结构二叉树的代码实现&#xff0c;可以知道其底层结构…

凝思60重置密码

凝思系统重置密码 - 赛博狗尾草 - 博客园 问题描述 凝思系统进入单用户模式&#xff0c;在此模式下&#xff0c;用户可以访问修复错误配置的文件。也可以在此模式下安装显卡驱动&#xff0c;解决和已加载驱动的冲突问题。 适用范围 linx-6.0.60 linx-6.0.80 linx-6.0.100…

MDPI的论文书写

一、作者信息 二、摘要 1、先写背景&#xff0c;将问题放到大背景里面&#xff0c;然后重点说明研究的目的。

2-kafka服务端之延时操作实现原理

文章目录 背景案例延时生产实现原理延时拉取实现原理 总结 背景 上篇我们说到了kafka时间轮是延时操作内部实现的重要数据结构&#xff0c;这篇我们来说下kafka内部的延时操作实现原理。这里我们以延时生产和延时拉取为例说明延时操作的实现原理。 案例 延时生产 我们知道如…

无心剑七绝《深度求索》

七绝深度求索 深研妙理定乾坤 度世玄机启智门 求路千难兼万险 索萦华夏自为尊 2025年2月1日 平水韵十三元平韵 无心剑七绝《深度求索》以平水韵十三元平韵写成&#xff0c;意境深远&#xff0c;气势磅礴。诗中“深研妙理定乾坤”开篇点题&#xff0c;展现出对深奥道理的钻研与探…

C++多级指针图解

AudioResample **pResample 指针的地址图解AudioResample **pResample; // pResample 存储 AudioResample* 的地址 AudioResample *ar *pResample; // ar 现在指向 AudioResample 结构体 pResample → 指向 AudioResample* 的地址 (0x2000)*pResample → 取出 AudioResample…

oracle基础语法

oracle基础语法 1、增删改查1.1查询语句1.2 修改语句1.3 删除表1.4 删除数据1.5 增加数据1.6 创建视图1.7 添加视图字段注释 1、增删改查 oracle与sql server语法上大致相同&#xff0c;但有些细微的不同&#xff0c;以下是我个人记录工作中常用到的一些语法句。 1.1查询语句…

数据库------------

一 mysql ----数据库就相当于一个端口 1. 三层结构 1&#xff09;数据库中 表的本质仍然是文件 1.1 mysql常用数据类型---&#xff08;即 mysql列类型&#xff09; 1&#xff09; 数值类型 2&#xff09; 文本类型 3&#xff09; 二进制数据类型 4&#xff09;日期类型 2. sq…

使用服务器部署DeepSeek-R1模型【详细版】

文章目录 引言deepseek-r1IDE或者终端工具算力平台体验deepseek-r1模型总结 引言 在现代的机器学习和深度学习应用中&#xff0c;模型部署和服务化是每个开发者面临的重要任务。无论是用于智能推荐、自然语言处理还是图像识别&#xff0c;如何高效、稳定地将深度学习模型部署到…

25/2/6 <机器人基础> 运动学中各连杆的变换矩阵求法

变换矩阵 机器人通常包含多个关节和连杆&#xff0c;每个关节和连杆都有自己的局部坐标系。变换矩阵能够将一个点或向量从一个坐标系转换到另一个坐标系&#xff0c;从而实现对机器人各个部件位置和姿态的统一描述 变换矩阵能够将复杂的运动分解为旋转和平移的组合。通过矩阵乘…

CS 与 BS 架构的差异

在数字化的今天&#xff0c;选择软件架构模式对系统的性能、维护、安全和成本都有很大影响。BS架构和CS架构是最常见的两种模式&#xff0c;了解它们的区别和特点对开发人员和企业决策者都很重要。 CS架构最早出现&#xff0c;当时用户直接从主机获取数据。随着客户端和服务端…

Vuex 解析:从 Vue 2 到 Vue 3 的演变与最佳实践

Vuex 是 Vue.js 中的状态管理模式&#xff0c;广泛应用于 Vue 2 和 Vue 3 中&#xff0c;其内部实现存在一些差异。 1. 什么是 Vuex &#xff1f; Vuex 是 Vue.js 官方提供的状态管理库&#xff0c;用于集中管理应用的所有组件的状态。主要是通过一种集中化的方式来管理共享状…

ip属地是手机号还是手机位置?一文理清

在数字化和网络化的今天&#xff0c;IP属地这一概念逐渐成为了人们关注的焦点。特别是在社交媒体和在线平台上&#xff0c;IP属地的显示往往让人联想到用户的地理位置。然而&#xff0c;关于IP属地到底与手机号还是手机位置有关&#xff0c;却存在着不少误解和混淆。本文将深入…

【C语言高级特性】预处理指令(二)

目录 一、取消宏定义&#xff08;#undef&#xff09; 1.1. 详细介绍 1.2. 代码示例 1.3. 使用场景 1.4. 注意事项 二、#line 指令 2.1. 详细介绍 2.2. 代码示例 2.3. 使用场景 2.4. 注意事项 三、#error 和 #warning 指令 3.1. #error 3.2. #warning 3.3 注意事项…

vim-plug的自动安装与基本使用介绍

vim-plug介绍 Vim-plug 是一个轻量级的 Vim 插件管理器&#xff0c;它允许你轻松地管理 Vim 插件的安装、更新和卸载。相较于其他插件管理器&#xff0c;vim-plug 的优点是简单易用&#xff0c;速度较快&#xff0c;而且支持懒加载插件&#xff08;即按需加载&#xff09; 自动…

华为支付-免密支付接入免密代扣说明

免密代扣包括支付并签约以及签约代扣场景。 开发者接入免密支付前需先申请开通签约代扣产品&#xff08;即申请配置免密代扣模板及协议模板ID&#xff09;。 华为支付以模板维度管理每一个代扣扣费服务&#xff0c;主要组成要素如下&#xff1a; 接入免密支付需注意&#x…