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.

题意，思路：
参考： http://bangbingsyb.blogspot.com/2014/11/leetcode-lru-cache.html LRU的核心在于维护一个按先后顺序排列key的数据结构。

• 进行get(key)操作之后，需要更新当前key的访问顺序；

• 进行set(key, value)操作之后

  • 如果容量未满，则仅需要更新当前key的访问顺序；
  • 如果容量已满，则先删除最“老”的key，再更新当前key的访问顺序。

• $$O(1)$$时间查找key，需要用hashmap来储存数据。

• $$O(1)$$时间更新顺序。（1）我们需要一个数据结构来顺序存放“访问”或添加的key。（2）考虑到$$O(1)$$时间复杂度，我们考虑用链表来实现，并且在hashmap中储存结点指针。 （3）更新key的访问时，需要对链表结点进行删除，因此考虑采用双链表的数据结构。
• 当给定一个key的时候，我们需要知道这个key对应的value，以及这个key对应的结点。因此我们设计如下的数据结构：

    struct item{
        int key, value;
        item* prev, *next;
        item(int k, int v) : key(k), value(v), prev(NULL), next(NULL) {}
    };
  

  对于整个cache，用map和双链表来表示：

    map<int, *item> record;
    item *head, *tail;
    int max_capacity, curr;
  

需要实现的操作有：

• update(key): 更新一个key对应的node，将record[key]移动到双链表表头；
• addHead(item* node): 添加一个node至表头；
• deleteTail(): 在表尾删除一个node。
• 注意链表中没有node或只有一个node的情况；以及移动的node为表头或表尾的特殊情况

    LRUCache(int capacity) {
        // initialize
        max_capacity = capacity;
        curr = 0;
        head = NULL;
        tail = NULL;
    }
    int get(int key) {
        if ( record.find(key) == record.end() ) return -1;
        update(key);
        return record[key]->value;
    }

    void set(int key, int value) {
        if ( record.find(key) == record.end() ) {
            if ( curr == max_capacity ) deleteTail();
            else curr += 1;
            item *tmp = new item(key, value);
            record[key] = tmp;
            addHead(tmp);
            return;
        }
        if ( record.find(key) != record.end() ) {
            record[key]->value = value;
            update(key);
            return;
        }
    }

对于每一个操作，注意考虑细节和corner case。

    void deleteTail() {
        if ( tail == NULL ) return;
        item *n = tail->next;
        // remove it from the record
        record.erase(record.find(tail->key));
        // free the memory
        delete tail;
        if ( n != NULL ) n->prev = NULL;
        else head = NULL; // consider one node in the list
        tail = n;
    }

    void addHead(item* node) {
        if ( head == NULL ) { // add to an empty list
            head = node; 
            tail = node; 
            return;
        } 
        head->next = node;
        node->prev = head;
        head = node;
        // make sure it is appropriately terminated.
        head->next = NULL;
    }

    void update(int key) {
        if ( record[key] == head ) return;
        if ( record[key] == tail ) {
            // delete the tail (but not erase it from record)
            item* n = tail->next;
            n->prev = NULL;
            tail = n;
            addHead(record[key]);
            return;
        }
        // delete a "normal" node in the middle
        item *n = record[key]->next, *p = record[key]->prev;
        p->next = n;
        n->prev = p;
        addHead(record[key]);
    }

Notes 这题怎么可能一次写对啊。。。。