C++ Implementation of LRU & LFU Cache
LRU (Least Recently Used) Cache
Referring to LeetCode Q146 https://leetcode.com/problems/lru-cache/
Description
LRUCache(int capacity)Initialize the LRU cache with positive size capacity.int get(int key)Return the value of the key if the key exists, otherwise return -1.void put(int key, int value)Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used- The functions
getandputmust each run inO(1)average time complexity.
Data Structure Used
To satisfy the O(1) average time complexity for get and put,
- Use double-linked list (STL
list) storing the cache items (as STLpair{key, value} ), - Use a HashMap (STL
unordered_map) storing the mapping relation from the key to the pairiterator
typedef std::unordered_map<int, std::list<std::pair<int, int> >::iterator > CacheMap;
typedef std::list<std::pair<int, int> > LRUList;
Flowchart
getfunction
putfunction
Implementation
#include <iostream>
#include <list>
#include <unordered_map>
typedef std::unordered_map<int, std::list<std::pair<int, int> >::iterator > CacheMap;
typedef std::list<std::pair<int, int> > LRUList;
class LRUCache {
public:
LRUCache(int capacity) {
_capacity = capacity;
}
int get(int key) {
CacheMap::iterator cache_itr = _cacheMap.find(key);
if (cache_itr == _cacheMap.end() ) {
return -1;
}
makeMostRecent(key, _cacheMap[key]->second);
LRUList::iterator list_itr = _LRUList.end();
--list_itr;
return list_itr->second;
}
void put(int key, int value) {
if (_cacheMap.find(key) != _cacheMap.end()) {
makeMostRecent(key, value);
return;
}
if (_LRUList.size() >= _capacity) {
removeLeastRecentTask(key);
}
addMostRecentTask(key, value);
}
private:
void makeMostRecent(int key, int value) {
_LRUList.erase(_cacheMap[key]);
_LRUList.push_back(std::make_pair(key, value) );
LRUList::iterator list_itr = _LRUList.end();
_cacheMap[key] = --list_itr;
}
void removeLeastRecentTask(int key) {
int keyToRemove = _LRUList.begin()->first;
_LRUList.erase(_LRUList.begin());
_cacheMap.erase(keyToRemove);
}
void addMostRecentTask(int key, int value) {
_LRUList.push_back(std::make_pair(key, value) );
LRUList::iterator list_itr = _LRUList.end();
_cacheMap[key] = --list_itr;
}
int _capacity;
LRUList _LRUList;
CacheMap _cacheMap;
};
// n = item number of the LRU list, aka capacity
// Time: O(1)
// Space: O(n)
Runtime
Accepted
22/22 cases passed (412 ms)
Your runtime beats 69.45 % of cpp submissions
Your memory usage beats 48.08 % of cpp submissions (174 MB)
LFU (Least Frequently Used) Cache
Referring to LeetCode Q460 https://leetcode.com/problems/lfu-cache/
Description
LFUCache(int capacity)Initializes the object with thecapacityof the data structure.int get(int key)Gets thevalueof thekeyif thekeyexists in the cache. Otherwise, returns -1.void put(int key, int value)Update the value of the key if present, or inserts thekeyif not already present.- When the cache reaches its
capacity, it should invalidate and remove the least frequently used key before inserting a new item. - For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used
keywould be invalidated.
- When the cache reaches its
- To determine the least frequently used key, a use counter is maintained for each
keyin the cache. The key with the smallest use counter is the least frequently used key. - When a key is first inserted into the cache, its use counter is set to
1(due to theputoperation). The use counter for a key in the cache is incremented either agetorputoperation is called on it. - The functions
getandputmust each run inO(1)average time complexity.
Data Structure Used
To satisfy the O(1) average time complexity for get and put,
- Use a HashMap (STL
unordered_map) storing the mapping relation from the key to its value and frequency (as STLpair{value, frequency} ) - Use a HashMap (STL
unordered_map) storing the mapping relation from the frequency to the corresponding keys (as double-linked list, STLlist) - Use a HashMap (STL
unordered_map) storing the mapping relation from thekeyto the correspondingiteratorin 2’s list.
std::unordered_map<int, std::pair<int, int> > _keyToValFreq;
std::unordered_map<int, std::list<int> > _freqToKeyList;
std::unordered_map<int, std::list<int>::iterator> _keyToKeyListItr;
Flowchart
getfunction
putfunction
Implementation
#include <iostream>
#include <list>
#include <unordered_map>
class LFUCache {
public:
LFUCache(int capacity) {
_capacity = capacity;
}
int get(int key) {
// If key doesn't exist
if (_keyToValFreq.find(key) == _keyToValFreq.end() ) {
return -1;
}
// if key exists, increse frequency and reorder
increaseFreq(key);
return _keyToValFreq[key].first;
}
void put(int key, int value) {
if (_capacity <= 0) { return; }
// if key exists
if (_keyToValFreq.find(key) != _keyToValFreq.end() ) {
_keyToValFreq[key].first = value;
increaseFreq(key);
return;
}
// if key doesn't exist
// if reached hashmap's max capacity, remove the LFU (LRU if tie)
if (_keyToValFreq.size() >= _capacity) {
int keyToRmove = _freqToKeyList[_minFreq].back();
_freqToKeyList[_minFreq].pop_back();
_keyToKeyListItr.erase(keyToRmove);
_keyToValFreq.erase(keyToRmove);
}
// Then add new item with frequency = 1
addNewTask(key, value);
}
void increaseFreq(int key) {
// Update the freq in the pair
int oldFreq = _keyToValFreq[key].second++;
// Detele the old freq by itr
_freqToKeyList[oldFreq].erase(_keyToKeyListItr[key]);
// Add the new freq and re-assign the itr
_freqToKeyList[oldFreq + 1].emplace_front(key);
_keyToKeyListItr[key] = _freqToKeyList[oldFreq + 1].begin();
// Update minFreq
if (_freqToKeyList[_minFreq].empty() ) {
_minFreq = oldFreq + 1;
}
}
void addNewTask(int key, int value) {
// Add new key-value/freq to all hashmaps
_minFreq = 1;
_keyToValFreq[key] = std::make_pair(value, _minFreq);
_freqToKeyList[_minFreq].emplace_front(key);
_keyToKeyListItr[key] = _freqToKeyList[_minFreq].begin();
}
private:
int _capacity;
int _minFreq;
std::unordered_map<int, std::pair<int, int> > _keyToValFreq;
std::unordered_map<int, std::list<int> > _freqToKeyList;
std::unordered_map<int, std::list<int>::iterator> _keyToKeyListItr;
};
// n = item number of the LFU, aka capacity
// Time: O(1)
// Space: O(n)
Runtime
Accepted
24/24 cases passed (464 ms)
Your runtime beats 72.37 % of cpp submissions
Your memory usage beats 45.99 % of cpp submissions (186.7 MB)