题：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); 移动指定范围的元素
*/
注：题解思路来源于题评论