LRU——缓存管理算法

超、凢脫俗 2023-02-18 14:08 14阅读 0赞

**1.页面缓存管理算法**，即LRU算法是运用过去预测未来的一种算法，将过去访问量最高的页面资源保存到缓冲区的最前面，将最不常用的资源放在缓冲区最后面或者将之删除。  
**2.缓冲区的结构为了更好的在后期查找**，遍历最好使用键值对，哈希表等结构，查找时间复杂度为O(1),所以本文采用  
map + list的数据结构来当做数据缓冲区。

**LRUCzche.h**

//LRU算法  map+循环链表实现
    class LRUCache {
        
    public:
    	LRUCache(int size);
    	~LRUCache();
    	void InserNode(int key, int value);//插入数据，如果插入的数据原本存在，就直接适用并更新队列排序
    	void SetHead(ListNode_LRU* pNode);//将节点放在头部，将最近使用的节点放在队里头部
    	void Remove(ListNode_LRU* pNode);//移除节点
    	int Get(int key);//获取缓存里的数据
    	int GetSize();//获取存储容量
    private:
    	int m_capacity;//缓存容量
    	ListNode_LRU* pHead;//头节点
    	ListNode_LRU* pTail;//尾节点
    	map<int, ListNode_LRU*> mp;//map存储数据，搜索时间复杂度O(1)级别
    };

**LRUCache.cpp**

LRUCache::LRUCache(int size)//构造函数初始化缓存大小
    {
        
    	m_capacity = size;
    	pHead = NULL;
    	pTail = NULL;
    }
    
    LRUCache::~LRUCache()
    {
        
    	map<int, ListNode_LRU*>::iterator it = mp.begin();
    	for (;it != mp.end();)
    	{
        
    		delete it->second;
    		it->second = NULL;
    		mp.erase(it++);//注意：一定要这样写，it++ 放在其他任何一个地方都会导致其迭代器失效。
    	}
    	delete pHead;//只是删除了指针指向的内存空间
    	pHead = NULL;//防止野指针
    	delete pTail;
    	pTail = NULL;
    }
    
    void LRUCache::SetHead(ListNode_LRU* pNode)//将节点放在头部，将最近使用的节点放在队里头部
    {
        
    	pNode->pNext = pHead;//链表内存空间不是连续的，只需要把前后指针指向地址明确就行
    	pNode->pPre = NULL;
    	if (pHead == NULL)
    	{
        
    		pHead = pNode;
    	}
    	else {
        
    		pHead->pPre = pNode;
    		pHead = pNode;
    	}
    	if (pTail == NULL)
    	{
        
    		pTail = pHead;
    	}
    }
    
    void LRUCache::Remove(ListNode_LRU* pNode)//这里本不用这么麻烦，但是好像有点脑回路短路，逻辑上会有点问题，
    {
        
    	if (pNode->pPre == NULL && pNode->pNext != NULL)//如果是头节点
    	{
        
    		pHead = pNode->pNext;
    		pHead->pPre = NULL;
    	}
    	if (pNode->pNext == NULL && pNode->pPre != NULL)//如果是尾节点
    	{
        
    		pTail = pNode->pPre;
    		pTail->pNext = NULL;
    	}
    	if (pNode->pNext == NULL && pNode->pPre == NULL)
    	{
        
    		pHead = pNode;
    		pHead = NULL;
    	}
    	if (pNode->pNext != NULL && pNode->pPre != NULL)
    	{
        
    		pNode->pPre->pNext = pNode->pNext;
    		pNode->pNext->pPre = pNode->pPre;
    	} 
    }
    
    void LRUCache::InserNode(int key,int value)//插入数据，如果插入的数据原本存在，就直接适用并更新队列排序
    {
         //map中的key值不能有重复，只能是唯一的
    	map<int, ListNode_LRU*>::iterator it = mp.find(key);//找到key值的value值，如果没有找到则返回mp.end()
    	if (it != mp.end())
    	{
        
    		ListNode_LRU* Node = it->second;//it->first 是指向key值，it->second是指向value值，pair<key,value>;
    		Node->m_value = value;
    		Remove(Node);//先移除掉，之后再放至头节点处
    		SetHead(Node);
    	}
    	else {
        
    		ListNode_LRU* NewNode = new ListNode_LRU(key, value);
    		if (mp.size() >= m_capacity)//插入新节点判断是否超过存储容量
    		{
        
    			map<int, ListNode_LRU*>::iterator it = mp.find(pTail->m_key);//尾节点
    			Remove(pTail);//移除尾节点，插入新节点
    			delete it->second;
    			mp.erase(it);
    		}
    		SetHead(NewNode);//放到头节点
    		mp[key] = NewNode;//map结构定位，方便以后查找O(1)，查找效率O(1)。
    	}
    }
    
    int LRUCache::Get(int key)//获取缓存里的数据
    {
        
    	map<int, ListNode_LRU*>::iterator it = mp.find(key);
    	if (it != mp.end())
    	{
        
    		ListNode_LRU* Node = it->second;
    		Remove(Node);
    		SetHead(Node);
    		return Node->m_value;
    	}
    	else {
        
    		return -1;
    	}
    }

main.cpp

int main()
    {
        
    	LRUCache *LRU = new LRUCache(5);
    	LRU->InserNode(1, 1);
    	LRU->InserNode(2, 2);
    	LRU->InserNode(3, 1);
    	cout << LRU->GetSize() << endl;
    	LRU->InserNode(4, 98);
    	LRU->InserNode(5, 10);
    	LRU->InserNode(6, 3);
    	cout << LRU->GetSize() << endl;
    	cout << LRU->Get(5) << endl;
    	for (size_t i = 1; i <= LRU->GetSize(); i++)
    	{
        
    		cout << LRU->Get(i) << endl;
    	}
    	return 0;
    }

运行结果：  
![在这里插入图片描述][20200618095403983.png]

[20200618095403983.png]: https://img-blog.csdnimg.cn/20200618095403983.png