[数据结构与算法]LeetCode-146. LRU 缓存

请你设计并实现一个满足??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) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); ? ?// 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); ? ?// 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); ? ?// 返回 -1 (未找到)
lRUCache.get(3); ? ?// 返回 3
lRUCache.get(4); ? ?// 返回 4
?

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

重新又写了一次，时隔多年。唉

#include<iostream>
#include<list>
#include<unordered_map>
using namespace std;
class LRUCache {
public:
	LRUCache(int capacity) {
		this->cur = 0;
		this->cap = capacity;
	}

	int get(int key) {
		if (m_Hash.count(key) == 0) {
			return -1;
		}
		cache c{};
		c.key = m_Hash[key]->key;
		c.value = m_Hash[key]->value;
		m_list.erase(m_Hash[key]);
		m_list.push_back(c);
		m_Hash[key] = (--m_list.end());

		return c.value;
	}

	void put(int key, int value) {
		/* 没找到 */
		cache c;
		c.key = key;
		c.value = value;
		if (m_Hash.count(key) == 0) {
			if (cur < cap) {
				m_list.push_back(c);
				cur++;
			}
			else {
				int key = m_list.front().key;
				m_list.pop_front();
				m_Hash.erase(key);
				m_list.push_back(c);
			}
			m_Hash[key] = (--m_list.end());
		}
		/* 找到了 */
		else {
			list<cache>::iterator it = m_Hash[key];
			m_list.erase(it);
			m_list.push_back(c);
			m_Hash[key] = (--m_list.end());
		}
	}

private:
	typedef struct _cache {
		int key;
		int value;
	}cache;
	int cur;                                             /*记录当前LRU的长度 */
	int cap;                                             /* 记录LRU的长度 */
	list<cache>    m_list;                               /* 双向链表 */
	unordered_map<int, list<cache>::iterator> m_Hash;     /* 哈希表 */
};

/**
 * 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);
 */
 //["LRUCache", "put", "put", "get", "put", "put", "get"]
 //[[2], [2, 1], [2, 2], [2], [1, 1], [4, 1], [2]]

//["LRUCache", "put", "put", "get", "put", "get", "get"]
//[[2], [2, 1], [1, 1], [2], [4, 1], [1], [2]]

int main() {

	LRUCache* L = new LRUCache(2);
	L->put(2, 1);
	L->put(1, 1);

	cout << L->get(2) << endl;
	L->put(4, 1);
	cout << L->get(1) << endl;
	cout << L->get(2) << endl;


	system("pause");
	return 0;
}