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.

class LRUCache{public:    LRUCache(int capacity)     {         m_cache.clear();         m_time2key.clear();         m_key2time.clear();         m_capacity = capacity;         m_time = 0;         m_size = 0;    }    int get(int key)    {        m_time ++;        map
      
       ::iterator it = m_cache.find(key);        if(it != m_cache.end() )        {            m_time2key.erase(m_key2time[key]);            m_time2key.insert(std::make_pair(m_time, key));            m_key2time[key] = m_time;            return m_cache[key];        }        return -1;    }    void set(int key, int value)     {        m_time++;        map
       
        ::iterator it = m_cache.find(key);        if(it != m_cache.end())        {            m_cache[key] = value;            m_time2key.insert(std::make_pair(m_time, key));            m_time2key.erase(m_key2time[key]);            m_key2time[key] = m_time;        }        else        {            if(m_size == m_capacity)            {                map
        
         ::iterator it = m_time2key.begin();                m_cache.erase(it->second);                m_time2key.erase(it->first);                m_key2time.erase(it->second);                m_size--;            }            m_cache.insert(std::make_pair(key, value));            m_time2key.insert(std::make_pair(m_time, key));            m_key2time.insert(std::make_pair(key, m_time));            m_size++;        }    }private:    map
         
           m_cache;    long long m_time;    map
          
            m_time2key;    map
           
             m_key2time; int m_capacity; int m_size;};