[Leetcode] LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Analysis:

The goal is to have O(1) time complexity for both get and set. To get O(1), we have to use a hash table to access the the element; To get O(1) for least visited element, we use a double linked list and keep the most recent visited key at the beginning of the list and the tail of the list would be least recent used element. Note when the capacity is reached, you have to remove both the tail of the list and the element in the hash table.

class LRUCache{
    int m_size;
    int m_capacity;
    list<pair<int, int>> m_list;
    map<int, list<pair<int, int>>::iterator> m_map;
public:
    LRUCache(int capacity) {
        m_capacity = capacity;
        m_size = 0;
    }
    
    int get(int key) {
        int value = -1;
        if (m_map.find(key) != m_map.end())
        {
            //key exists in the cache, move the element to the beginning of the list
            list<pair<int, int>>::iterator itr = m_map[key];
            value = itr->second;
            m_list.erase(itr);
            m_list.push_front(make_pair(key,value));
            m_map[key] = m_list.begin();
        }
        
        return value;
    }
    
    void set(int key, int value) {
        if (m_map.find(key) != m_map.end())
        {
            //if the key is present, update and move the element to the beginning of the list
            m_list.erase(m_map[key]);
            m_list.push_front(make_pair(key, value));
            m_map[key] = m_list.begin();
        }
        else
        {
            //if reach the capacity, remove the last element and erase the element in map
            if (m_capacity <= m_size)
            {
                int tmp = m_list.back().first;
                m_map.erase(tmp);
                m_list.pop_back();
                m_size--;
            }
            //insert to the front of the list
            m_list.push_front(make_pair(key, value));
            m_map[key] = m_list.begin();
            m_size++;
            
        }
    }
};