LRU(最近最少使用) 缓存题与该算法思路

题：https://leetcode.cn/problems/lru-cache/description/

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

解题（题解说明见注释）

/*
采用hash map和list结合方式，让hash map达到O(1)的访问性能，让list根据元素的顺序实现最近访问的过程。
思路：
1. 每次读或写元素，表示该元素最近被访问了，则把该元素移动至List队首，这样能保证第一个元素是最近访问的，最后一个元素是最近最少访问的。
2. 如果新增的元素数量大于设置的容量，则每次直接删除最后一个元素即可，实现了最近最少使用则清除的要求。
3. 若只用list查找性能太差，则使用哈希map存放key-list元素指针的方式，实现能直接访问List元素的目的，达到o(1)的时间复杂度。

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

    }
    
    int get(int key) {
        auto map_it = cacheMap.find(key);
        if (map_it != cacheMap.end()) {
            // 如果找到了，则把元素移动到队首表示最近访问过，并返回value
            cacheData.splice(cacheData.begin(), cacheData, map_it->second);
            return map_it->second->second;
        }
        return -1;

    }
    
    void put(int key, int value) {
        auto map_it = cacheMap.find(key);
        // 如果找到了则更新value
        if (map_it != cacheMap.end()) {
            // 更新过值也表示最近访问过，需把该元素移动到队首
            cacheData.splice(cacheData.begin(), cacheData, map_it->second);
            map_it->second->second = value;
            return;
        }
        // 如果没有找到，则新建一元素节点，放在队首
        cacheData.emplace_front(key, value);
        cacheMap[key] = cacheData.begin();
        // 如果超过了容量，则把队尾一直没被访问过的元素删除了
        if(cacheMap.size() > capacity) {
            cacheMap.erase(cacheData.back().first);
            cacheData.pop_back();
        }

    }
private:
    int capacity;
    // cacheData存放的是一个元素pair，一个pair是<key, value>的结对，
    // 要同时存key的原因是需要在删除元素时知道这个元素的key，才能保证删除元素也是O（1）
    std::list<std::pair<int, int>> cacheData;
    // key对于一个List元素节点，通过该元素的迭代器指针能直接找到list元素，以免List每次从头遍历耗时
    unordered_map<int, std::list<std::pair<int, int>>::iterator> cacheMap;
};

 /*
 list.splice() 将一个List的元素移动到当前list的指定位置，如：
 list1.splice（p1, list2, p2）是将list2中p2指向的节点移动到list1的p1之前，
 完成后list2中不再有p2，单纯的指针赋值，不会进行（移动）构造析构等操作。
 如果是list1.splice(p1, list1, p2)则是对list1自己的元素调整顺序，须得p2移动到p1前边。

 list.splice()有三个重载：
 1. void splice (iterator position, list& x);	移动整个list
 2. void splice (iterator position, list& x, iterator i);	移动单个元素
 3. void splice (iterator position, list& x, iterator first, iterator last);	移动指定范围的元素

 */

注：题解思路来源于题评论