1. FIFO(First in First out) -- 先进先出
先来先服务的策略。如果一个数据最先进入缓存中，则应该最早淘汰掉。也就是说，当缓存满的时候，应当把最先进入缓存的数据给淘汰掉。（这个可以类比队列较好理解）
实现：核心：双向链表实现队列+ hashmap
利用一个双向链表保存数据，当来了新的数据之后便添加到链表末尾，如果Cache存满数据，则把链表头部数据删除，然后把新的数据添加到链表末尾，这样插入和删除都可以在O（1）时间内完成。在访问数据的时候，如果在Cache中存在该数据的话，则返回对应的value值；否则返回-1。访问效率为O（n），可以通过添加hashmap来提高访问速度达到O（logn）。
#include"head.h"//头文件在最后处#include<math.h>class FIFOCache{public:FIFOCache(int capacity){FIFOcapacity = capacity;FIFOsize = 0;list.Listcapcity = capacity;}int get(int key){if (!FIFOmap.count(key))return -1;Node* node = FIFOmap[key];return node->val;}void put(int key, int value){if (FIFOcapacity == 0)return;if (FIFOmap.count(key)){Node* node = FIFOmap[key];list.remove(node);node->val = value;list.append(node);}else{if (FIFOsize == FIFOcapacity){Node* node = list.pop();int x = node->val;map<int, Node*>::iterator it3 = FIFOmap.find(x);//通过find拿到 node.val 为关键字的的迭代器FIFOmap.erase(it3);--FIFOsize;}Node* node = new Node(value);list.append(node);FIFOmap[key] = node;++FIFOsize;}}void printFIFO(){list.printList();}//数据成员int FIFOsize;int FIFOcapacity;DoubleList list;map<int, Node*>FIFOmap;};
测试代码（FIFO）：
FIFOCache cache(2);cache.put(1,1);cache.printFIFO();cache.put(2, 2);cache.printFIFO();cout << cache.get(1) << endl;cache.put(3, 3);cache.printFIFO();cout << cache.get(2) << endl;cache.printFIFO();cache.put(4, 4);cache.printFIFO();cout << cache.get(1) << endl;
2. LFU（Least Frequently Used） -- 最近最少使用
基于“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”的思路。
LFU是基于访问次数的。（这里可以把LFU看作是FIFO的优化，数据在原有基础增添一新的数据成员，用以计数数据被访问次数，按照数据被访问计数进行“分组”，计数相同的数据分为一组，淘汰时，选取最计数组，按照FIFO方法淘汰首元素）
实现：核心：存放双向链表的hashmap
LFU可以视为按频率“分组”的FIFO算法，所以我们利用hashmap，key存放数据被访问频率，key对应的value存放key频率下的双向链表。这样淘汰数据时，只要找到最小频率组，再按照FIFO策略淘汰数据即可。同时需要一个hashmap存放，数据地址，加快查找。
访问数据命中，则从相应的双向链表中删除，插入下一频数的双向链表，若该频数双向链表不存在则创建并插入；若删除数据使得双向链表为空，则删除双向链表。
#include"head.h"#include<math.h>class LFUNode :public Node//新定义的LFUNode类继承Node类基础上，添加freq数据成员作为计数{public:LFUNode() {}LFUNode(int x){freq = 0;val = x;}int freq;};class LFUcache{public:LFUcache(int capacity){LFUcapacity = capacity;LFUsize = 0;}void update(LFUNode*node) //更新节点 每次get或者put 访问频率改变{int freq = node->freq;//删除LFUNode* node1 = NULL;node1=(LFUNode*)freq_map[freq]->remove(node); ///if (freq_map[freq]->Listsize == 0)//如果该节点为最后一个节点，则删除双向链表{map<int, DoubleList*>::iterator it = freq_map.find(freq);freq_map.erase(it);}//更新++freq;node1->freq = freq;if (freq_map.count(freq))//该频率已存在，则尾部加入{freq_map[freq]->append(node1);//static_cast<Node*>(node)}else //该频率未存在，则创建新双向链表插入{DoubleList* Dlist = new DoubleList();Dlist->append(node1);//freq_map[freq] = Dlist;}}int get(int key){if (!LFUmap.count(key))return -1;else{LFUNode* node = LFUmap[key];update(node);return node->val;}}void put(int key,int value){if (LFUcapacity == 0)return;if (LFUmap.count(key))//缓存命中{LFUNode* node = LFUmap[key];node->val = value;update(node);}else//缓存没有命中{if (LFUsize == LFUcapacity){Node* node = NULL;map<int, DoubleList*>::iterator it1 = freq_map.begin();node =it1->second->pop();map<int, LFUNode*>::iterator it2 = LFUmap.find(node->val);LFUmap.erase(it2);--LFUsize;}LFUNode* lfNode = new LFUNode(value);lfNode->freq = 1;LFUmap[key] = lfNode;if (!freq_map.count(lfNode->freq)){freq_map[lfNode->freq] = new DoubleList();}freq_map[lfNode->freq]->append(static_cast<Node*>(lfNode));//++LFUsize;}}void printLFU(){cout << "---------Start-------------------"<< endl;for (map<int ,DoubleList*>::iterator it= freq_map.begin(); it != freq_map.end(); ++it){cout << "Freq = " << it->first << " :" << endl;it->second->printList(); }cout << "---------End-------------------"<< endl<<endl;}int LFUsize;int LFUcapacity;map<int, DoubleList*>freq_map;map<int, LFUNode*>LFUmap;};
测试代码（LFU）：
LFUcache cache3(2);cache3.put(1, 1);cache3.printLFU();cache3.put(2, 2);cache3.printLFU();cout << cache3.get(1) << endl;cache3.printLFU();cache3.put(3, 3);cache3.printLFU();cout<<cache3.get(2) << endl;cache3.printLFU();cout << cache3.get(3) << endl;cache3.printLFU();cache3.put(4, 4);cache3.printLFU();cout << cache3.get(1) << endl;cache3.printLFU();cout << cache3.get(3) << endl;cache3.printLFU();cout << cache3.get(4) << endl;cache3.printLFU();
3. LRU（Least Frequently Used） -- 最近最久未使用
如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。（从描述来看和LFU很类似，区别在于，LRU注重的是访问时间，而LFU注重的是访问次数，考察细节不同，但大体方向类似）
实现：核心：双向链表实现队列+ hashmap
用一个双向链表来存储数据，并把相应的地址放入hashmap中，hashmap的作用主要是提高查找效率。当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部；如果不存在，则新建一个节点，放到链表头部。若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。
#include"head.h"#include<math.h>class LRUcache{public:LRUcache(int capacity){LRUcapacity = capacity;list.Listcapcity = capacity;LRUsize = 0;}int get(int key){if (LRUmap.count(key)){Node* node = LRUmap[key];list.remove(node);list.append_front(node);return node->val;}elsereturn - 1;}void put(int key, int value){if (LRUcapacity == 0)return;if (LRUmap.count(key)){Node* node = NULL;node = list.remove(LRUmap[key]);node->val = value;list.append_front(node);}else{if (LRUsize == LRUcapacity){Node* node = NULL;node= list.remove();int x = node->val;map<int, Node*>::iterator it = LRUmap.find(x);LRUmap.erase(it);--LRUsize;}Node* node = new Node(value);list.append_front(node);LRUmap[key] = node;++LRUsize;}}void printLRU(){list.printList();}//数据成员int LRUsize;int LRUcapacity;DoubleList list;map<int, Node*>LRUmap;};
测试代码（LRU）：
LRUcache cache2(2);cache2.put(2, 2);cache2.printLRU();cache2.put(1, 1);cache2.printLRU();cache2.put(3, 3);cache2.printLRU();cout << cache2.get(1) << endl;cache2.printLRU();cout << cache2.get(2) << endl;cache2.printLRU();cout << cache2.get(3) << endl;cache2.printLRU();
头文件：
#pragma once#include<iostream>#include<map>using namespace std;class Node{public:Node() {}Node(int x){val = x;}int val = 0;Node* prev = NULL;Node* next = NULL;};class DoubleList{public:DoubleList(int capacity = 100){Listsize = 0;head = NULL;tail = NULL;Listcapcity = capacity;}//头插入bool add_head(Node* node){if (head == NULL){head = node;tail = node;head->prev = NULL;tail->next = NULL;++Listsize;return false;}else{node->next = head;head->prev = node;head = node;head->prev = NULL;++Listsize;return true;}}//尾插入bool add_tail(Node* node){if (tail == NULL){head = node;tail = node;head->prev = NULL;tail->next = NULL;++Listsize;return true;}else{node->prev = tail;tail->next = node;tail = node;tail->next = NULL;++Listsize;return true;}}//任意删除Node* removerad(Node* node){//node为 NULL 默认删除尾部节点if (node == NULL)node = tail;if (node == tail){remove_tail();return node;}else if (node == head){remove_head();return node;}else{node->prev->next = node->next;node->next->prev = node->prev;--Listsize;return node;}}//尾部删除Node* remove_tail(){if (Listsize == 0)return NULL;else if (Listsize == 1){Node* node = tail;head = NULL;tail = NULL;--Listsize;return node;}else{Node* node = tail;tail = tail->prev;tail->next = NULL;--Listsize;return node;}}//头部删除Node* remove_head(){if (Listsize == 0)return NULL;else if (Listsize == 1){Node* node = head;head = NULL;tail = NULL;--Listsize;return node;}else{Node* node = head;head = head->next;head->prev = NULL;--Listsize;return node;}}//外部接口：弹出头部Node* pop(){return remove_head();}//外部接口： 添加节点 从尾部bool append(Node* node){return add_tail(node);}//外部接口： 添加节点 从头部bool append_front(Node* node){return add_head(node);}//外部接口： 删除节点Node* remove(Node* node = NULL){return removerad(node);}//外部接口： 打印链表void printList(){if (Listsize == 0)cout << "No Node..." << endl;else {Node* cur = head;cout << "{ ";while (cur != NULL){cout << " -> " << cur->val ;cur = cur->next;}cout <<" }"<< endl;}}//数据成员部分int Listsize;int Listcapcity;Node* head;Node* tail;};
如果觉得《页面置换算法（FIFO LRU LFU）c++实现》对你有帮助，请点赞、收藏，并留下你的观点哦！
