Note: This article is available in Chinese only. 本文暂无英文版本。
View original
请实现最近最少使用缓存(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;
16
17 #define fst first
18 #define sec second
19 #define MP make_pair
20 void hit(Cache::iterator it) //access once
21 {
22 int key = it->fst;
23 hit_seq.erase(it->sec.sec);
24 hit_seq.push_front(key); //更新访问序列
25 it->sec.sec = hit_seq.begin(); //更新该key的最后访问时间
26
27 }
28 public:
29 LRUCache(int capacity)
30 {
31 siz = capacity;
32 }
33 int get(int key)
34 {
35 auto it = cache.find(key);
36 if (it==cache.end()) return -1;
37 hit(it);
38 return it->sec.fst;
39 }
40 void put(int key, int value)
41 {
42 auto it = cache.find(key);
43 if (it != cache.end()) hit(it);
44 else
45 {
46 if (siz == cache.size())
47 {
48 cache.erase(hit_seq.back());
49 //淘汰hit序列最后的，也就是最旧的
50 hit_seq.pop_back();
51 }
52 hit_seq.push_front(key);
53 }
54 cache[key]=MP(value,hit_seq.begin());
55
56 }
57};