C++实现LRU（最久未使用）缓存算法

亦凉 2022-08-05 08:49 138阅读 0赞

LRU缓存算法也叫LRU页面置换算法，是一种经典常用的页面置换算法，本文将用C++实现一个LRU算法。

LRU算法实现并不难，但是要高效地实现却是有难度的，要想高效实现其中的插入、删除、查找，第一想法就是红黑树，但是红黑树也是一种折中的办法。插入、删除效率最高当属链表，查找效率当属hash。所以，这里我们就将链表和hash结合起来，利用空间换时间的思想，实现LRU算法。

LRU具体概念就不列出了，本文的目的是进一步了解LRU算法和学习高效的编程方法。

代码如下：

class LRUCache{
    private:
    	//LRU数据结构
    	struct Node{
    		int key;
    		int value;
    		Node(int k,int v):key(k),value(v){}
    	};
    public:
    	LRUCache(int c):capacity(c) {}
    	
    	int get(int key){
    		if (cacheMap.find(key) == cacheMap.end())
    			return -1; //这里产生缺页中断，根据页表将页面调入内存，然后set(key, value)
    		//将key移到第一个，并更新cacheMap 
    		cacheList.splice(cacheList.begin(),cacheList,cacheMap[key]);
    		cacheMap[key] = cacheList.begin();
    		return cacheMap[key]->value;
    	}
    	void set(int key, int value){
    		if (cacheMap.find(key) == cacheMap.end())
    		{
    			//淘汰最后一个，然后将其加到第一个位置
    			if (cacheList.size() == capacity)
    			{
    				cacheMap.erase(cacheList.back().key);
    				cacheList.pop_back();
    			}
    			cacheList.push_front(Node(key,value));
    			cacheMap[key] = cacheList.begin();
    		} 
    		else
    		{
    			//更新节点的值，并将其加到第一个位置
    			cacheMap[key]->value = value;
    			cacheList.splice(cacheList.begin(),cacheList,cacheMap[key]);
    			cacheMap[key] = cacheList.begin();
    		}
    	}
    private:
    	int capacity;
    	list<Node> cacheList;
    	unordered_map<int, list<Node>::iterator> cacheMap;
    };

实际算法并不难，但是高效解决问题的思想是值得学习的。也让我们更加了解LRU缓存算法了。