# C++ Solution with unordered_map and priority_queue, 189ms beats 84.41%

• I use a unordered_map to track the correct key value pair and corresponding to its counter and newest timer. And use a priority_queue to lazy store the current data, the priority_queue is sorted by its frequency and time.

``````class LFUCache {
private:
struct Node {
int key, val;
int freq;
long time;
Node(int k, int v, int f, long t) : key(k), val(v), freq(f), time(t) {}
Node() : key(0), val(0), freq(0), time(0) {}
friend bool operator<(const Node& a, const Node& b) {
if(a.freq == b.freq) return a.time > b.time;
return a.freq > b.freq;
}
};
// key -> Node map
unordered_map<int, Node> _umap;
// sorted by freq and time
priority_queue<Node> _pq;
int _cap;
static long curTime;

public:
LFUCache(int capacity) {
_cap = capacity;
}

int get(int key) {
if(_cap <= 0) return -1;
if(_umap.find(key) == _umap.end()) return -1;
_umap[key].freq ++;
_umap[key].time = curTime ++;
return _umap[key].val;
}

void set(int key, int value) {
if(_cap <= 0) return;
if(_umap.find(key) != _umap.end()) {
_umap[key].freq ++;
_umap[key].time = curTime ++;
_umap[key].val = value;
}
else {
clrExpire();
_umap[key] = Node(key, value, 1, curTime);
_pq.push(Node(key, value, 1, curTime ++));
}
}

void clrExpire() {
while(!_pq.empty() && _pq.size() >= _cap) {
Node tmp = _pq.top();
_pq.pop();
// lazy update, if the record in the priority_queue is not the same as
// the newest record in the unordered_map, then update it and push back
// to the priority_queue
if(_umap[tmp.key].freq != tmp.freq || _umap[tmp.key].time != tmp.time) {
_pq.push(_umap[tmp.key]);
}
else _umap.erase(_umap.find(tmp.key));
}

}
};

long LFUCache::curTime = 0;

/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache obj = new LFUCache(capacity);
* int param_1 = obj.get(key);
* obj.set(key,value);
*/
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.