c++ hr + list


  • 0
    G
    class LRUCache {
    public:
        
        typedef int key_t;
        typedef int val_t;
        typedef list<pair<key_t,val_t> > list_t;
        typedef list_t::iterator list_iter_t;
        
        unordered_map<key_t,list_iter_t> map;
        list_t lru;
        int cap;
        
        LRUCache(int capacity)
        :cap(capacity){
            
        }
        
        int get(int key) {
            if(map.find(key) == map.end()){
                return -1;
            }
            
            list_iter_t iter = map[key];
            auto p = *iter;
            lru.erase(iter);
            lru.push_front(p);
            map[key] = lru.begin();
            return p.second;
        }
        
        void evict(){
            auto iter = prev(lru.end());
            map.erase(iter->first);
            lru.erase(iter);
        }
        
        void put(int key, int value) {
            if(map.find(key) == map.end()){
                if(map.size() >= cap){
                    evict();
                }
            }
            else{
                lru.erase(map[key]);
            }
            
            lru.push_front({key,value});
            map[key] = lru.begin();
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.