来自LeetCode的一道题目，要求在O(1)时间实现带有LRU的Get，Set数据结构。
下面给出实现的方法：
Public需要实现的有，put; get; 构造函数；
Private需要实现的有，size；capacity；head，tail结点；hash表cache；poptail；moveToHead；removeNode；addNode;(通常的双向链表的实现方式)
下面给出代码：
class LRUCache {
public:
struct LRUNode{
int key;
int val;
LRUNode* pre;
LRUNode* next;
};
LRUCache(int capacity) {
this->size = 0;
this->capacity = capacity;
head = new LRUNode;
tail = new LRUNode;
head->next = tail;
tail->pre = head;
}
int get(int key) {
if(hash_table.count(key) == 0){
return -1;
}
else{
auto item = hash_table[key];
moveToHead(item);
return item->val;
}
}
void put(int key, int value) {
if(hash_table.count(key) == 0){
auto newNode = new LRUNode;
newNode->key = key;
newNode->val = value;
hash_table[key] = newNode;
addNode(newNode);
size++;
if(size > capacity){
popTail();
size--;
}
}
else{
hash_table[key]->val = value;
}
moveToHead(hash_table[key]);
}
private:
int size;
int capacity;
LRUNode* head;
LRUNode* tail;
unordered_map<int, LRUNode*> hash_table;
void popTail(){
auto node = tail->pre;
tail->pre = this->tail->pre->pre;
tail->pre->next = tail;
hash_table.erase(node->key);
delete node;
}
void moveToHead(LRUNode* node){
removeNode(node);
addNode(node);
}
void removeNode(LRUNode* node){
node->pre->next = node->next;
node->next->pre = node->pre;
}
void addNode(LRUNode* node){
node->next = head->next;
node->pre = head;
head->next = node;
node->next->pre = node;
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
