leetcode-LRUCache的解

因為要頻繁執行查詢插入删除等操作，是以考慮用hash表來做。

為了實作LRU，可以根據資料的最後使用時間維護一個堆，查找和調整都是O(lgn) ，沒有試過，不知道想法對不對。 

我采用的是雙連結清單+map的辦法，在表頭插，表尾删。

class LRUCacheValue;      

typedef pair<const int, LRUCacheValue> VTYPE;      

class LRUCacheValue      

{      

public:      

VTYPE * next;      

VTYPE * prev;      

LRUCacheValue(int v);      

LRUCacheValue():value(-1), next(NULL), prev(NULL){}      

~LRUCacheValue(){}      

int getValue() const;      

void setValue(int v);      

private:      

int value;      

};      

LRUCacheValue::LRUCacheValue(int v):value(v), next(NULL), prev(NULL)      

{      

}      

int LRUCacheValue::getValue() const      

{      

return value;      

}      

void LRUCacheValue::setValue(int v)      

{      

value = v;      

}      

class LRUCache{      

public:      

typedef map<int, LRUCacheValue> MAP;      

LRUCache(int capacity) {      

_capacity = capacity;      

vmap.clear();      

head = NULL;      

tail = NULL;      

}      

int get(int key)      

{      

MAP::iterator it = vmap.find(key);      

if(it != vmap.end())      

{      

int ret = it->second.getValue();      

update(it, ret);      

return ret;      

}      

return -1;      

}      

void set(int key, int value) {      

MAP::iterator it = vmap.find(key);      

if(it != vmap.end())      

{      

update(it, value);      

}      

else      

insert(key, value);      

}      

void update(MAP::iterator it, int value)      

{      

VTYPE *v = &*it;      

VTYPE *pre = v->second.prev;      

VTYPE *nex = v->second.next;      

v->second.setValue(value);      

if(pre != NULL)      

{      

pre->second.next = nex;      

v->second.next = head;      

head->second.prev = v;      

v->second.prev = NULL;      

head = v;      

if(nex != NULL)      

nex->second.prev = pre;      

else      

{      

tail = pre;      

}      

}      

}      

void insert(int key, int value)      

{      

if(vmap.size() >= _capacity)      

{      

VTYPE * old = tail;      

VTYPE* p = tail->second.prev;      

if(p != NULL)      

{      

p->second.next = NULL;      

tail = p;      

}      

vmap.erase(old->first);      

}      

pair<MAP::iterator, bool> ret = vmap.insert(make_pair(key, LRUCacheValue(value)));      

VTYPE *inserted = &*ret.first;      

if(head != NULL)      

{      

head->second.prev = inserted;      

inserted->second.next = head;      

head = head->second.prev;      

}      

else      

head = inserted;      

if(tail == NULL)      

tail = head;      

}      

private:      

unsigned int _capacity;      

MAP vmap;      

VTYPE* head;      

VTYPE* tail;      

};      

有一點之前沒有注意的是，查詢也應該更新查詢到的元素在連結清單中的位置。