LRUCache

LRUCache.cc

class LRUCache{
public:
    LRUCache(int capacity) {
        total = capacity;
        current = 0;
    }

    int get(int key) {
        auto it = m.find(key);
        if (it == m.end()) {
            return -1;
        }
        int v = it->second->first;
        l.erase(it->second);
        m[key] = l.insert(l.begin(), pair<int, int>(v, key));
        return v;
    }

    void set(int key, int value) {
        auto it = m.find(key);
        if (it == m.end()) {
            if (current == total) {
                auto iit = l.end();
                --iit;
                m.erase(m.find(iit->second));
                l.erase(iit);
            } else {
                ++current;
            }
        } else {
            l.erase(it->second);
        }
        m[key] = l.insert(l.begin(), pair<int, int>(value, key));
    }
private:
    int total;
    int current;
    list<pair<int, int> > l;
    map<int, list<pair<int, int> >::iterator> m;
};