LRU Cache

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.

----------------------------------------- thinking --------------------------------------------------------
hash table + double linked list
according to the codes, I have a big problem on accurately writting double linked list!!! Please pay attention to the codes
----------------------------------------- codes ----------------------------------------------------------
struct node {
    int key;
    int value;
    node *next;
    node *pre;
    node(int k, int v) : key(k), value(v), next(NULL), pre(NULL) {}
    node () : key(-1), value(-1), next(NULL), pre(NULL) {}
};
class LRUCache{
private:
    node head;
    node *tail;
    unordered_map<int, node *> map;
    int capacity;
    int cur_capa;
public:
    LRUCache(int capacity) {
        this->cur_capa = 0;
        this->capacity = capacity;
        this->tail = NULL;
        this->head.pre = NULL;
        this->head.next = NULL;
    }

    int get(int key) {
        if (map[key]) {
            node *cur = map[key];
            node *pre = cur->pre;
            node *next = cur->next;
            //bug here, tail needs to be updated
            if (tail == cur && head.next != tail) {
                tail = pre;
            }
            pre->next = next;
            if (next) {
                //bug here, next can be null
                next->pre = pre;
            }
            cur->pre = &head;
            cur->next = head.next;
            if (head.next) {
                head.next->pre = cur;
            }
            head.next = cur;

            return cur->value;
        } else {
            return -1;
        }
    }

    void set(int key, int value) {
        if (map[key]) {
            node *cur = map[key];
            cur->value = value;
            get(key);
            return;
        }
        node *ele = new node(key, value);
        map[key] = ele;
        ele->next = head.next;
        ele->pre = &head;
        if (head.next) {
            //bug here head.next can be null
            head.next->pre = ele;
        } else {
            tail = ele;
        }
        head.next = ele;
        if (cur_capa < capacity) {
            cur_capa++;
        } else {
            node *tmp = tail->pre;
            tmp->next = NULL;
            map.erase(tail->key);
            delete[] tail;
            tail = tmp;
        }
    }

};
---------------------------------------- read codes -------------------------------------------------------
https://oj.leetcode.com/discuss/20619/c-11-code-74ms-hash-table-list
class LRUCache { public: LRUCache(int capacity) : _capacity(capacity) {} int get(int key) { auto it = cache.find(key); if (it == cache.end()) return -1; touch(it); return it->second.first; } void set(int key, int value) { auto it = cache.find(key); if (it != cache.end()) touch(it); else { if (cache.size() == _capacity) { cache.erase(used.back()); used.pop_back(); } used.push_front(key); } cache[key] = { value, used.begin() }; } private: typedef list<int> LI; typedef pair<int, LI::iterator> PII; typedef unordered_map<int, PII> HIPII; void touch(HIPII::iterator it) { int key = it->first; used.erase(it->second.second); used.push_front(key); it->second.second = used.begin(); } HIPII cache; LI used; int _capacity; };