算法逻辑：
1.新数据会插入到链表头
2.当缓存数据被访问，将该缓存数据移到链表头部
3.当新数据插入时达到缓存上限了，将尾部数据删除掉（也就是最近最少使用的），新数据放在头部。
利用Map进行节点定位，时间复杂度大大降低，利用双向链表实现LRUCache逻辑，便于频繁实现首尾节点的移除和更新。
#include<iostream> #include<map> using namespace std; typedef struct MyListNode { int key; int val; MyListNode* next; MyListNode* pre; MyListNode(int k, int v) :key(k), val(v), next(NULL), pre(NULL) {} //C++里可以这样来初始化结构体，如同一个构造函数 }MyListNode; class LRUCache { private: int m_capacity; //缓存容量 MyListNode* pHead; //头节点 MyListNode* pTail; //尾节点 map<int, MyListNode*> mp; //mp用来存数据，达到find为o(1)级别 public: LRUCache(int size) { m_capacity = size; pHead = NULL; pTail = NULL; } ~LRUCache() { map<int, MyListNode*>::iterator it = mp.begin(); for (; it != mp.end();) { delete it->second; //一定要注意，map释放内存时，先释放内部new的内存，再释放map的内存，先释放的是MyListNode节点内存 it->second = NULL;//节点指针指向空 mp.erase(it++); } delete pHead; pHead = NULL; delete pTail; pTail = NULL; } void remove(MyListNode* node) { if (node->pre == NULL) //若本身是头节点 { pHead = node->next;//将头节点连接到其下一个节点node->next pHead->pre = NULL; } else if (node->next == NULL) //若本身是尾节点 { pTail = node->pre; //新尾节点为node->pre pTail->next = NULL; } else { node->pre->next = node->next; node->next->pre = node->pre; } } void sethead(MyListNode* node) { node->next = pHead; node->pre = NULL; if (pHead == NULL) { pHead = node; } else { pHead->pre = node; pHead = node; } if (pTail == NULL) { pTail = pHead; } } void Set(int key, int value) { map<int, MyListNode*>::iterator it = mp.find(key);//找到key值则返回key所在的节点，否则返回mp.end() if (it != mp.end()) { MyListNode* node = it->second; node->val = value; remove(node); sethead(node); } else { MyListNode* node = new MyListNode(key, value);//没有找到键值就创建一个新节点 int len = this->gtesize(); if (len >= m_capacity) { map<int, MyListNode*>::iterator it = mp.find(pTail->key); //这里寻找尾节点位置为了快速定位才在MyListNode结构体中定义了Key //否则需要遍历整个双向链表才能找到尾节点 remove(pTail); delete it->second; //如果大于设定缓存大小，则删除尾节点 ，同样要先释放节点内存，再释放map内存 mp.erase(it); } sethead(node); mp[key] = node; } } int Get(int key) { map<int, MyListNode*>::iterator it = mp.find(key);//找到key值则返回key所在的节点，否则返回mp.end() if (it != mp.end()) { MyListNode* Node = it->second; remove(Node); //移除节点，不是删除 sethead(Node); //将找到的节点放到首部 return Node->val; } else return -1; } int gtesize() { return mp.size(); } }; int main() { LRUCache* lru=new LRUCache(3); lru->Set(1, 3); cout<<lru->gtesize()<<endl; lru->Set(2, 4); cout<<lru->Get(3)<<endl; lru->Set(5, 6); cout<< lru->Get(2)<<endl; cout << lru->Get(5) << endl; cout << lru->gtesize()<<endl; lru->Set(4, 7); cout << lru->Get(4)<<endl; cout << lru->Get(1)<< endl; return 0; }
测试：
设置缓存大小为3：所以最多存储数据为3个
lru->Set(1, 3); 缓存里存有（1，3）这个节点数据
cout<<lru->gtesize()<<endl; 此时大小为1，只有一个节点存入
lru->Set(2, 4); 缓存里为（2，4）（1，3）两个节点，后存入的放在前面
cout<<lru->Get(3)<<endl; 在缓存里寻找key=3的节点，返回该节点的value，此时缓存里只有key=2,key=1的节点，所以返回 -1
lru->Set(5, 6); 此时缓存里为（5，6）（2，4）（1，3）三个节点，同样后存入的放在前面
cout<< lru->Get(2)<<endl; 在缓存里寻找key=2的节点，返回该节点的value，所以输出为key=2对应的value=4;注意这里使用了（2，4），所以缓存内要把这个节点移到最前面
所以此时缓存内容为（2，4）（5，6）（1，3）
cout << lru->Get(5) << endl; 在缓存里寻找key=5的节点，返回该节点的value，所以输出为key=5对应的value=6;注意这里使用了（5，6），所以缓存内要把这个节点移到最前面
所以此时缓存内容为（5，6）（2，4）（1，3）
cout << lru->gtesize()<<endl; 此时大小为3，有三个节点存入
lru->Set(4, 7); 缓存里存有（4，7）这个节点数据，但缓存大小为3 已满，所以删除在缓存最末端的节点（1，3），把新插入的节点放最前面
所以此时缓存内容为（4，7）（5，6）（2，4）
cout << lru->Get(4)<<endl; 在缓存里寻找key=4的节点，返回该节点的value，输出value=7，该节点已经在最前面了，数据依旧是（4，7）（5，6）（2，4）
cout << lru->Get(1)<< endl; 在缓存里寻找key=1的节点，返回该节点的value，由于节点（1，3）已经被挤出缓存，所以返回为 -1