LRUCache

template<typename K, typename V>
class LRUCache {
public:
    LRUCache(int cap) : cap_(cap) {}
    void Set(const K &key, const V &value) {
        auto item = hash_.find(key);
        if (hash_.end() == item) {
            Add(key, value);
        } else {
            Change(key, value);
        }
    }
    V Get(const K &key) {
        auto item = hash_.find(key);
        if (hash_.end() == item) {
            return V(-1);
        }
        V val = item->second->second;
        Change(key, val);
        return val;
    }
    void Add(const K &key, const V &value) {
        if (cache_.size() + 1 > cap_) {
            Del(cache_.back().first);
        }
        cache_.push_front(make_pair(key, value));
        hash_[key] = cache_.begin();
    }
    void Del(const K &key) {
        auto item = hash_.find(key);
        cache_.erase(item->second);
        hash_.erase(key);
    }
    void Change(const K &key, const V &value) {
        Del(key);
        Add(key, value);
    }
private:
    int cap_;
    list<pair<K, V>> cache_;
    unordered_map<K, decltype(cache_.begin())> hash_;
};