LRU和LFU算法的简单实现

LRU

#include <iostream>
#include <unordered_map>
#include <list>
struct Node{int key;int value;Node(int key, int value):key(key),value(value){}
};
class LruCache{
private:int maxCapacity;// 最大容量std::list<Node>CacheList;// 缓存链表std::unordered_map<int, std::list<Node>::iterator>mp; // 快速找到key在链表中位置
public:LruCache(int cap):maxCapacity(cap){}int get(int key){// 找一个缓存是否在缓存链表中if(mp.find(key) == mp.end()){return -1;}auto cur = mp[key];CacheList.splice(CacheList.begin(), CacheList, cur);return cur->value;}void put(int key, int value){// 往缓存中插入一个Nodeif(mp.find(key) != mp.end()){ // key 存在时候auto cur = mp[key];cur->value = value;CacheList.splice(CacheList.begin(), CacheList, cur);return;}if(CacheList.size() == maxCapacity){// key 不存在的时候村缓存满的时候需要将CacheList中队尾的一个弹出去auto last = CacheList.back();mp.erase(last.key);CacheList.pop_back();}CacheList.insert(CacheList.begin(), Node(key, value));mp[key] = CacheList.begin();      }};
int main(){LruCache cache(3);cache.put(1, 1);cache.put(2, 2);std::cout << cache.get(1) << std::endl; // 1cache.put(3, 3);std::cout << cache.get(2) << std::endl; // -1cache.put(4, 4); std::cout << cache.get(1) << std::endl; // -1std::cout << cache.get(3) << std::endl; // 3std::cout << cache.get(4) << std::endl; // 4std::getchar();return 0;
}

LFU

#include <iostream>
#include <unordered_map>
#include <vector>
#include <queue>
#include <algorithm>
struct CacheNode{int key;int value;int freq;// 频率CacheNode() = default;CacheNode(int key, int value, int freq):key(key),value(value),freq(freq){}bool operator < (const CacheNode& other)const{return this->freq > other.freq;}
};
class LfuCache{
public:int maxCapacity;// 维护一个key到CacheNode的一个映射std::unordered_map<int, CacheNode>keymap;// 维护一个freq到CacheNode的一个映射std::unordered_map<int, std::vector<CacheNode>>freqmap;// 维护频率的最小堆std::priority_queue<CacheNode, std::vector<CacheNode>>minheap;
public: LfuCache(int cap):maxCapacity(cap){}int get(int key){if(keymap.find(key) == keymap.end()){return -1;}auto cur = keymap[key];updateFreq(cur);return cur.value;}void put(int key, int value){if(keymap.find(key) != keymap.end()){// key存在auto cur = keymap[key];cur.value = value;updateFreq(cur);return ;}if(keymap.size() == maxCapacity){// 满了       // 删除最小频率的键CacheNode node = minheap.top();minheap.pop();freqmap[node.freq].erase(std::remove_if(freqmap[node.freq].end(),freqmap[node.freq].end(),[&](const CacheNode cur){return cur.key == node.key;}),freqmap[node.freq].end());keymap.erase(node.key);}// 插入新的键值对CacheNode node(key, value, 1);keymap[key] = node;minheap.push(node);freqmap[1].push_back(node);}// 更新缓存记录频率void updateFreq(CacheNode node) {// 从原频率表删去freqmap[node.freq].erase(std::remove_if(freqmap[node.freq].end(),freqmap[node.freq].end(),[&](const CacheNode cur){return cur.key == node.key;}),freqmap[node.freq].end());// 更新频率++node.freq;// 插入到新频率表freqmap[node.freq].push_back(node);// 更新最小堆先要将之前堆中的Node删除std::priority_queue<CacheNode, std::vector<CacheNode>>tmp;while(!minheap.empty()){auto cur = minheap.top();minheap.pop();if(cur.key != node.key){tmp.push(cur);}}minheap.swap(tmp);minheap.push(node);}
};
int main(){LfuCache cache(3);std::cout<<cache.get(1)<<std::endl;cache.put(1,1);cache.put(2,2);cache.put(3,3);cache.get(1);cache.get(2);cache.put(4,4);std::cout<<cache.minheap.size()<<std::endl;while(!cache.minheap.empty()){auto cur = cache.minheap.top();cache.minheap.pop();std::cout<<cur.key<<cur.value<<cur.freq<<std::endl;}std::getchar();
};