ZBLOG

C++实现

下面是一个 C++ 中 LRU(Least Recently Used)缓存的实现示例。我们将使用 std::unordered_map 来存储键值对,同时用 std::list 来维护元素的顺序。

C++ 实现

  1. #include <iostream>
  2. #include <unordered_map>
  3. #include <list>
  4. class LRUCache {
  5. public:
  6. LRUCache(int capacity) : capacity(capacity) {}
  7. int get(int key) {
  8. if (cacheMap.find(key) == cacheMap.end()) {
  9. return -1; // 如果不存在,返回 -1
  10. }
  11. // 移动到最近使用的位置
  12. updateUsage(key);
  13. return cacheMap[key]->second;
  14. }
  15. void put(int key, int value) {
  16. if (cacheMap.find(key) != cacheMap.end()) {
  17. // 更新已存在的值并移动到最近使用的位置
  18. cacheMap[key]->second = value;
  19. updateUsage(key);
  20. } else {
  21. if (cacheList.size() >= capacity) {
  22. // 超出容量,移除最久未使用的项
  23. int lruKey = cacheList.back().first;
  24. cacheList.pop_back();
  25. cacheMap.erase(lruKey);
  26. }
  27. // 插入新项
  28. cacheList.push_front({key, value});
  29. cacheMap[key] = cacheList.begin();
  30. }
  31. }
  32. private:
  33. using Pair = std::pair<int, int>;
  34. std::list<Pair> cacheList; // 用于保持顺序的链表
  35. std::unordered_map<int, decltype(cacheList.begin())> cacheMap; // 存储键和对应列表位置的映射
  36. int capacity;
  37. void updateUsage(int key) {
  38. auto it = cacheMap[key];
  39. Pair item = *it;
  40. // 将当前项移除并重新插入到前面表示最近使用过
  41. cacheList.erase(it);
  42. cacheList.push_front(item);
  43. // 更新 map 中对应的迭代器位置
  44. cacheMap[key] = cacheList.begin();
  45. }
  46. };
  47. // 示例用法:
  48. int main() {
  49. LRUCache lru_cache(2); // 容量为2
  50. lru_cache.put(1, 1); // 缓存是 {1=1}
  51. lru_cache.put(2, 2); // 缓存是 {1=1, 2=2}
  52. std::cout << lru_cache.get(1) << std::endl; // 返回 1
  53. lru_cache.put(3, 3); // 淘汰键 2,缓存是 {1=1, 3=3}
  54. std::cout << lru_cache.get(2) << std::endl; // 返回 -1 (未找到)
  55. lru_cache.put(4, 4); // 淘汰键 1,缓存是 {3=3, 4=4}
  56. std::cout << lru_cache.get(1) << std::endl; // 返回 -1 (未找到)
  57. std::cout << lru_cache.get(3) << std::endl; // 返回 3
  58. std::cout << lru_cache.get(4) << std::endl; // 返回 4
  59. return 0;
  60. }

工作原理:

  • 使用 std::list 来保持元素的顺序,以便能够快速删除和插入元素。
  • 使用 std::unordered_map 保存每个键及其在链表中的位置,这样可以在 O(1) 的时间内访问。
  • get 方法中,当获取一个元素时,我们会将其标记为最近使用,通过将它从链表中删除并插入到头部来完成。
  • put 方法中,如果缓存达到最大容量,则移除最后一个(最不常用)元素。

这种实现方式同样提供了平均 O(1) 的时间复杂度,非常适合用于 LRU 缓存。


内容由零声教学AI助手提供,问题来源于学员提问

本站部分文章来源于网络,版权归原作者所有,如有侵权请联系站长删除。
转载请注明出处:https://golang.0voice.com/?id=21837

分享:
扫描分享到社交APP
上一篇
下一篇
发表列表
游客 游客
此处应有掌声~
评论列表

还没有评论,快来说点什么吧~

联系我们

在线咨询: 点击这里给我发消息

微信号:3007537140

上班时间: 10:30-22:30

关注我们
x

注册

已经有帐号?