C++实现支持泛型的LFU C++实现支持泛型的LFU详解
黄杨峻 人气:0想了解C++实现支持泛型的LFU详解的相关内容吗,黄杨峻在本文为您仔细讲解C++实现支持泛型的LFU的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:C++泛型,C++LFU,下面大家一起来学习吧。
首先定义LFU存储数据节点ListNode的结构, 此结构支持键K和值V的模板,为了在有序元素中实现比较(严格小于),这里需要重载小于号,如果此数据的使用频次最少,则小于结果为true,如果频次相等,轮次早的数据最小。
template<typename K, typename V> struct ListNode { K key; V value; int freq; long cur; bool operator<(const ListNode &x) const { if (freq < x.freq) return true; else if (freq == x.freq) return cur < x.cur; else return false; } };
然后我们来实现lfu类,我们用unordered_map去存key值对应的ListNode,用set<ListNode<K,V>> freq来充当频次的存储容器,使用set的好处是自动排序,频次小的数据迭代器会被排到freq的begin(),删除是只需要erase掉begin所指向的迭代器即可。我们来具体分析get和put操作
- get操作首先去map中查询此key对应ListNode是否存在,如果此数据存在,将其对应的频次+1(这里用reinsert函数实现),如果数据不存在,返回-1。
- put操作也要去map中查询此key对应ListNode是否存在,若存在,直接将ListNode的value更新,并且将其对应的频次+1(同上),否则,在map对应此键值的桶中插入ListNode,然后在freq中将其对应的频次设为1并插入。
完整代码如下:
#include <map> #include <set> #include <unordered_map> using namespace std; template<typename K, typename V> struct ListNode { K key; V value; int freq; long cur; bool operator<(const ListNode &x) const { if (freq < x.freq) return true; else if (freq == x.freq) return cur < x.cur; else return false; } }; template<typename K, typename V> class lfu { private: long cur_rount; int capacity; unordered_map<int, ListNode<K, V>> m; set<ListNode<K, V>> freq; public: lfu(int capacity) { capacity = capacity; cur_rount = 0; } V get(K key) { auto it = m.find(key); if (it == m.end()) return -1; V value = it->second.value; reinsert(it->second); return value; } void put(K key, V value) { if (capacity == 0) return; auto it = m.find(key); if (it != m.end()) { it->second.value = value; reinsert(it->second); return; } if (m.size() == capacity) { const ListNode<K, V> &node = *freq.begin(); m.erase(node.key); freq.erase(node); } ListNode<K, V> node{key, value, 1, ++cur_rount}; m[node.key] = node; freq.insert(node); } void reinsert(ListNode<K, V> &node) { freq.erase(node); ++node.freq; node.cur = ++cur_rount; freq.insert(node); } };
这里写了一个简单的主函数去验证,K和V都使用int进行实例化。
可以看到第一次查询,得到key=1的值为8,符合预期,在插入key=7 value=10的ListNode后,LFU频次最低的Key=5 ListNode。此时再去get Key=5的值会得到一个-1,符合预期。
总结
本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注的更多内容!
加载全部内容