编写一个具有put,get功能的LFU Cache类
时间: 2024-05-03 21:22:39 浏览: 12
```
class LFUCache {
private:
int capacity;
int minFreq;
unordered_map<int, pair<int, int>> cache; // key -> {value, freq}
unordered_map<int, list<int>::iterator> freqMap; // freq -> iterator of keys
unordered_map<int, list<int>> lruMap; // freq -> list of keys
public:
LFUCache(int capacity) {
this->capacity = capacity;
minFreq = 0;
}
int get(int key) {
if (cache.count(key) == 0) {
return -1;
}
int value = cache[key].first;
int freq = cache[key].second;
freqMap.erase(key);
lruMap[freq].erase(freqMap[key]);
if (lruMap[freq].empty()) {
lruMap.erase(freq);
if (freq == minFreq) {
minFreq++;
}
}
freq++;
cache[key] = {value, freq};
lruMap[freq].push_front(key);
freqMap[key] = lruMap[freq].begin();
return value;
}
void put(int key, int value) {
if (capacity == 0) {
return;
}
if (cache.count(key) != 0) {
cache[key].first = value;
get(key);
return;
}
if (cache.size() == capacity) {
int keyToRemove = lruMap[minFreq].back();
lruMap[minFreq].pop_back();
freqMap.erase(keyToRemove);
cache.erase(keyToRemove);
}
minFreq = 1;
cache[key] = {value, minFreq};
lruMap[minFreq].push_front(key);
freqMap[key] = lruMap[minFreq].begin();
}
};
```
LFU Cache类的实现使用了三个哈希表:
- `cache` 哈希表:存储键值对和对应的频率。
- `freqMap` 哈希表:存储键值对的频率和对应的迭代器。
- `lruMap` 哈希表:存储键值对的频率和对应的链表。
其中,`cache` 哈希表用于快速查找键值对,`freqMap` 哈希表用于快速查找键值对对应的迭代器,`lruMap` 哈希表用于快速查找某个频率对应的键值对。
LFU Cache类有两个方法:
- `get` 方法:根据键获取值,如果键不存在则返回 -1。同时更新键值对的频率和链表。
- `put` 方法:插入一个键值对。如果键已存在,则更新值和频率;如果容量已满,则删除频率最小的键值对。同时更新最小频率和链表。