LRU算法

Green

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）

//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::unordered_map<int, std::list<std::pair<int, int>>::iterator> hashmap_;
//将list的迭代器作为map的val值，为直接访问提供了好大的便捷
};

//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;
}

//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 结果如下：