146题：LRU缓存

题目

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

问题简述

我们需要在O(1)的平均复杂度内得到对应的值，所以我们需要利用哈希表来存储（也就是std::unordered_map）。同时，删除也需要我们有O(1)的时间复杂度，所以我们需要利用双向链表存储键值对。
这里我们需要用到链表拼接函数splice()，表示该节点刚刚用过，然后移动到链表头部。

void splice( const_iterator pos, list& other, const_iterator it );

这个函数声明表示it指向的节点移动到other的pos指向的节点。

template< class... Args >
void emplace_front( Args&&... args );

可以看见，emplace_front()是一个变长函数模板，所以我们可以直接利用该函数插入一个std::pair<int,int>。

代码

class LRUCache {
    using MAP_ITER = std::list<std::pair<int,int>>::iterator;
public:

    LRUCache(int capacity): capacity_(capacity) {

    }
     
    int get(int key) {
         auto find_key = lru_map.find(key);
         if(find_key==lru_map.cend())
            return -1;
         map_list.splice(map_list.cbegin(), map_list, find_key->second);
         return find_key->second->second;
    }
    
    void put(int key, int value) {
        auto find_key = lru_map.find(key);
        if(find_key!=lru_map.cend())
        {
            find_key->second->second = value;
            map_list.splice(map_list.cbegin(), map_list, find_key->second);
            return;
        }
        if(map_list.size()>=capacity_)
        {
            std::pair<int,int> pair_back = map_list.back();
            lru_map.erase(pair_back.first);
            map_list.pop_back();
        }
        map_list.emplace_front(key, value);
        lru_map[key] = map_list.begin();

    }
private:
    int capacity_;
    std::list<std::pair<int,int>> map_list;
    std::unordered_map<int, MAP_ITER> lru_map;
};

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

这里的get()函数思路很简单，首先判断哈希表里面有没有对应的key,如果找不到直接返回-1。如果找到了，由于这个key值刚刚用过，所以我们需要利用splice()函数将该节点置前，表示这个key值刚刚用过。
put()函数同样先查找有没有对应的key值，如果有，需要更新对应的value值(find_key->second->second=value)并将该节点置前。接着判断是否已经越界。如果越界，需要删除对应的哈希值并弹出链表的尾部值。接着，我们利用emplace_back()插入新的键值对，并更新哈希表的值。