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)

/* ***********************************************
Author :111qqz
Created Time :2017年08月18日 星期五 00时00分22秒
File Name :LRU.cpp
 ************************************************ */

1class LRUCache{
2    private:
3    //map:<key,Value>
4    //Value:pair<value,time>
5    //time:vector? list?
6    typedef  unordered_map<int, pair<int , list<int>::iterator > >Cache;
7    Cache cache;
8    list<int>hit_seq; //头部最新元素，尾部最旧元素
9    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的最后访问时间

 1    }
 2    public:
 3    LRUCache(int capacity) 
 4    {
 5        siz = capacity;
 6    }
 7    int get(int key) 
 8    {
 9        auto it = cache.find(key);
10        if (it==cache.end()) return -1;
11        hit(it);
12        return it->sec.fst; 
13    }
14    void put(int key, int value) 
15    {
16        auto it = cache.find(key);
17        if (it != cache.end()) hit(it);
18        else
19        {
20        if (siz == cache.size())
21        {
22            cache.erase(hit_seq.back());
23            //淘汰hit序列最后的，也就是最旧的
24            hit_seq.pop_back();
25        }
26        hit_seq.push_front(key);
27        }
28        cache[key]=MP(value,hit_seq.begin());

    }
};