C++使用链表实现key-value存储，并且实现LRU策略

1单链表长度不超过LIMIT
2如果长度满，采用LRU（最旧记录丢弃）策略

set时往单链表的尾部插入数据，每次get时将get到的节点移动到链表尾部，因此链表尾部数据为最新数据，依次往前，链表头部为最旧数据。

代码如下

#include <string>
#include <iostream>
using namespace std;
struct ListNode
{
string key;
string value;
ListNode* next;
ListNode() : key(""), value(""), next(nullptr) {}
};
ListNode* kv= new ListNode();//定义整个链表头结点
ListNode* setpre = kv;//定义链表的尾部
int count = 0;//定义链表中已存储的数量
int LIMIT = 3;//链表的最大长度
string get(string key)//查询数据，并将查询到的数据移动到链表尾部
{
ListNode* getpre = kv;
ListNode* tmp = kv;
while (getpre !=nullptr)
{
if (getpre->key == key)
{
if (getpre == kv)
{
kv = kv->next;
}
else
{
tmp->next = tmp->next->next;
}
setpre->key = getpre->key;
setpre->value = getpre->value;
string value = getpre->value;
setpre->next = new ListNode();
setpre = setpre->next;
delete getpre;//释放被移动节点的内存
return value;
}
tmp = getpre;
getpre = getpre->next;
}
return "cant find this key";
}
int set(string key, string value)//插入新数据
{
if (count >= LIMIT)
{
kv = kv->next;
count --;
}
setpre->key = key;
setpre->value = value;
setpre->next = new ListNode();
setpre = setpre->next;
count ++;
return 0;
}
int main()
{
string action;
string key, value;
cout << "please enter set or get" << endl;
while (cin >> action)
{
if (action == "set")
{
cout << "please enter key" << endl;
cin >> key;
cout << "please enter value" << endl;
cin >> value;
int result=set(key, value);
if (result == 0)
cout << "set success" << endl;
cout << "please enter set or get" << endl;
}
if (action == "get")
{
cout << "please enter key" << endl;
cin >> key;
value = get(key);
cout << "result:" << value << endl;
cout << "please enter set or get" << endl;
}
}
return 0;
}

最后

以上就是纯真月光为你收集整理的C++使用链表实现key-value存储，并且实现LRU策略的全部内容，希望文章能够帮你解决C++使用链表实现key-value存储，并且实现LRU策略所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。