利用数组实现lru

article/2025/9/29 18:01:38

LRU主要包含两个函数，第一个插入一个页面，第二个获得一个页面

主要思路如下，当插入页面的时候，所有的页面向后移动一个单位（若果多出来一个元素舍弃掉），然后把这个页面放到数组首元素
当获得一个页面的时候，就便利数组，找到这个页面然后放到最前面

代码如下：

//页面
struct page
{int id;//...其他信息page(int _id) : id(_id) {}
};//LRU类
class Array_LRUCache {
private:vector<page*> ap;int length;int _capacity;private:void copy(int dst,int src,int len) //目标地址，原地址，复制的长度{//原地址小于目标地址的时候从后往前复制//原地址大于目标地址的时候从前往后复制if (src <= dst){int i = src + len - 1;int j = dst + len - 1;while (i >= src){ap[j] = ap[i];i--;j--;}}else{int i = src;int j = dst;while (i<src+len){ap[j] = ap[i];i++;j++;}}}public:Array_LRUCache(int capacity) : _capacity(capacity) ,length(0){ ap.resize(capacity, nullptr);	}void put(page *p){//元素已经满了，吧最后的元素去掉，然后这个元素放到前面if (length == _capacity){copy(1, 0, length - 1);ap[0] = p;}//元素没有满，吧元素统统向后移一位，然后这个元素放到前面else{copy(1, 0, length);length++;ap[0] = p;}}page* get(int id){for (int i = 0;i < length;i++){if (ap[i]->id == id){page* p = ap[i];copy(1, 0, i);ap[0] = p;return p;}}return nullptr;}void print(){for (int i=0;i<length;i++){page* p = ap[i];cout << p->id << " ";}cout << endl;}
};//测试一下：
int main()
{	Array_LRUCache lru(3);lru.put(new page(1));lru.print();lru.put(new page(2));lru.print();lru.put(new page(3));lru.print();lru.put(new page(4));lru.print();lru.get(2);lru.print();lru.get(2);lru.print();lru.get(4);lru.print();lru.get(5);lru.print();
}