Leetcode-146-LRU Cache

这道题目还挺新颖的，要求我们根据需求来设计一个数据结构，使得查找和添加元素的复杂度都是。这题我直接参考了别人的做法（因为确实没什么思路），就当学习了。

代码摘自linz36的回答。

可以看到，这种解法把unordered_map和list结合起来了。我们首先熟悉一下这两种数据结构。unordered_map是关联容器，它存储由键值和映射值组合而成的元素，并允许基于键快速检索单个元素。无序映射实现了直接访问操作符(operator[])，该操作符允许使用键值作为参数直接访问映射值。list是一个线性双向链表结构，它的数据由若干个节点构成，每一个节点都包括一个信息块（即实际存储的数据）、一个前驱指针和一个后驱指针。由于其结构的原因，它可以迅速地在任何节点进行插入和删除操作。

class LRUCache {
public:
    int size;
    list<int> lru;                              // MRU ... LRU
    unordered_map<int, list<int>::iterator> mp; // key -> iterator
    unordered_map<int, int> kv;                 // key -> value

    LRUCache(int capacity) : size(capacity) {}
    int get(int key) {
        if (kv.count(key) == 0) return -1;
        updateLRU(key);
        return kv[key];
    }
    void put(int key, int value) {
        if (kv.size() == size && kv.count(key) == 0)
            evict();
        updateLRU(key);
        kv[key] = value;
    }
    void updateLRU(int key) {
        if (kv.count(key)) 
            lru.erase(mp[key]);
        lru.push_front(key);
        mp[key] = lru.begin();
    }
    void evict() {
        mp.erase(lru.back());
        kv.erase(lru.back());
        lru.pop_back();
    }
};

/**
 * 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);
 */