LRU与LFU的c++实现

LRU 是时间维度上最少使用 维持一个链表，最近使用的放在表头 淘汰表尾
LFU 是实际使用频率的最少使用 每一个对应的频率维持一个链表， 淘汰最低频率的最后一个

1. LRU
LRU（Least Recently Used，最近最少使用）是一种常用的缓存淘汰算法。
LRU算法基于时间局部性原理，认为最近使用的数据很可能在近期内再次被使用，而最久未使用的数据很可能是不再使用的数据，因此将最久未使用的数据淘汰出缓存。

每个缓存项都会在链表中维护一个链表节点，并在哈希表中以缓存键为键存储对应的节点地址。当需要访问缓存项时，如果该项已经存在于缓存中，就将其移到链表的头部；如果该项不存在于缓存中，则将其加入缓存，并放置在链表的头部。当缓存容量达到上限并且需要淘汰数据时，就将链表尾部的元素移除。

#include <list>
#include <utility>
class Solution {private: list<pair<int, int>> cache_list;  // 实际数据位置unordered_map<int, list<pair<int,int>>::iterator>cache_map; // 索引， 指向列表中实际的数据存储位置int capacity;
public:Solution(int capacity){this->capacity = capacity;}int get(int key) {if(cache_map.find(key)!=cache_map.end()){auto it = cache_map[key];pair<int, int>cur = *it;cache_list.erase(it);     // 被get或者set 就数值移动到list 头部cache_list.push_front(cur);cache_map[key] = cache_list.begin();return cur.second;}return -1;}void set(int key, int value){if(cache_map.find(key)!=cache_map.end()){auto it = cache_map[key];cache_list.erase(it);}else if(cache_list.size() >= capacity){cache_map.erase(cache_list.back().first);  //list中的最后一个肯定是最近最少使用cache_list.pop_back();}pair<int, int>cur = make_pair(key, value);cache_list.push_front(cur);cache_map[key] = cache_list.begin();}
};

2. LFU
LFU（Least Frequently Used，最不经常使用）是一种常用的缓存淘汰算法。LFU算法基于访问频率原理，认为被访问频率最低的数据很可能是不再使用的数据，因此将访问频率最低的数据淘汰出缓存。

#include <list>
class Solution {struct Node{ int key;int value;int frequency;list<int>::iterator it;   // 指向频率队列中这个节点的位置 用于清除这个元素};private:unordered_map<int, Node>cache_map; // 既是索引又是数据存储位置unordered_map<int, list<int>>cache_list; //只是为了记录淘汰顺序的map int 为频率， list存着对应这个频率的队列int capcity;int min_f;   // 当前的最小频率public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** lfu design* @param operators int整型vector<vector<>> ops* @param k int整型 the k* @return int整型vector*/vector<int> LFU(vector<vector<int> >& operators, int k) {vector<int>result;setCapcity(k);cout <<"start"<<endl;for(int i=0; i<operators.size(); i++){cout << operators[i][0] <<endl;if(operators[i][0] == 1){cout << "插入: " <<" key: " << operators[i][1] <<" value: " << operators[i][2] <<endl;set(operators[i][1], operators[i][2]);}else{int r = get(operators[i][1]);result.push_back(r);cout << "返回: " <<" key: " << operators[i][1] <<" value: " << r <<endl;;}}return result;}void setCapcity (int capcity){this->capcity = capcity;}int get(int key){if(cache_map.find(key) != cache_map.end()){update(cache_map[key]);return cache_map[key].value;}return -1;}void set(int key, int value){if(cache_map.find(key) != cache_map.end()){Node &node = cache_map[key];   // 命中缓存，修改数值update(node);     // 去更新node在频率列表中的位置 node.frequency += 1;  // 更改缓存cache_map[key] = node;  装回缓存return;}if(cache_map.size() == capcity){   int key = cache_list[min_f].back(); // 清除最低频率的最后一个元素cache_map.erase(key);            cache_list[min_f].pop_back();}Node node;node.key = key;node.value = value;node.frequency = 1;cache_list[1].push_front(key);node.it = cache_list[1].begin();min_f = 1;   //装入一个新的元素，最低频率更新为1cache_map[key] = node;}void update(Node &node){int old_f = node.frequency;int new_f = old_f + 1;cache_list[old_f].erase(node.it);cache_list[new_f].push_front(node.key);node.it = cache_list[new_f].begin();if(cache_list[old_f].empty() && old_f == min_f){   // 更新最小次数min_f = old_f+1;}}};