146. LRU Cache (Hard)

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.

Solution:

这道题让我们实现一个LRU缓存器，LRU是Least Recently Used的简写，就是最近最少使用的意思。那么这个缓存器主要有两个成员函数，get和set，其中get函数是通过输入key来获得value，如果成功获得后，这对(key, value)升至缓存器中最常用的位置（顶部），如果key不存在，则返回-1。而set函数是插入一对新的(key, value)，如果原缓存器中有该key，则需要先删除掉原有的，将新的插入到缓存器的顶部。如果不存在，则直接插入到顶部。若加入新的值后缓存器超过了容量，则需要删掉一个最不常用的值，也就是底部的值。具体实现时我们需要三个私有变量，cap, l和m，其中cap是缓存器的容量大小，l是保存缓存器内容的列表，m是哈希表，保存关键值key和缓存器各项的迭代器之间映射，方便我们以O(1)的时间内找到目标项。

class LRUCache{
public:
    LRUCache(int capacity): cap(capacity) {}

    int get(int key) {
        auto it = m.find(key);
        if (it == m.end()) return -1;
        l.splice(l.begin(), l, it->second);
        return it->second->second;
    }

    void set(int key, int value) {
        auto it = m.find(key);
        if (it != m.end()) l.erase(it->second);
        l.push_front(make_pair(key, value));
        m[key] = l.begin();
        if (m.size() > cap) {
            int k = l.rbegin()->first;
            l.pop_back();
            m.erase(k);
        }
    }
private:
    int cap;
    list<pair<int, int>> l;
    unordered_map<int, list<pair<int, int>>::iterator> m;
};

version 2: 82ms

class LRUCache {
public:
    LRUCache(int capacity): m_cap(capacity) {

    }

    int get(int key) {
        auto it = m_map.find(key);
        if (it == m_map.end()) return -1; // key doesn't exist
        m_list.splice(m_list.begin(), m_list, it->second); //move the node corresponding to key to front
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = m_map.find(key);
        if (it != m_map.end()) { // key exists
            m_list.splice(m_list.begin(), m_list, it->second); 
            it->second->second = value;
            return;
        }

        if (m_list.size() == m_cap) {
            m_map.erase(m_list.back().first); // remove key in map
            m_list.pop_back(); //  remove node in list
        }
        m_list.push_front({key,value});
        m_map[key] = m_list.begin();
    }
private:
    int m_cap;
    unordered_map<int,list<pair<int,int>>::iterator> m_map;
    list<pair<int,int>> m_list;
};

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