BM100 设计LRU缓存结构

基本思想：hash结构m_db存储key-value。链表结构m_link存储最近set的key值，key值在链表中的位置越后，key值越新。m_keyLink存储的是key和std::list<int>::iterator（就是key值在m_link对应的位置）。

class Solution {
public:
    Solution(int capacity){
         // write code here
         m_capacity=capacity;
    }

    int get(int key) {
         // write code here
         auto it=m_db.find(key);
         int res=-1;
         if(it!=m_db.end()){
            res=it->second;
            updateLocation(key);
         }
         return res;
    }

    void set(int key, int value){
         // write code here
        auto it=m_db.find(key);
        if(it!=m_db.end()){
            it->second=value;
            updateLocation(key);
        }else{
            if(m_cached<m_capacity){
                insertNewOne(key,value);
            }else{
                deleteOldOne();
                insertNewOne(key,value);
            }
        }

    }
private:
    void updateLocation(const int &key){
        auto map_it=m_keyLink.find(key);
        if(map_it!=m_keyLink.end()){
            auto list_it=map_it->second;
            m_link.erase(list_it);
            auto new_it=m_link.insert(m_link.end(),key);
            map_it->second=new_it;
        }
    }
    void deleteOldOne(){
        if(m_cached>0){
            auto list_it=m_link.begin();
            if(list_it!=m_link.end()){
                int key=(*list_it);
                m_link.erase(list_it);
                auto map_it=m_keyLink.find(key);
                if(map_it!=m_keyLink.end()){
                    m_keyLink.erase(map_it);
                }
                auto db_it=m_db.find(key);
                if(db_it!=m_db.end()){
                    m_db.erase(db_it);
                }
                m_cached--;
            }


        }

    }
    void insertNewOne(const int &key,const int &value){
         m_db.insert(std::make_pair(key,value));
         auto list_it=m_link.insert(m_link.end(),key);
         m_keyLink.insert(std::make_pair(key,list_it));
         m_cached++;
    }
    typedef std::list<int>::iterator Loc;
    std::unordered_map<int,Loc> m_keyLink;
    std::list<int> m_link;
    std::unordered_map<int,int> m_db;
    int m_cached=0;
    int m_capacity=0;

};