首先定义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，符合预期。
总结
本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注编程网的更多内容！
