Can't seem to find problem in my C++ solution [FIXED - posted accepted solution]


  • 0
    B

    My understanding is:

    get(key):
    if it exists in cache, then promote that node to the front and return the value
    if it doesn't exist in cache, return -1
    
    set(key, value):
    if it exists in cache, then update the value of the node, and then promote it to front
    if it doesn't exist in cache, then:
    1) if cache is full. Remove last node, then add new node to the front
    2) if cache isn't full, add new node to front
    

    Please help me understand why I get a runtime error! Thanks.

    class LRUCache{
        public:
            int capacity_;
            map<int, list<int>::iterator> lru;
            list<int> lruList;
            
            LRUCache(int capacity) {
                capacity_ = capacity;    
            }
            
            // make the touched node most recently used by adding a new node to head
            // remove the touched node from it's old position in O(1)
            void promote(int key, list<int>::iterator it) {
                lruList.push_front(*it);
                lruList.erase(it);
                lru[key] = lruList.begin();
            }
            
            int get(int key) {
                if(lru.find(key) == lru.end())
                    return -1;
                list<int>::iterator it = lru[key];
                int value = *it;
                // if we're not already promoted then promote the node
                if(it != lruList.begin()) {
                    promote(key, it);
                }
                return value;
            }
            
            void set(int key, int value) {
                // if it doesn't exist in cache
                if(lru.find(key) == lru.end()) {
                    // if cache is full, remove LRU element
                    if(lruList.size() == capacity_) {
                        list<int>::iterator end = lruList.end();
                        lru.erase(*end);
                        lruList.pop_back();
                    }
                    // add new element to cache and add it to front
                    lruList.push_front(value);
                    lru[key] = lruList.begin();
                }
                // exists in cache, update the value of the node, then promote it
                else {
                    list<int>::iterator node = lru[key];
                    *node = value;
                    promote(key, node);
                }
            }
        };

  • 0
    B

    Nevermind, fixed the problem. I had to store both key and value in the map as well as the lruList. Also, list::end() doesn't give the last element, to access last element, I need --lruList.end();

    Now, the modified version contains LRU element at the front, and MRU element at the back.

    Here is the working ACCEPTED solution:

    class LRUCache{
    public:
        int capacity_;
        map<int, list< pair<int,int> >::iterator> lru;
        list< pair<int,int> > lruList;
        
        LRUCache(int capacity) {
            capacity_ = capacity;    
        }
        
        // make the touched node most recently used by adding a new node to head
        // remove the touched node from it's old position in O(1)
        void promote(int key, list< pair<int,int> >::iterator it) {
            lruList.push_back(make_pair(it->first, it->second));
            lruList.erase(it);
            lru[key] = --lruList.end();
        }
        
        int get(int key) {
            if(lru.find(key) == lru.end())
                return -1;
            list< pair<int,int> >::iterator it = lru[key];
            int value = it->second;
            // if we're not already promoted then promote the node
            if(it != --lruList.end()) {
                promote(key, it);
            }
            return value;
        }
        
        void set(int key, int value) {
            // if it doesn't exist in cache
            if(lru.find(key) == lru.end()) {
                // if cache is full, remove LRU element
                if(lruList.size() == capacity_) {
                    list< pair<int,int> >::iterator lruIt = lruList.begin();
                    lru.erase(lruIt->first);
                    lruList.pop_front();
                }
                // add new element to cache and add it to front
                lruList.push_back(make_pair(key,value));
                lru[key] = --lruList.end();
            }
            // exists in cache, update the value of the node, then promote it
            else {
                list< pair<int,int> >::iterator node = lru[key];
                node->second = value;
                promote(key, node);
            }
        }
    };

Log in to reply
 

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