C++面试可能会用到的Cache

LRUCache

• 描述：考虑维护一个按照最近的使用时间来排序的链表，查询操作去哈希表中查当前key所对应的节点的指针，然后把该节点删除后再插入到链表首。插入操作的话先查询当前的key是否存在，如果存在的话先把当前key所对应的节点删除；如果链表已经满了的话就把链表尾部的元素删除，考虑完这两种情况以后插入操作就可以直接插入在链表前端，同时在哈希表中记录一下当前的指针即可。

class LRUCache {
public:
	struct LRUNode {
		int key, value;
		LRUNode(int k, int v) : key(k), value(v) {}
	}

	list<LRUNode> List;
	unordered_map<int, list<LRUNode>::iterator> Dict;
	int cnt, capa;

   	LRUCache(int capacity) {
		capa = capacity, cnt = 0;
    }
    
    	int get(int key) {
		auto it = Dict.find(key);
		if (it == Dict.end())
			return -1;
		int value = it->second->value;
		erase(it->second);
		put(key, value);
		return value;
    }

	void erase(list<LRUNode>::iterator it) { 
		Dict.erase(it->key);
		List.erase(it);
		--cnt;
	}
    
   	 void put(int key, int value) {
		if (Dict.find(key) != Dict.end()) 
			erase(Dict.find(key));
		if (cnt == capa) { 
			auto tail = List.end();
			erase(--tail);
		}
		List.push_front((LRUNode){key, value});
		Dict[key] = List.begin();
		cnt = cnt + 1; 
    }
};