leetcode 146. LRU Cache(list+unordered_map)

2017-08-18 · 1 min read · LRU

请实现最近最少使用缓存(Least Recently Used (LRU) cache)类,需要支持 get, set,操作。 get 操作,给出 key,获取到相应的 value (value 为非负数),如果不存在返回-1, 如果存在此 key 算作被访问过。 set 操作,设置 key,如果 key 存在则覆盖之前的 value (此时相当于访问过一次)。如果 key 不存在,需要进行插入操作,如果此时已经 key 的数量已经到达 capacity, 这样需要淘汰掉最近最少使用(也就是上次被使用的时间距离现在最久的)的那一项。

要求get和set的时间复杂度都是O(1)

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2017年08月18日 星期五 00时00分22秒
 4File Name :LRU.cpp
 5 ************************************************ */
 6
 7class LRUCache{
 8    private:
 9    //map:<key,Value>
10    //Value:pair<value,time>
11    //time:vector? list?
12    typedef  unordered_map<int, pair<int , list<int>::iterator > >Cache;
13    Cache cache;
14    list<int>hit_seq; //头部最新元素，尾部最旧元素
15    int siz;

 1        #define fst first 
 2        #define sec  second 
 3        #define MP make_pair
 4    void hit(Cache::iterator it) //access once
 5    {
 6        int key = it->fst;
 7        hit_seq.erase(it->sec.sec);
 8        hit_seq.push_front(key); //更新访问序列
 9        it->sec.sec = hit_seq.begin(); //更新该key的最后访问时间
10
11    }
12    public:
13    LRUCache(int capacity) 
14    {
15        siz = capacity;
16    }
17    int get(int key) 
18    {
19        auto it = cache.find(key);
20        if (it==cache.end()) return -1;
21        hit(it);
22        return it->sec.fst; 
23    }
24    void put(int key, int value) 
25    {
26        auto it = cache.find(key);
27        if (it != cache.end()) hit(it);
28        else
29        {
30        if (siz == cache.size())
31        {
32            cache.erase(hit_seq.back());
33            //淘汰hit序列最后的，也就是最旧的
34            hit_seq.pop_back();
35        }
36        hit_seq.push_front(key);
37        }
38        cache[key]=MP(value,hit_seq.begin());
39
40    }
41};