[数据结构与算法]C++实现LRU缓存

1、LRU概念：

least recently used，最近最少使用是一种存页面置换算法；
缺页异常（缺页中断）：当 CPU 访问的页面不在物理内存时，便会产生?个缺页中断，请求操作系统将所缺页调入到物理内存。

在第4步找空闲页，找不到空闲页的话，就说明此时内存已满了，这时候，就需要页面置换算法选择?个物理页。
LRU 是通过历史的使用情况来推测要淘汰的页面。额外开销较大：需要寄存器和栈的硬件支持。
完全实现 LRU，需要在内存中维护?个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。

2、LRU实现

双向链表+哈希map；map存储数据实现查找效率O(1)；

双向链表实现逻辑：

1、新数据插入在链表头 。
2、缓存的数据被访问，把它移到链表头 。
3、新数据插入到上限，尾部数据删除，新数据放在头部。

struct ListNode       //双向链表节点结构体
{
	int Key;
	int Value;
	ListNode* pre;
	ListNode* next;
	
	ListNode(int key, int value) : Key(key),Value(value),pre(nullptr), next(nullptr) {}
	ListNode() : Key(0), Value(0), pre(nullptr), next(nullptr) {}
};

class LRU
{
private:
		int capacity;
		ListNode* head;        //头结点
		ListNode* tail;        //尾节点
		map<int, ListNode*>mp;
public:
		LUR(int size)       // 构造函数
		{
			capacity = size;
			head = new ListNode();
			tail = new ListNode();
			head->next = tail;
			tail->pre = head;
		}
		~LRU()   //析构
		{	
			if(head != nullptr){
				delete head;
				head == nullptr;
			}
			if(tail != nullptr){
				delete tail;
				tail ==NULL;
			}
			for (auto& a : mp) {
 				if (a.second != nullptr) {
 					delete a.second;
 					a.second = nullptr;
 				}
 			}
		}
		
		void Remove(ListNode* Node)  //移除，还没删除
		{	
				Node->pre->next = Node->next;
				Node->next->pre = Node->pre;
		}
		void Puthead(ListNode* node) //最近数据放在头部
		{
			node->pre = head;
            node->next = head->next;
            head->next->pre = node;
            head->next = node;
		}
		void moveToHead(ListNode* node)  //移动到头部
        {
            Remove(node);
            Puthead(node);
        }
        ListNode* removeTail()        //移除最后一个结点
        {
        	ListNode* node = tail->pre;
        	Remove(node);
        	return node;
    	}
    	
    	void Set(int key, int value)   //插入数据,存在只更新
		{
			if(mp.find(key) != mp.end())  // 存在只更新
			{
				ListNode* Node = mp[key];
				Node->Value = value;
 				moveToHead(Node);
				return;
			}
			else
			{
				ListNode* newNode = new ListNode(key, value);
				if(mp.size() >= capacity)
				{
					ListNode* removed = removeTail();
                	// 删除哈希表中对应的项
                	mp.erase(removed->Key);
                	// 防止内存泄漏
                	delete removed;
				}
				Puthead(newNode);
				mp[key] = newNode;
			}
		}
		int Get(int key)
		{
			if(mp.find(key) != mp.end())
			{
				ListNode* Node = mp[key];
				moveToHead(Node);        //最近访问放到头部
				return Node->Value;
			}
			else return -1;
		}
}