LRU缓存机制

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

你是否可以在 O(1) 时间复杂度内完成这两种操作？

实例：

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

思考：

在O(1)的时间复杂度里面完成对key对应val的获取，肯定是使用hash map的方式；同时需要考虑LRU，
可以使用链表，通过erase(list iterator)来完成O(1)时间内的删除元素，同时将最近使用的元素放到链表的头或者尾部;
(1)get函数，通过hash map查找是否存在对应的key，不存在则返回-1；
存在则将使用过的元素放置到链表的头部；
(2)put函数，先对该key值进行搜索是否存在，如果存在，则直接修改原来对应的val，同时将其放到链表的头部（表示最近被使用）；
如果不存在，则需要考虑是否队列已经满了，如果已经满了，则需要将链表尾部的元素移除，再将新的元素移入；

题目的难点在于设计数据结构完成操作。

1.使用hash map在时间复杂度O(1)的查找key值对应的val；
2.同时要在O(1)时间内找到对应链表的节点，完成在原链表中的移除并且添加到链表头部；
因此设计的时候应该是 unordered_map<key, list::iterator>
3.在这个缓冲区满的时候，找到list对应的节点进行删除，同时还需要删除原hash map中的内容，
所以需要从list中需要存储key值，这样才能返回hash map中去删除元素
list<pair<key, val>> unordered_map<key, list<pair<key, val>>::iterator>

代码：

class LRUCache {
public:
    LRUCache(int capacity) {
        this->max_cap = capacity;
        this->LRUMap.clear();
        this->LRUList.clear();
    }
    
    // 通过key来获取val，这里不仅要判断key是否存在，同时要考虑如果存在则使用了要将该数值放在队列的头部
    int get(int key) {
        unordered_map<int, list<pair<int, int>>::iterator>::iterator iter = this->LRUMap.find(key);
        if(iter == this->LRUMap.end()) {
            return -1;
        }else {
            // 处理LRU缓冲队列
            int value = iter->second->second;
            LRUList.erase(iter->second);
            pair<int, int> pair_ = make_pair(key, value);
            LRUList.push_front(pair_);
            this->LRUMap[key] = this->LRUList.begin();
            return value;
        }
    }
    
    // 添加一个数值的时候首先判断是否已经存在了
    void put(int key, int value) {
        unordered_map<int, list<pair<int, int>>::iterator>::iterator iter_ = this->LRUMap.find(key);
        if(iter_ != this->LRUMap.end()) {
            list<pair<int, int>>::iterator _iter = iter_->second;
            this->LRUList.erase(_iter);
            this->LRUList.push_front(pair<int, int>(key, value));
            this->LRUMap[key] = this->LRUList.begin();
            return ;
        }
        if(this->LRUMap.size() == this->max_cap) {
            // 队满
            int key_ = this->LRUList.back().first;
            list<pair<int, int>>::iterator list_iter = this->LRUMap[key_];
            this->LRUList.erase(list_iter);
            this->LRUMap.erase(key_);
        }
        pair<int, int> pair_ = make_pair(key, value);
        this->LRUList.push_front(pair_);
        this->LRUMap[key] = this->LRUList.begin();
    }
private:
    int max_cap; // 最大容量
    unordered_map<int, list<pair<int, int>>::iterator> LRUMap;
    list<pair<int, int>> LRUList; // 用于判定清除哪一个元素,超过时候每次删除list尾巴
};

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