LRU缓存-实现哈希链表结合

class LRUCache {
private:int cap;list<pair<int ,int>> cache;unordered_map<int,list<pair<int,int>>::iterator> map;public:LRUCache(int capacity) {cap = capacity;}int get(int key) {if(!map.count(key)){//没找到return -1;}auto key_value = map[key];//huoqu链表地址cache.erase(key_value);//删除对应的pair，传递的参数是值cache.push_front(*key_value);//插入到链表头，传的参数是链表地址map[key] = cache.begin();//链表头return key_value->second;}void put(int key, int value) {if(!map.count(key)) {if (cache.size() == cap) {map.erase(cache.back().first);cache.pop_back();}}else{cache.erase(map[key]);}cache.push_front({key,value});map[key]=cache.begin();}
};/*** 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);*/

list是双向链表，从头插入代码 cache.push_front(make_pair<int,int>(key,value));

cache.erase()//参数是迭代器位置，也就是指针，地址，

cache.pop_back()//从尾部删除一个节点

cache.pop_font()//从头部删除一个节点

cache.insert(迭代器位置，元素)//在迭代器位置之前插入一个元素

hashmap的函数：

map.count(key);//如果找到了返回1，没找到返回0

map[key]=valie;//直接fuzhi

map.erase(key);//根据key删除元素。