extremely clean and easy C++ code


  • 1
    R

    still use hashtable+list, but very very very easy to read and understand

    class LRUCache {
    public:
        LRUCache(int capacity) {
            maxsize=capacity;
        }
        void touch(int key){
            //erase in list if exist
            if(hashtable.find(key) != hashtable.end()) blist.erase(hashtable[key].ptr);
            //if size full, remove least recently used things
            if(blist.size()==maxsize){
                int rm_key = blist.back();
                hashtable.erase(rm_key);
                blist.pop_back();
            }
            //add our new key
            blist.push_front(key);
            hashtable[key].ptr = blist.begin();
        }
        
        int get(int key) {
            if(hashtable.find(key) == hashtable.end()) return -1;
            touch(key);
            return hashtable[key].val;
        }
        void put(int key, int value) {
            touch(key);
            hashtable[key].val=value;
            return;
        }
        
        struct Bucket{
            int val;
            list<int>::iterator ptr;
        };
        unordered_map<int,Bucket> hashtable; //key -> bucket
        list<int> blist; // list with key  back is least used/front is newly used
        int maxsize;
        
    };
    

Log in to reply
 

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