146-LRU Cache

tags: Medium

Question

https://leetcode.com/problems/lru-cache/

Key

1. Map is used for quickly referencing location on List, such that access of LinkList become O(1)
2. List is used to satisfy O(1) removal, and it also provide possibility so that your data has time structure (order of recently used), this can also be achieved by using array but then the removal will become O(n)
3. iterator of list<pair<int, int>>. It's like a pointer to access element of list (list: [key, value])

Reference

c++ STL solution
list 用法

Solution

C++ with map and list STL Sol.

class LRUCache {
list<pair<int, int>> dll;
unordered_map<int, list<pair<int, int>>::iterator> m;
int capacity;
public:
    LRUCache(int _capacity) {
        capacity = _capacity;
    }

    int get(int key) {
        if(m.count(key) == 0) return -1;
        auto itr = m[key];
        auto item = *itr;
        dll.erase(itr);
        dll.push_front(item);
        m[key] = dll.begin();
        return item.second;
    }

    void put(int key, int value) {
        if(m.count(key) == 1) {
            // If key exists, update value for that key
            auto itr = m[key];
            dll.erase(itr);
            dll.push_front({key, value});
            m[key] = dll.begin();
        } else {
            if(dll.size() >= capacity) {
                // Evict LRU
                auto item = dll.back();
                dll.pop_back();
                m.erase(item.first);
            }
            // Insert new key, val
            dll.push_front({key, value});
            m[key] = dll.begin();
        }
    }
};

C++ with self-defined struct Sol.

struct Node {
public:
    int m_key{-1};
    int m_value{};
    Node* m_prev{};
    Node* m_next{};
    
public:
    Node() = default;
    Node(int key, int value) : m_key{key}, m_value{value} {}
};

class LRUCache {
public:
    LRUCache(int capacity) : m_capacity{capacity}, m_cache(10001) {
        /*ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);*/
        
        m_head_dummy.m_next = &m_tail_dummy;
        m_tail_dummy.m_prev = &m_head_dummy;
    }
    
    int get(int key) {
        Node& node = m_cache[key];
        
        if (node.m_key == -1) {
            return -1;   
        }
        
        move_to_front(node);
        return node.m_value;
    }
    
    void put(int key, int value) {
        Node& node = m_cache[key];

        if (node.m_key == -1) {
            if (m_size == m_capacity) {
                evict_lru();
            } else {
                ++m_size;
            }
            
            add_node(node);
        } else {
            move_to_front(node);
        }
 
        node.m_key = key;
        node.m_value = value;
    }
    
private:
    void remove_node(Node& node) {
        node.m_prev->m_next = node.m_next;
        node.m_next->m_prev = node.m_prev;
    }
    
    void add_node(Node& node) {
        node.m_prev = &m_head_dummy;
        node.m_next = m_head_dummy.m_next;
        
        m_head_dummy.m_next->m_prev = &node;
        m_head_dummy.m_next = &node;
    }
    
    void move_to_front(Node& node) {
        // optimization
        if (node.m_prev == &m_head_dummy) {
            return;
        }
        
        remove_node(node);
        add_node(node);
    }
    
    void evict_lru() {
        Node& node = *m_tail_dummy.m_prev;
        node.m_key = -1;
        remove_node(node);
    }
    
private:
    const int m_capacity{};
    int m_size{};
    
    vector<Node> m_cache;
    
    Node m_head_dummy;
    Node m_tail_dummy;
};