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 get and put must each run in O(1) average time complexity.

Data Structure Used

To satisfy the O(1) average time complexity for get and put,

  1. Use double-linked list (STL list) storing the cache items (as STL pair {key, value} ),
  2. Use a HashMap (STL unordered_map) storing the mapping relation from the key to the pair iterator
typedef std::unordered_map<int, std::list<std::pair<int, int> >::iterator > CacheMap;
typedef std::list<std::pair<int, int> > LRUList;

Flowchart

  • get function
  • put function

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 the capacity of the data structure.
  • int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1.
  • void put(int key, int value) Update the value of the key if present, or inserts the key if 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 key would be invalidated.
  • To determine the least frequently used key, a use counter is maintained for each key in 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 the put operation). The use counter for a key in the cache is incremented either a get or put operation is called on it.
  • The functions get and put must each run in O(1) average time complexity.

Data Structure Used

To satisfy the O(1) average time complexity for get and put,

  1. Use a HashMap (STL unordered_map) storing the mapping relation from the key to its value and frequency (as STL pair {value, frequency} )
  2. Use a HashMap (STL unordered_map) storing the mapping relation from the frequency to the corresponding keys (as double-linked list, STL list)
  3. Use a HashMap (STL unordered_map) storing the mapping relation from the key to the corresponding iterator in 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

  • get function
  • put function

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)