[LeetCode 146] 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.

Diffculty
Hard

Similar Problems

Analysis

The best way to implement an LRU is to use the combination of a std::list and std::unordered_map (want to use only std then std::map). Store the data in the list so that the least recently used in at the last and use the map to point to the list items. For "get" use the map to get the list addr and retrieve the data and move the current node to the first(since this was used now) and update the map. For "insert" remove the last element from the list and add the new data to the front and update the map. This is the fastest u can get.

The LRU cache is structure containing hash table and double linked nodes. The hash table makes the time of get() to be O(1). The list of double linked nodes make the nodes adding/removal operations O(1).

class Node{ int key; int value; Node pre; Node next;

public Node(int key, int value){
    this.key = key;
    this.value = value;
}

}

// 分析：

1. 1. 要能快速找到最早更新的item。可选的数据结构有：queue，heap，linked list
2. 这里需要将item以更新时间顺序排序。对于更新时间顺序这个操作，queue和heap要做到就很困难了。所以这点最佳的是linked list。 但linked list中查找指定item需要遍历，这里可以用一个hash table来记录key与节点之间的对应。 并且由于要随时更新节点位置，doubly linked list更为适用。 注意在链表里一定要同时存储key和value，不能够只存储value，因为在删除list部节点时， 需要同时将这个键值对在map中删除，而删除map中的元素是需要对应的key的。

class LRUCache{ public: struct CacheEntry{ public: int key; int value; CacheEntry(int k, int v) :key(k), value(v) {} };

LRUCache(int capacity) {
    m_capacity = capacity;
}

int get(int key) {
    if (m_map.find(key) == m_map.end()) return -1;
    MoveToHead(key);
    return m_map[key]->value;
}

void set(int key, int value) {
    if (m_map.find(key) == m_map.end()){
        CacheEntry newItem(key, value);
        if (m_LRU_cache.size() >= m_capacity){ // first check whether the capacity is already full
            //remove from tail
            m_map.erase(m_LRU_cache.back().key);
            m_LRU_cache.pop_back();
        }

        // insert in head.
        m_LRU_cache.push_front(newItem);
        m_map[key] = m_LRU_cache.begin();
        return;
    }

    m_map[key]->value = value;
    MoveToHead(key);
}

private: unordered_map::iterator> m_map; list m_LRU_cache; int m_capacity;

void MoveToHead(int key){
    //Move key from current location to head
    auto entrytoUpdate = *m_map[key];
    m_LRU_cache.erase(m_map[key]);
    m_LRU_cache.push_front(entrytoUpdate);
    m_map[key] = m_LRU_cache.begin();
}

};

class LRUCache{

struct Node {
    int val;
    int key;
    Node *next;
    Node *prev;
    Node(int k, int v):key(k),val(v) {}
};

int maxSize;
Node* head;
Node* tail;
unordered_map<int,Node*> keyToNode;

void insertToEnd(int key, int value) {
    if(isFull() || keyToNode.count(key)!=0) return;
    Node *nd = new Node(key, value);
    keyToNode[key] = nd;
    if(!head) {
        head = tail = nd;
    }
    else {
        tail->next = nd;
        nd->prev = tail;
        tail = tail->next;
    }
}

void removeHead() {
    if(!head) return;
    keyToNode.erase(head->key);
    Node *temp = head;
    if(head==tail) // only one node remain
        head = tail = NULL;
    else {
        head = head->next;
        head->prev = NULL;
    }
    delete temp;
}

void moveToEnd(int key) {
    // key not exist, or already at the end
    if(keyToNode.count(key)==0 || keyToNode[key]==tail) return;
    Node *nd = keyToNode[key];
    if(nd==head) {
        head = head->next;
        head->prev = NULL;
    }
    else {  // not head, not tail
        nd->prev->next = nd->next;
        nd->next->prev = nd->prev;
    }

    tail->next = nd;
    nd->prev = tail;
    nd->next = NULL;
    tail = tail->next;
}

public: LRUCache(int capacity) { maxSize = capacity; head = NULL; tail = NULL; keyToNode.clear(); }

int get(int key) {
    if(keyToNode.count(key)==0) return -1;
    moveToEnd(key);
    return keyToNode[key]->val;
}

void set(int key, int value) {
    // key already exists
    if(get(key)!=-1) {
        keyToNode[key]->val = value;
        return;
    }

    // key not exist, insert new node
    if(isFull()) removeHead();
    insertToEnd(key, value);
}

bool isFull() {
    return keyToNode.size()>=maxSize;
}

};