leetcode 146. LRU Cache

浏览数：25 / 时间：2015年06月20日

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

为了查找高效O(1)，考虑使用哈希表hash，为了使插入/删除高效O(1)，考虑使用双链表list, 因此采用双链表和哈希表结合。

GET(key):

　　hash命中节点node，把node从list中移动到表头，否则返回-1

SET(key, value):

　　hash命中node，只需更新hash中的node，并把node从list中移动到表头。

　　hash不命中，则需要判断capacity. 如果cache满，需要替换cache中的node，并删除list的表尾元素，cache未满，将node插入表头，更新cache。

 1 struct CacheNode
 2 {
 3     int key;
 4     int value;
 5     CacheNode(int k, int v):key(k), value(v){}
 6 };
 7 
 8 class LRUCache{
 9 public:
10     LRUCache(int capacity) 
11     {
12         cacheSize = capacity;
13     }
14     
15     int get(int key) 
16     {
17         if (cacheMap.find(key) == cacheMap.end()) // hit fail
18             return -1;
19         cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
20         cacheMap[key] = cacheList.begin();
21         return cacheMap[key]->value;
22     }
23     
24     void set(int key, int value) 
25     {
26         if (cacheMap.find(key) == cacheMap.end()) // hit fail
27         {
28             CacheNode cacheItem(key, value);
29             if (cacheMap.size() == cacheSize) // cache is full
30             {
31                 cacheMap.erase(cacheList.back().key);
32                 cacheList.pop_back();
33             }
34             cacheList.push_front(cacheItem);
35             cacheMap[key] = cacheList.begin();
36         }
37         else    // hit success
38         {
39             cacheMap[key]->value = value;
40             cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
41             cacheMap[key] = cacheList.begin();
42         }
43     }
44     
45 private:
46     int cacheSize;
47     unordered_map<int, list<CacheNode>::iterator> cacheMap;
48     list<CacheNode> cacheList;
49 };