146_LRUCache.txt

//哈希链表法
//哈希表与双向链表的结合
//利用哈希表查找快的特点和双向链表插入删除快的特点
class LRUCache {
private:
    int capacity_;//容量
    list<pair<int,int>> cache;
    unordered_map<int,list<pair<int,int>>::iterator> map;
public:
    LRUCache(int capacity) {
        this->capacity_ = capacity;
    }
    
    int get(int key) {
        if(map.find(key)==map.end())
            return -1;//没找到返回-1
        //找到了准备更新位置
        else{
            pair<int,int> newkey = *map[key];//新建一个pair存着当前秘钥
            cache.erase(map[key]);//先把他删了
            cache.push_front(newkey);//再往队头插入
            map[key] = cache.begin();
            return newkey.second;
        }
    }
    void put(int key, int value) {
        if(map.find(key)!=map.end())
            cache.erase(map[key]);//如果找到了就先把它删了之后再写入
        else{
            if(map.size() == capacity_){//如果已经满了，则要删除队尾元素
                map.erase((cache.back()).first);
                cache.pop_back();//cache和map中数据都要删除
            }
        }
        cache.push_front(make_pair(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);
 */