146. LRU 缓存

我们使用了一个双向链表cache来存储数据，同时使用一个哈希表hash_map来映射键和链表节点的迭代器。当调用get(key)函数时，我们首先检查hash_map中是否存在该key，如果存在则将之前位置移到链表头部并返回值；当调用put(key, value)函数时，我们先检查hash_map中是否存在该key，存在的话将该节点从链表中删除，不管存在与否都需要考虑是否需要删除旧数据（缓存已满的情况）。

class LRUCache {
private:int _capacity;list<pair<int, int>> _cache;unordered_map<int, list<pair<int, int>>::iterator> _hashmap;public:LRUCache(int capacity) {_capacity = capacity;}int get(int key) {if (_hashmap.find(key) == _hashmap.end()) {return -1;}auto iter = _hashmap[key];int value = iter->second;_cache.erase(iter);_cache.push_fron