/// 最近最少使用缓存(LRU)，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。
class LRUCache {
public:
    LRUCache(int capacity) : max_size(capacity) {
    }
    ///  获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
    int get(int key) {
      auto res = map.find(key);
      if(res != map.end()){
        list.splice(list.begin(), list, res->second);
        return res->second->second;
      } else {
        return -1;
      }
    }

    /// 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
    void put(int key, int value) {
      auto res = map.find(key);
      list.push_front(std::make_pair(key, value));
      if(res != map.end()){
        list.erase(res->second);
        map.erase(res);
      }
      map[key] = list.begin();

      if(map.size() > max_size){
        auto last = list.end();
        --last;
        map.erase(last->first);
        list.pop_back();
      }
    }

public:
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> map;
    std::list<std::pair<int, int>> list;
    int max_size = 0;
};