目录

1.什么是LRU Cache

2.LRU Cache的简单实现

成员变量

构造函数

查询数据（get(key)）

插入/更新数据（put(key, value)）

1.什么是LRU Cache

• LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法。
• 什么是 Cache？狭义的Cache指的是位于CPU和主存间的快速RAM， 通常它不像系统主存那样使用 DRAM技术，而使用昂贵但较快速的SRAM技术。 广义上的Cache指的是位于速度相差较大的两种 硬件之间， 用于协调两者数据传输速度差异的结构。
• 除了CPU与主存之间有Cache， 内存与硬盘 之间也有Cache，乃至在硬盘与网络之间也有某种意义上的Cache── 称为Internet临时文件夹或 网络内容缓存等
• Cache的容量有限，因此当Cache的容量用完后，而又有新的内容需要添加进来时， 就需要挑选 并舍弃原有的部分内容，从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用 的内容替换掉。其实，LRU译成最久未使用会更形象， 因为该算法每次替换掉的就是一段时间内 最久没有使用过的内容。

2.LRU Cache的简单实现

以讲解这题为切口进行实现

yjy146. LRU 缓存 - 力扣（LeetCode）

• 成员变量

    //表头元素表示最近最多使用，尾元素表示最近最少使用
    //链表插入删除O(1),更新LRU效率O(N)，先找到，再转移
    list<pair<int, int>> _LRUlist;
    typedef list<pair<int, int>>::iterator _Listiterator;
    unordered_map<int, _Listiterator> _hashMap;//查找更新O(1)，LRU不可实现
    int _capacity;

(1) _capacity表示缓存的容量

(2)

• 只用unordered_map，查找更新效率为O(1)，但是无法记录数据的频率，如果使用引用计数，又需要查找，效率低，难以实现LRU
• 让链表尾元素表示最近最少使用的数据就可以实现LRU，但是，查找更新的效率为O(N)
• 所以，_LRUlist存储数据，
  _hashMap实现关键字与链表中关键字对应数据的迭代器一一映射

• 构造函数

    LRUCache(int capacity) {
        _capacity = capacity;
    }

初始化成员变量_capacity 即可

• 查询数据（get(key)）

    int get(int key) {
        auto it = _hashMap.find(key);
        //找不到就返回-1
        if(it == _hashMap.end()) return -1;
        //找到了,返回之前，更新元素位置
        _LRUlist.splice(_LRUlist.begin(), _LRUlist, it->second);

        return it->second->second;
    }

_hashMap根据关键字key以O(1)的时间效率进行查找，

找不到返回-1，找到了就将数据更新到表头，再返回value值

• 在 C++ 中，std::list::splice() 是 std::list 的一个高效成员函数，用于在常数时间 O(1) 内移动链表中的元素或整个链表，无需拷贝或析构元素。它通过重新链接链表节点实现

1. 移动单个节点

   void splice(iterator position, list& other, iterator it);

   • 作用：将 other 链表中的节点 it 移动到当前链表的 position 位置。
   • 要求：it 必须是 other 的有效迭代器，position 可以属于 other，但是ji被移动的节点（或范围）不能包含 position 本身（即不能自引用）
2. 移动整个链表

   void splice(iterator position, list& other);

   • 作用：将 other 链表的所有元素移动到当前链表的 position 位置。
   • 结果：other 变为空链表。
3. 移动一个范围内的节点

   void splice(iterator position, list& other, iterator first, iterator last);

   • 作用：将 other 链表中 [first, last) 范围内的节点移动到当前链表的 position 位置。
   • 注意：[first, last) 必须是 other 的有效范围，且不能包含 position 的迭代器（避免自引用）。

• 插入/更新数据（put(key, value)）

void put(int key, int value)
 {
    auto ret = _hashMap.find(key);
    //找不到，表头插入，注意删除数据
    if (ret == _hashMap.end())
    {
        //删除数据

        //头插

    }
    else//找到了就更新
    {

    }
}

(1)插入、更新数据得先查找

(2)找不到就需要插入数据，但是缓存容量有限，得先考虑删除数据

if (_hashMap.size() == _capacity)
{
    //链表尾节点元素
    pair<int, int> back = _LRUlist.back();
    _hashMap.erase(back.first);
    _LRUlist.pop_back();
}

• 将链表尾元素视为最近最少使用的元素，所以删除尾元素
• 然后头插最新数据

            _LRUlist.push_front(make_pair(key, value));
            _hashMap[key] = _LRUlist.begin();

(2)找到了就更新value值，同时将数据转移到表头

            ret->second->second = value;
            _LRUlist.splice(_LRUlist.begin(), _LRUlist, ret->second);

ret->second表示链表中节点的迭代器

转载自CSDN-专业IT技术社区

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/zl_dfq/article/details/152506665