LRU算法

@[toc](目 录)

1. LRU是什么

• LRU是least Recently Used（LRU） 的缩写，直译的话，称为“最近最少使用”，通常我们也叫做“最久未使用”——我是觉得这样更加贴切
• LRU算法，是一种类似Cache替换的算法。

  Cache一般就是一种缓存机制，比如说CPU和主存直接有快速存储的RAM，就是一个Cache，Cache主要用于存储速度相对相差较大的俩硬件之间，作为协调数据传输速度差异，Cache一般是有固定的大小的，不会太大，也不会太小，个中原因也是效率问题；

Cache容量有限，当容量告罄时再有新数据到来时，就会舍弃一部分已经存在的内容（根据某种算法依据），然后存放新到来的数据—对于LRU来说，就是舍弃掉最长时间灭有使用的那个数据，用新数据替换掉它

2.LRU的实现

2.1 考虑前提

• LRU需要实现快速的插入和删除
• LRU需要快速访问到需要的数据

  2.2 实现

  快速插入与删除，这里我采用 list标准容器， 快速访问选择了哈希map（unordered_map),关于LRU的实现有许多，我的code如下(运行环境 vs 2019）
  ```C++
  //LRU.hC
  #pragma once
  #include<unordered_map>
  #include<list>

class LRUCache {
public:
LRUCache(int capacity);

void put(int key, int value);
int get(int key); // 获取值

private:
int capacity; // 容量
std::list<std::pair<int, int>> list;
std::unorderedmap<int, std::list<std::pair<int, int>>::iterator> hashmap;
//将list的迭代器作为map的val值，为直接访问提供了好大的便捷
};

```C++
//LRU.cpp
#include"LRu.h"
#include<iostream>

using namespace std;

LRUCache::LRUCache(int capacity)
{
    capacity_ = capacity;
}
void LRUCache::put(int key, int value)
{
    auto hash_it = hashmap_.find(key);
    if (hash_it == hashmap_.end())
    {
        if (list_.size() >= capacity_)
        {
            hashmap_.erase(list_.back().first);
            list_.pop_back();
        }
        list_.push_front(make_pair(key, value));
        hashmap_[key] = list_.begin();
    }
    else {
        auto listits = hash_it->second;
        pair<int, int> val = *listits;

        list_.erase(listits);
        list_.push_front(val);
        hashmap_[key] = list_.begin();
    }
}
int LRUCache::get(int key)
{
    auto hash_it = hashmap_.find(key);
    if (hash_it == hashmap_.end())
    {
        cout << "can not find " << "key" << "in MAP" << endl;
        return -1;
    }
    auto listits = hash_it->second;
    pair<int, int> val = *listits;

    list_.erase(listits);
    list_.push_front(val);
    hashmap_[key] = list_.begin();
    std::cout << val.second << endl;
    return val.second;
}

```C++
//main.cpp
#pragma once
#include"LRu.h"
#include<iostream>

void test()
{
/
int ret;
//LRUCache lru_m(2);
ret = lru_m.get(1);
std::cout << ret << std::endl;
lru_m.put(1, 2);/
//LRUCache cache = new LRUCache(2);
LRUCache lru_m(2);
lru_m.put(1, 1);
lru_m.put(2, 2);

lru_m.get(1);
lru_m.put(3, 3);
lru_m.get(2);
lru_m.get(1);

}
int main()
{
test();
return 0;
}

### 2.3 结果如下：
![image.png](https://s2.51cto.com/images/20210803/1627995843304714.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=)
![image.png](https://s2.51cto.com/images/20210803/1627995985220954.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=)