【题目】设计可以变更的缓存结构：该结构在构造时确定大小，假设大小为k，且有两个功能：
int set（string key，int value）：将记录（key，value）插入该结构
int get（string key）：返回key对应的value
要求：1. set和get时间复杂度为O(1)
2. 某个key的set/get操作一旦发生，认为这个key成为最常使用的
3. 当缓存大小超过k时，移除最不常用的记录。
结构设计思路：
k个固定大小的内存结构使用双向链表实现：
双向链表节点中的value即为消息记录的值value，且双向链表结构有头尾两个指针，头指针指向最长时间未使用的消息块（准淘汰位），尾指针指向最近使用过的消息块。满足get操作的O(1)复杂度：
使用hashmap来记录双向链表中消息key与节点的对应关系，发生get操作时就使用消息key作为key来查询消息是否在内存结构中，若在，则返回查询到的节点里的value值。如何维护双向链表满足LRU规则：
若双向链表为空，直接插入消息节点，且头尾指针均指向这个节点；插入节点时，若节点已经在链表中（查询O(1)），则将该节点的前后节点进行连接（O(1)），再将该节点插入尾指针之后（O(1)）；插入节点时，若节点不在链表中且缓存已满(hashmap的大小==k?)则删去头结点，并将该节点插入尾部，若缓存未满则直接插入尾部。
注意：在淘汰最长时间未使用的节点（即双向链表中的头结点）时，需要把（key→node）的hashmap进行同步更新，即根据头节点中存储的value值删除hashmap中对应的记录，为了满足O(1)时间复杂度，需要再准备一个hashmap2将node→key的对应关系存储下来。
删除过程：得到头节点head，根据head节点查找hashmap<node, k>，得到被淘汰的记录key值为k，然后同步删除hashmap<k,node>和hashmap<node,k>中的记录。
#include <iostream>
#include <unordered_map>
using namespace std;
struct Node{ //双向链表的节点
int value;
Node* last;
Node* next;
Node(int v):value(v){
last = NULL, next = NULL;
}
};
class doubleLinkList{ //双向链表结构
Node* head;
Node* tail;
public:
doubleLinkList(){
head = NULL;
tail = NULL;
}
//双向链表结构主要有三个方法：添加节点 & 将最近get的节点放到尾部 & 移除最长时间未使用的头节点
void addNode(Node* n){
if(n == NULL) return ;
if(head == NULL){
head = tail = n;
return;
}
tail->next = n;
n->next = NULL;
n->last = tail;
tail = n;
}
void moveNodeToTail(Node* node){
if(node == tail) return;
if(node == head){
head = head->next;
head->last = NULL;
}
else{
node->last->next = node->next;
node->next->last = node->last;
}
node->next = NULL;
node->last = tail;
tail->next = node;
tail = node;
}
Node* removeHead(){
if(head == NULL) return NULL;
Node* ret = head;
if(head == tail){
head = tail = NULL;
}
else{
head->next->last = NULL;
head = head->next;
ret->next = NULL;
}
return ret;
}
};
class LRUCache{
int capacity;
doubleLinkList cacheList;
unordered_map<string,Node*> KeyToNode;
unordered_map<Node*,string> NodeToKey;
public:
LRUCache(int k):capacity(k){}
int get(string key){
int ret = -1;
if(KeyToNode.find(key) != KeyToNode.end()){
Node* node = KeyToNode[key];
cacheList.moveNodeToTail(node);
ret = node->value;
}
return ret;
}
//移除最长时间未使用的记录
void removeMostUnusedCache(){
Node* head = cacheList.removeHead(); //从链表结构取出要删除的记录
string keyToBeDeleted = NodeToKey[head]; // 根据node来获取消息的key
NodeToKey.erase(head);
KeyToNode.erase(keyToBeDeleted);
}
void set(string key, int value){
unordered_map<string,Node*>::iterator it = KeyToNode.find(key);
if(it != KeyToNode.end())
cacheList.moveNodeToTail(it->second);
else{
Node* node = new Node(value);
cacheList.addNode(node);
KeyToNode[key] = node;
NodeToKey[node] = key;
if(KeyToNode.size() == capacity + 1)
removeMostUnusedCache();
}
}
};
int main()
{
LRUCache testCache = LRUCache(3);
testCache.set("A",1);
testCache.set("B", 2);
testCache.set("C", 3);
cout << "testCache.get(B) = " << testCache.get("B") << endl;
cout << "testCache.get(A) = " << testCache.get("A") << endl;
testCache.set("D", 4);
cout << "testCache.get(D) = " << testCache.get("D") << endl;
cout << "testCache.get(C) = " << testCache.get("C") << endl;
return 0;
}
