LFU 缓存
回顾一下LRU：最近最久未使用。实现时采用双向链表+哈希表使得每次查询O1复杂度，哈希表中（key，双向链表节点（value）），查到之后，双向链表可以实现快速的删除操作，以及双向链表实现队列的效果。哈希就是为了get(key）快一些，而双向链表是为了put(key,value)的时候，调整顺序，以及满的时候淘汰，双向链表中存的只是value。
最不经常使用LFU：缓存满了之后，需要删除使用频率最小的内存，并且如果使用频率相同，需要删除插入时间最早的。
实现 LFUCache 类：
LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
int get(int key) - 如果键存在于缓存中，则获取键的值，否则返回 -1。
void put(int key, int value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。
实现：双向链表+哈希表，原则：内存标记即key是唯一的，所以第一个哈希map：key--双向链表节点，第二个map：使用次数--第一次使用的节点
方法一：
用链表顺序记录是用最少的
#include<iostream>
#include<map>
#include<list>
#include<vector>
#include<unordered_map>
using namespace std;
/*
get：查询
put：插入、删除
哈希表，维护 key，node
哈希表，维护 cnt，firstnode //cnt是使用次数，firstnode是最久未使用的
由于多个节点的cnt可能相同，因此记录每个cnt的最前方元素节点，保证最久不用的节点依次位于后方
链表node<cnt, value>
其中，cnt需要降序排列，
- 有新的key时，插入到cnt=1的最前面，保证最后一位是“最不常用&&cnt=1中最久没使用“的。
更新 cnt，node，firstnode
- 删除时，删除cnt最小的，即，最后一位
更新 cnt，node，firstnode
*/
class LFUCache {
private:
int capacity;
list<vector<int>> nodeList; //node<cnt, value, key>
unordered_map<int, list<vector<int>>::iterator> keyNodeMap;
unordered_map<int, list<vector<int>>::iterator> cntFirstNodeMap;
//打印 list 和 map
void printAllData(string action) {
for (auto it = nodeList.begin(); it != nodeList.end(); it++) {
auto vec = *it;
cout << "{" << vec[2] << "," << vec[1] << "," << vec[0] << "}, ";
}
cout << endl;
for (auto it = keyNodeMap.begin(); it != keyNodeMap.end(); it++) {
int key = it->first;
auto vec = *(it->second);
cout << "key: " << key << "{" << vec[2] << "," << vec[1] << "," << vec[0] << "}, ";
}
cout << endl;
for (auto it = cntFirstNodeMap.begin(); it != cntFirstNodeMap.end(); it++) {
int cnt = it->first;
auto vec = *(it->second);
cout << "cnt: " << cnt << "{" << vec[2] << "," << vec[1] << "," << vec[0] << "}, ";
}
cout << endl << endl;
}
public:
LFUCache(int capacity) {
this->capacity = capacity;
}
int get(int key) {
if (!keyNodeMap.count(key)) return -1;
auto currNode = keyNodeMap[key];
int currCnt = (*currNode)[0];
int value = (*currNode)[1];
auto firstNode = cntFirstNodeMap[currCnt];
int newCnt = currCnt + 1;
//若newCnt已存在，则放到全部newCnt之前，否在放到全部currCnt之前
if (cntFirstNodeMap.count(newCnt)) { firstNode = cntFirstNodeMap[newCnt]; }
//更新list：插入
auto newNode = nodeList.insert(firstNode, { newCnt, value, key });
//更新keyNodeMap：替换
keyNodeMap[key] = newNode;
//新的cnt，更新cntFirstNodeMap：替换
cntFirstNodeMap[newCnt] = newNode;
//老的cnt，更新cntFirstNodeMap：若恰好为currNode，则更新or删除，否则不用动
if (cntFirstNodeMap[currCnt] == currNode) {
auto it = currNode;
it++;
if (it == nodeList.end()) {
cntFirstNodeMap.erase(currCnt);
}
else if ((*it)[0] == currCnt) {
cntFirstNodeMap[currCnt] = it;
}
else { //cnt变了，说明currCnt下，已经没有任何节点了
cntFirstNodeMap.erase(currCnt);
}
}
//更新list：删除
nodeList.erase(currNode);
//printAllData("get");
return value;
}
void put(int key, int value) {
if (capacity == 0) return;
if (get(key) != -1) {
(*keyNodeMap[key])[1] = value;
//printAllData("put(update)");
return;
}
//溢出删除
if (nodeList.size() == capacity) {
auto lastNode = --nodeList.end();
int cnt = (*lastNode)[0];
int value = (*lastNode)[1];
int key = (*lastNode)[2];
//keyNodeMap：删除这个key
keyNodeMap.erase(key);
//cntFirstNodeMap：相同则删除，否则不变
if (cntFirstNodeMap[cnt] == lastNode) cntFirstNodeMap.erase(cnt);
//nodeList：删除链表最后一个节点
nodeList.pop_back();
}
//插入到 cnt=1 的最前面
auto currNode = nodeList.end();
if (cntFirstNodeMap.count(1)) {
currNode = cntFirstNodeMap[1];
}
auto newNode = nodeList.insert(currNode, { 1, value, key });
cntFirstNodeMap[1] = newNode;
keyNodeMap[key] = newNode;
//printAllData("put(add)");
return;
}
};
int main()
{
//LFUCache a;
//定义了构造函数就没有默认构造函数里，在栈上创建出来的对象都有一个名字，比如 stu，使用指针指向它不是必须的。用.调用方法
LFUCache *lFUCache = new LFUCache(2); //定义对象
//通过 new 创建出来的对象就不一样了，它在堆上分配内存，没有名字，只能得到一个指向它的指针，所以必须使用一个指针变量来接收这个指针，否则以后再也无法找到这个对象了，更没有办法使用它。也就是说，使用 new 在堆上创建出来的对象是匿名的，没法直接使用，必须要用一个指针指向它，再借助指针来访问它的成员变量或成员函数。
lFUCache->put(1, 1); //因为上面定义的指针对象，所以->，不是指针对象用.
lFUCache->put(2, 2);
cout << lFUCache->get(1) << endl; //key2对应的是1
lFUCache->put(3, 3);
cout << lFUCache->get(2) << endl; //1已经被淘汰
cout << lFUCache->get(1) << endl;
system("pause");
}
方法二：
或是可以维护一个最小频次，每次移除一个节点的时候，需要移除最小频次的节点，每次增加时，也需要更新节点的频次。
#include<iostream>
#include<map>
#include<list>
#include<vector>
#include<unordered_map>
using namespace std;
/*
get：查询
put：插入、删除
哈希表，维护 key，node
哈希表，维护 cnt，firstnode //cnt是使用次数，firstnode是最久未使用的
由于多个节点的cnt可能相同，因此记录每个cnt的最前方元素节点，保证最久不用的节点依次位于后方
这个链表不需要相连，只是用它的节点
维护一个最小频次
*/
struct Node
{
int key;
int value;
int frenquency;
Node(int _key, int _value, int _frequency) :key(_key), value(_value), frenquency(_frequency){}
};
class LFUCache {
public:
LFUCache(int _capacity) {
capacity = _capacity;
minfreq = 0;
frequency_table.clear();
key_table.clear();
}
int get(int key) {
if (capacity == 0) return -1;
auto it = key_table.find(key);
if (it == key_table.end()) return -1;
auto node = it->second;
int val = node->value;
int freq = node->frenquency;
//删除操作
frequency_table[freq].erase(node);
if (frequency_table[freq].size() == 0)
{
//记录freq频率的双链表没结点了
frequency_table.erase(freq);
if (minfreq == freq) minfreq++;
}
//添加结点
frequency_table[freq + 1].push_front(Node(key, val, freq + 1));
key_table[key] = frequency_table[freq + 1].begin();
return val;
}
void put(int key, int value) {
if (capacity == 0) return;
auto it = key_table.find(key);
//key表中找不到值，分缓存满和不满两种情况
if (it == key_table.end())
{
//缓存已经满的情况
if (key_table.size() == capacity)
{
auto it2 = frequency_table[minfreq].back();
key_table.erase(it2.key);
frequency_table[minfreq].pop_back();
if (frequency_table[minfreq].size() == 0)
{
frequency_table.erase(minfreq);
}
}
//两种情况都要添加操作，所以合并在一起
frequency_table[1].push_front(Node(key, value, 1));
key_table[key] = frequency_table[1].begin();
minfreq = 1;
}
else{
//如果表中存在，需要更新frequency的值
auto node = it->second;
int freq = node->frenquency;
//删除操作
frequency_table[freq].erase(node);
if (frequency_table[freq].size() == 0)
{
//记录freq频率的双链表没结点了
frequency_table.erase(freq);
if (minfreq == freq) minfreq++;
}
//添加结点
frequency_table[freq + 1].push_front(Node(key, value, freq + 1));
key_table[key] = frequency_table[freq + 1].begin();
}
}
private:
int minfreq;
int capacity;
unordered_map<int, list<Node>>frequency_table;
unordered_map<int, list<Node>::iterator>key_table;
};
int main()
{
//LFUCache a;
//定义了构造函数就没有默认构造函数里，在栈上创建出来的对象都有一个名字，比如 stu，使用指针指向它不是必须的。用.调用方法
LFUCache *lFUCache = new LFUCache(2); //定义对象
//通过 new 创建出来的对象就不一样了，它在堆上分配内存，没有名字，只能得到一个指向它的指针，所以必须使用一个指针变量来接收这个指针，否则以后再也无法找到这个对象了，更没有办法使用它。也就是说，使用 new 在堆上创建出来的对象是匿名的，没法直接使用，必须要用一个指针指向它，再借助指针来访问它的成员变量或成员函数。
lFUCache->put(1, 1); //因为上面定义的指针对象，所以->，不是指针对象用.
lFUCache->put(2, 2);
cout << lFUCache->get(1) << endl; //key2对应的是1
lFUCache->put(3, 3);
cout << lFUCache->get(2) << endl; //1已经被淘汰
cout << lFUCache->get(1) << endl;
system("pause");
}