1 #include <bits/stdc++.h>
2 #include <unordered_map>
3 using namespace std;
4 class Cache {
5 private:
6 int maxlen; //缓存大小
7 unordered_map< int, pair<int, list<int>::iterator> > cache; //unordered_map 无序容器哈希表
8 list<int> recentlist; //双向链表维护
9 public:
10 Cache(int maxlen) {
11 this->maxlen = maxlen;
12 }
13 int get(int key) {
14 if (cache.find(key) == cache.end()) //缓存找不到，返回报错
15 return -1;
16 recentlist.splice(recentlist.begin(), recentlist, cache[key].second); //访问到了，将该结点放到list头部
17 return cache[key].first;
18 }
19 void put(int key, int value) {
20 if (cache.find(key) != cache.end()) { // 有这个值，则更新该值，并将该节点移到list头部
21 cache[key].first = value;
22 recentlist.splice(recentlist.begin(), recentlist, cache[key].second);
23 }
24 else { //没有这个值，则要插入到缓存中，一种情况是缓存满了，则把最近最少使用的移除，另一种情况是没满，则直接放进去即可
25 if (cache.size() == maxlen) {
26 int lastkey = recentlist.back();
27 cache.erase(lastkey);
28 recentlist.pop_back();
29 }
30 recentlist.push_front(key);
31 cache[key] = make_pair(value, recentlist.begin());
32 }
33 }
34 };
35
36 int main()
37 {
38 Cache newlist(2);
39 newlist.put(1, 2009);
40 newlist.put(2, 2010);
41 cout << newlist.get(1) <<endl; //2009
42 cout << newlist.get(2) << endl; //2010
43 cout << newlist.get(3) << endl; // -1
44 newlist.put(3, 2011);
45 cout << newlist.get(1) << endl; // -1
46 return 0;
47 }