1+ // 使用双向链表和哈希表共同实现
2+ // typedef 如果写在函数外部，作用范围就是本文件
3+ // 如果写在函数内，作用范围本函数
4+ // 如果写在类内，且是公有，就可以在类外用className::typename来调用，如果是私有，当然也就不行了
5+
6+ // Runtime: 120 ms, faster than 40.72% of C++ online submissions for LRU Cache.
7+ // Memory Usage: 40 MB, less than 32.93% of C++ online submissions for LRU Cache.
8+
9+ class LRUCache
10+ {
11+ public:
12+ LRUCache (int capacity)
13+ {
14+ maxSize = capacity;
15+ }
16+
17+ int get (int key)
18+ {
19+ auto iter = hashmap.find (key);
20+ if (iter == hashmap.end ())
21+ {
22+ return -1 ;
23+ }
24+ else
25+ {
26+ update (iter);
27+ return iter->second .first ;
28+ }
29+ }
30+
31+ void put (int key,int value)
32+ {
33+ auto iter = hashmap.find (key);
34+ if (iter == hashmap.end ())
35+ {
36+ if (hashmap.size () == maxSize)
37+ {
38+ int key = queue.back ();
39+ queue.pop_back ();
40+ hashmap.erase (key);
41+ }
42+
43+ queue.push_front (key);
44+ hashmap.insert (pair<int , pa>(key,pa (value, queue.begin ())));
45+ }
46+ else
47+ {
48+ iter->second .first = value;
49+ update (iter);
50+ }
51+ }
52+ private:
53+ typedef list<int >::iterator lit;
54+ typedef pair<int , lit> pa;
55+ private:
56+ void update (unordered_map<int , pa>::iterator iter)
57+ {
58+ int key = iter->first ;
59+
60+ queue.erase (iter->second .second );
61+
62+ queue.push_front (key);
63+
64+ iter->second .second = queue.begin ();
65+ }
66+ private:
67+ int maxSize;
68+ list<int > queue;
69+ unordered_map<int , pa> hashmap;
70+ };
71+
72+ /* *
73+ * Your LRUCache object will be instantiated and called as such:
74+ * LRUCache* obj = new LRUCache(capacity);
75+ * int param_1 = obj->get(key);
76+ * obj->put(key,value);
77+ */