高阶数据结构学习之LRU_Cache

1. 什么是LRU Cache

Cache：通常用于速度不相同的两个介质之间
例如：磁盘和内存，内存和cpu

LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法。
高效LRU Cache：任意操作都是O(1)

2. 相关题目

2.1 146. LRU 缓存题目链接

链接: 146. LRU 缓存

2.2 题目描述

2.2 代码

补充：
list一些库里面没有size，当访问size的时候，是遍历一遍链表
所以尽量不要使用list的size.
splice 将一个迭代器转移到另一个迭代器的前面

class LRUCache {
public:
    LRUCache(int capacity) 
        :_capacity(capacity)
    {}
    
    //查找
    int get(int key) {
        auto ret=_hashmap.find(key);
        if(ret!=_hashmap.end())
        {
            Liit it = ret->second;
            //splice 将一个迭代器转移到另一个迭代器的前面
            _list.splice(_list.begin(),_list,it);
            return it->second;
        }
        else
        {
            return -1;
        }
    }
    
    void put(int key, int value) {
        auto ret=_hashmap.find(key);
        if(ret==_hashmap.end())
        {
            //判断是否满了
            if(_capacity==_hashmap.size())
            {
                pair<int,int> back=_list.back();
                _hashmap.erase(back.first);
                _list.pop_back();
            }
            _list.push_front(make_pair(key,value));
            _hashmap[key]=_list.begin();
        }
        else
        {
            Liit it = ret->second;
            it->second=value;
            
            _list.splice(_list.begin(),_list,it);
        }
    }
private:
    typedef list<pair<int, int>>::iterator Liit;
    unordered_map<int, Liit> _hashmap;
    list<pair<int, int>> _list;
    size_t _capacity;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57