#include <iostream>
#include <unordered_map>
#include <list>
using namespace std;
typedef pair<int,int> PII;

class LRUCache{
    public: 
        LRUCache(int capcity)
        {
            _cap = capcity;
        }
        int get(int k)
        {
            if(mapkey.find(k) != mapkey.end())
            {    
                put(k,mapkey[k]->second);
                return mapkey[k]->second;
            }else return -1;
        }
        void put(int k,int v)
        {
            if(mapkey.find(k) != mapkey.end()){
            {   
                data.erase(mapkey[k]);
                size--;
            }
            }else if(size >= _cap)
            {   
                mapkey.erase(data.back().first);
                size--;
                data.pop_back();
            }
            data.push_front({k,v});
            mapkey[k] = data.begin();
            ++size;
        }
        void print(){
            for(auto &x : data){
                cout << x.first << " : " << x.second << endl;
            }
            cout << endl;
        }
    private:
        int _cap;
        int size;
        list<PII> data;
        unordered_map<int,list<PII> :: iterator> mapkey;
};
int main()
{
    auto lru = new LRUCache(3);
    lru->put(1,1);
    lru->put(2,2);
    lru->put(3,3);
    lru->put(4,4);
    lru->print();
    cout << lru->get(4) << endl;

    return  0;
}