146. LRU Cache

class LRUCache {
public:
    LRUCache(int capacity) : capacity(capacity) {

    }

    int get(int key) {
        if (!cache.count(key)) return -1;
        auto it = cache[key];
        history.splice(begin(history), history, it);
        return it->second;
    }

    void put(int key, int value) {
        if (cache.count(key)) {
            auto it = cache[key];
            history.splice(begin(history), history, it);
            it->second = value;
            return;
        }
        if (capacity == size(cache)) {
            auto key_to_delete = history.back().first;
            history.pop_back();
            cache.erase(key_to_delete);
        }
        cache[key] = history.emplace(begin(history), key, value);
    }

    unordered_map<int, list<pair<int, int>>::iterator> cache;
    list<pair<int, int>> history;
    int capacity;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

class LRUCache{
public:
    LRUCache(int capacity) : m_capacity(capacity) {}

    int get(int key) {
        auto it(cache.find(key));
        if (it == cache.end()) return -1;
        history.splice(history.begin(), history, it->second); // 把找到的键值对放到链表首表明是最新被访问的
        return it->second->second;
    }

    void set(int key, int value) {
        auto it(cache.find(key));
        if (it != cache.end()) {
            history.splice(history.begin(), history, it->second);
            it->second->second = value;
            return; // cache不需要增加新的键值对，直接返回
        }
        if (cache.size() == m_capacity) { // 一定要先删后加！！！
            auto key_to_be_deleted = history.back().first;
            history.pop_back(); // 弹出最近最少被访问的键值对
            cache.erase(key_to_be_deleted);
        }
        history.emplace_front(key, value); // 把最新的键值对插入链表首
        cache[key] = history.begin();
        // cache[key] = history.insert(begin(history), {key, value});
    }

private:
    unordered_map<int, list<pair<int, int> >::iterator> cache;
    list<pair<int, int> > history;
    size_t m_capacity;
};