基于双向链表和hashmap的LRU算法实现
什么是LRU
LRU缓存淘汰算法就是一种常用策略。LRU的全称是Least Recently Used，也就是说我们认为最近使用过的数据应该是有用的，很久都没用过的数据应该是无用的，缓存满了就优先删除那些很久没有用过的数据。
代码
#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<stack>
using namespace std;
struct Node {
int data;
int key;
Node *nextNode;
Node *beforeNode;
};
struct MapLinkedList {
int fullNum;
int currentSize = 0;
Node *begin;
Node *last;
map<int, Node*> myMap;
};
void init(MapLinkedList *&mapLinkedList) {
mapLinkedList = new MapLinkedList();
mapLinkedList->begin = new Node();
mapLinkedList->fullNum = 10;
}
void destory(MapLinkedList *&mapLinkedList) {
Node *temp = mapLinkedList->begin->nextNode;
Node *temp_2;
cout << "开始清除垃圾" << endl;
while (temp!= NULL) {
temp_2 = temp;
cout << "清除 data：" << temp_2->data << " key：" << temp_2->key << "..."<<endl;
temp= temp->nextNode;
delete temp_2;
}
delete mapLinkedList;
cout << "清除完毕" << endl;
}
void visit(MapLinkedList *&mapLinkedList,int data,int key) {
Node *newNode=new Node;
newNode->data = data;
newNode->key = key;
newNode->nextNode = NULL;
if (mapLinkedList->currentSize == 0) {
cout << "当前容量为0" << endl;
mapLinkedList->last = newNode;
mapLinkedList->begin->nextNode = newNode;
newNode->beforeNode = mapLinkedList->begin;
mapLinkedList->myMap[key] = newNode;
mapLinkedList->currentSize++;
}
else if (mapLinkedList->myMap[key] != NULL) {
if (mapLinkedList->myMap[key] == mapLinkedList->last){
if (mapLinkedList->currentSize !=1) {
mapLinkedList->last = mapLinkedList->myMap[key]->beforeNode;
mapLinkedList->last->nextNode = NULL;
mapLinkedList->myMap[key]->nextNode = mapLinkedList->begin->nextNode;
mapLinkedList->begin->nextNode->beforeNode= mapLinkedList->myMap[key];
mapLinkedList->myMap[key]->beforeNode = mapLinkedList->begin;
mapLinkedList->begin->nextNode = mapLinkedList->myMap[key];
}
}
else {
mapLinkedList->myMap[key]->nextNode->beforeNode = mapLinkedList->myMap[key]->beforeNode;
mapLinkedList->myMap[key]->beforeNode->nextNode = mapLinkedList->myMap[key]->nextNode;
mapLinkedList->myMap[key]->nextNode = mapLinkedList->begin->nextNode;
mapLinkedList->begin->nextNode->beforeNode = mapLinkedList->myMap[key];
mapLinkedList->myMap[key]->beforeNode = mapLinkedList->begin;
mapLinkedList->begin->nextNode = mapLinkedList->myMap[key];
}
cout << "当前容器中存在对应key的元素，将对应key提到链表头部" << endl;
}
else if(mapLinkedList->currentSize<mapLinkedList->fullNum){
newNode->nextNode = mapLinkedList->begin->nextNode;
mapLinkedList->begin->nextNode->beforeNode = newNode;
mapLinkedList->begin->nextNode = newNode;
newNode->beforeNode = mapLinkedList -> begin;
mapLinkedList->myMap[key] = newNode;
mapLinkedList->currentSize++;
cout << "当前容器中没有新插入的元素，将新来的元素插入到链表头" << endl;
}
//超出最大容量
else {
//弹出最久未使用的块
mapLinkedList->myMap[mapLinkedList->last->key] = NULL;
Node* temp = mapLinkedList->last;
mapLinkedList->last->beforeNode->nextNode = NULL;
mapLinkedList->last = mapLinkedList->last->beforeNode;
delete temp;
mapLinkedList->currentSize--;
//插入新块
newNode->nextNode = mapLinkedList->begin->nextNode;
mapLinkedList->begin->nextNode->beforeNode = newNode;
mapLinkedList->begin->nextNode = newNode;
newNode->beforeNode = mapLinkedList->begin;
mapLinkedList->myMap[key] = newNode;
mapLinkedList->currentSize++;
cout << "当前容器的已装满，将最久未使用的key弹出链表" << endl;
}
cout << "插入节点成功，当前节点数为 " << mapLinkedList->currentSize << " ..."<<endl;
cout << "所有节点为：" << endl;
Node *temp = mapLinkedList->begin;
while (temp->nextNode != NULL) {
cout << "data:" << temp->nextNode->data << " key:" << temp->nextNode->key << endl;
temp = temp->nextNode;
}
cout << endl;
}
int main() {
MapLinkedList *mapLinkedList=NULL;
init(mapLinkedList);
int data;
int key;
cout << "LRU模拟 输入-1 -1结束.." << endl;
while (1) {
cout << "请输入data和key:";
cin >> data >> key;
if (data == -1 || key == -1) {
break;
}
visit(mapLinkedList, data, key);
}
destory(mapLinkedList);
return 0;
}