20210705

LRU缓存机制
题目链接：https://leetcode-cn.com/problems/lru-cache/

思路：数据结构分为两个部分：数据被访问顺序的存储；数据的查询

• 存储数据被访问顺序的部分涉及中间删除、两头增删操作，因此采用链表
• 数据查询部分要求O(1)，因此想到用哈希表

综上，采用哈希表存储数据与链表迭代器的映射，链表存储数据的值，并维护被访问的顺序；当数据被访问或过期时，同步更新哈希表中的迭代器。

参考代码：

class LRUCache {
private:
    unordered_map<int, list<pair<int, int>>::const_iterator> _map;
    list<pair<int, int>> _list;
    int maxSize;
public:
    LRUCache(int capacity) {
        maxSize = capacity;
    }
    int get(int key) {
        unordered_map<int, list<pair<int, int>>::const_iterator>::const_iterator it = _map.find(key);
        if (it == _map.end()) {
            return -1;
        }
        int value = it->second->second;
        _list.erase(it->second);
        _list.push_front(make_pair(key, value));
        _map[key] = _list.cbegin();
        return value;
    }
    void put(int key, int value) {
        unordered_map<int, list<pair<int, int>>::const_iterator>::const_iterator it = _map.find(key);
        if (it != _map.end()) {
            _list.erase(it->second);
            _list.push_front(make_pair(key, value));
            _map[key] = _list.cbegin();
        }
        else {
            if (_map.size() < maxSize) {
                _list.push_front(make_pair(key, value));
                _map[key] = _list.cbegin();
            }
            else {
                list<pair<int, int>>::const_iterator end = _list.cend();
                --end;
                _map.erase(end->first);
                _list.pop_back();
                _list.push_front(make_pair(key, value));
                _map[key] = _list.cbegin();
            }
        }
    }
};