leetcode上一个双向链表+哈希表的题（460. LFU缓存）

这个题简直就是对所学数据结构的一个汇总应用啊，太绝了，涉及list、map、hashmap，对还包含front()、back（）方法返回的是值，而begin（）方法返回的是迭代器指针，真的是一绝。
不往本子上记了，就记在博客下吧
一共定义了三个数据结构。
一个哈希表存放当前key对应的节点位置
一个频率表，用map，因为要根据频率进行排序，存放的是当前频率下，都有哪些节点，这时候用双向链表实现。
一个哈希表，存放当前key-frequency。

class LFUCache {
public:
    int capacity;
    int count = 0;
    unordered_map<int,list<pair<int,int>>::iterator> location;//记录每个节点所在频率链表的位置
    map<int,list<pair<int,int>>> frequence;//记录每个频率下有几个节点
    unordered_map<int,int> hashmap;//key-frequence记录每个节点及对应的频率
    LFUCache(int capacity) {
        this->capacity = capacity;
    }

    int get(int key) {
        if(capacity == 0 || !hashmap.count(key)) return -1;
        int oldfq = hashmap[key];
        int val = (*location[key]).second;
        frequence[oldfq].erase(location[key]);
        if(frequence[oldfq].empty()){
            frequence.erase(oldfq);
        }
        hashmap[key]++;//当前节点的频率值+1
        frequence[oldfq + 1].emplace_front(make_pair(key,val));//在频率表中重新插入该节点
        location[key] = frequence[oldfq + 1].begin();//重新改该节点的位置赋值
        return val;
    }

    void put(int key, int value) {
        if(capacity <= 0) return;//防止出现无效的情况
        if(hashmap.find(key) != hashmap.end()){//如果原先已经插入过当前值，进行更新
            int oldfq = hashmap[key];
            //去对应频率链表下删除那个节点
            frequence[oldfq].erase(location[key]);
            if(frequence[oldfq].empty()){
                frequence.erase(oldfq);
            }
            hashmap[key]++;//当前key对应的频率要+1
            frequence[oldfq + 1].emplace_front(make_pair(key,value));//在当前频率下插入最新节点
            //更新位置信息
            location[key] = frequence[oldfq + 1].begin();
            return;
        }
        //如果当前节点满了
        if(count == capacity){
            auto fre = frequence.begin();//此时返回的是指针
            auto listp = fre->second.back();//对于list返回的是最后一个数字对，而不是迭代器指针
            int n = listp.first;
            hashmap.erase(n);//频率表删除当前节点
            location.erase(n);//位置表删除
            fre->second.pop_back();//当前链表中删除这个节点
            if(fre->second.empty()){
                frequence.erase(fre->first);
            }
            count--;
        }
        //插入新key-val
        hashmap[key] = 1;
        frequence[1].emplace_front(make_pair(key,value));
        location[key] = frequence[1].begin();//存放的是指针
        count++;
    }
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */