Clean C++ with detailed comments


  • 0
    G
    class LRUCache{
    public:
        
        typedef list<pair<int,int> >::iterator Iter;
        
        //
        // A nice feature of STL lists is that
        // iterators don't get invalidated when
        // operating on the list. Even when deleting.
        //
        
        list<pair<int,int> > LRU;
        
        //
        // Hash table from the key to a list iterator
        //
        
        unordered_map<int,Iter> Cache;
        
        //
        // keep track of the capacity
        //
        
        int Cap;
        
        LRUCache(int capacity) 
        :
        Cap(capacity)
        {
        }
        
        //
        // Move an element from a location in the list
        // to the front of the list and update the cache
        // with the new iterator
        //
        
        void MoveToFront(int Key)
        {
            auto Found = Cache.find(Key);
            auto P = *(Found->second);
            LRU.erase(Found->second);
            auto I = LRU.insert(LRU.begin(),P);
            Found->second = I;
        }
        
        int get(int key) 
        {
            auto Found = Cache.find(key);
            
            if(Found == Cache.end())
            {
                return (-1);
            }
            
            MoveToFront(key);
            return (LRU.front().second);
        }
        
        void set(int key, int value) 
        {
            auto Found = Cache.find(key);
            
            //
            // element already exists in the cache
            // just need to update its value
            //
            
            if(Found != Cache.end())
            {
                MoveToFront(key);
                LRU.front().second = value;
                Cache[key] = LRU.begin();
                return;
            }
            
            //
            // element doesnt exist in cache
            // and capacity will be exceeded
            //
            
            if(Cache.size() == Cap)
            {
                int K = LRU.back().first;
                LRU.pop_back();
                Cache.erase(K);
            }
            
            auto I = LRU.insert(LRU.begin(),{key,value});
            Cache[key] = I;
        }
    };

Log in to reply
 

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