c++实现高速缓存Cache

• • 需求：
  • 分析：
  • 实现：

Cache对键值对进行存储，capacity为Cache最大容量
1.get(key)方法获取对应映射值，不存在返回-1；
2.put(key,value)方法插入键值对。

1.get()方法要经常获取对应值所以低层存储应该是hashMap；
2.要及时更新频次，每次使用过一个节点之后要更新频次，对于频次更新可以使用双向结构，每次插入首部，删除时直接删除尾部；常用的双向结构主要有双向队列，双向链表，队列可以满足put需求，但get方法使用完之后需要将该键值对更新至队首，队列对于该任务太过复杂。
3. 选用双向链表实现，链表节点中存储key，value以及链表前后节点的两个指针pre，next；

//定义双链表结构体
struct DoubleLinkedNode{
​	int val;
​	int key;
​	DoubleLinkedNode *pre;
​	DoubleLinkedNode *next;
	//定义结构体初始化方法
​	DoubleLinkedNode():key(0),val(0),pre(nullptr),nxt(nullptr);
​	DoubleLinkedNode(int x,int y):key(x),val(y),pre(nullptr),nxt(nullptr);
}

Class Cache{
private:
	//定义head,tail ：最新节点永远在head->next，频次最低的为tail->pre;
	//hashMap中存储key-键值对节点地址，可以快速访问对应节点
	//定义容量与当前使用内存
	unordered_maptempList;
	int capacity;
	DoubleLinkedNode *head;	
	DoubleLinkedNode *tail;
	int curSize;
public:
​	//构造函数完成 私有变量的初始化；
	Cache(int x):capacity(x),curSize(0){
		this->head = new DoubleLinkedNode();
		this->tail = new DoubleLinkedNode();
		this->head->next = this->tail;
		this->tail->pre = this->head;
	}
	//先来定义节点的操作
	//1.在首部插入
	void addNew(DoubleLinkedNode* x){
		head->next->pre = x;
		x->next = head->next;
		x->pre = head;
		head->next = x;
	}
	//2.在尾部删除
	//由于删除完还需要更新hashMap所以需要对所删除节点进行返回
	DoubleLinkedNode* removeTail(DoubleLinkedNode* x){
		DoubleLinkedNode* node = tail->pre;
		removeNode(tail);
		return node;
	}
	//3. 删除任意节点
	//更新操作其实可以理解为 先删除，再首部插入
	void removeNode(DoubleLinkedNode* x){
		node->pre->next = node->next;
		node->next->pre = node->pre;
	}
	//获取更新，不牵扯容量
	int get(int key){
		if(tempList.count(key)==0) return -1;
		DoubleLinkedNode* node = tempList[key];
		removeNode(node);
		addNew(node);
		return node->val;
	}
	//
	int put(int key,int val){
		if(tmpList.count(key)==0){
			DoubleLinkedNode* node = new DoubleLinkedNode(key,val);
			tmpList[key] = node;
			addNew(node);
			size++;
			if(size>capacity){
				//这里是唯一会产生内存泄露的地方
				//假设removeTail()为返回节点而直接返回node->key,而节点都是在put()方法中堆空间申请
				//所以删除节点的时候需要将其返回，再此处将节点delete，释放堆空间内存
				DoubleListNode* eraseNode = removeTail();
				tmpList.erase(key);
				delete (eraseNode);
				size--;
			}
		}else{
			DoubleLinkedNode* node = tmpList(key);
			removeNode(node);
			addNew(node);
		}		
	}
}