class cache{
private:
struct node{
int key;
int val;
node(int k, int v):key(k), val(v) {}
};
int capacity;
list<node> cl;
unordered_map<int, list<node>::iterator> mp;
public:
int get(int key){
if(mp.find(key) == mp.end()) return -1;
else{
cl.splice(cl.begin(), cl, mp[key]);
mp[key] = cl.begin();
return mp[key]->val;
}
}
void put(int key, int val){
if(mp.find(key) == mp.end()){
if(cl.size() == capacity){
mp.erase(cl.back().key);
cl.pop_back();
}
cl.push_front(node(key, val));
mp[key] = cl.begin();
}
else{
mp[key]->val = val;
cl.splice(cl.begin(), cl, mp[key]);
mp[key] = cl.begin();
}
}
};
