LRU和LFU算法

使用unordered_map和双向链表实现LRU算法,定义结构体双向链表的节点,四个属性:key, value, next, prev。声明虚头节点和虚尾节点。增删改查注意维护unordered_map和双向链表里的数据,最新访问的内容放在双向链表的头部,从双向链表的尾部删除节点,unordered_map是key到节点的映射。

使用两个无序字典实现LFU算法,定义节点三个属性:key, value, cnt。声明unordered_map<int, list<Node>::iterator>类型的keyMap, unordered_map<int, list<Node>>类型的cntMap,keyMap跟LRU算法中的map功能差不多,根据key能够访问节点,cntMap维护cnt对应的双向链表,比LRU算法中的双向链表多维护一个cnt信息,相同cnt的节点连成一条双向链表,最久未访问节点在链表的尾部,声明minCnt记录双向链表中的最小cnt值。

参考链接:146. LRU 缓存
460. LFU 缓存

创建于2022.3.24/22.56,修改于2022.3.24/22.56