GNU GCC passed, but leetcode runtime error


  • 0
    D

    Hi there,

    I wrote a code of LRUCache and it works good on GNU GCC, but leetcode says runtime error. I wonder whether you could provide more information on the runtime error? Thank you very much!

    My code is as following:

    class LRUCache{
    public:
        LRUCache(int capacity) : cap(capacity){
    
        }
    
        int get(int key) {
            if(cache.find(key) == cache.end()){
                return -1;
            }
            //if find out the key
            order.erase(findIt[key]);
            order.push_back(key);
            return cache[key];
        }
    
        void set(int key, int value) {
            if(cache.find(key) == cache.end()) {
                if(cache.size() >= cap) {
                    cache.erase(*(order.begin()));
                    order.erase(order.begin());
                    cache[key] = value;
                    order.push_back(key);
                    findIt[key] = order.rbegin().base();
                }else {
                    cache[key] = value;
                    order.push_back(key);
                    findIt[key] = order.rbegin().base();
                }
            }else {
                cache[key] = value;
                order.erase(findIt[key]);
                order.push_back(key);
                findIt[key] = order.rbegin().base();
            }
        }
    private:
        unordered_map<int, int> cache;
        unordered_map<int, list<int>::iterator> findIt;
        list<int> order;
        int cap;
    };

  • 0
    Z

    You map the key to the iterator.
    Are you sure it is still correct mapped after you modify the list "order"?
    The iterator might be changed when you do the erase and push_back.


  • 1
    Y

    When you get(), you should refresh the 'findIt' at the same time. What's more, you can't use order.rbegin().base(); it is an fix number(I don't know why, but I test your code). I modify your code, it will be accepted:

    class LRUCache{
    public:
    LRUCache(int capacity) : cap(capacity){
    
    }
    
    int get(int key) {
    	if (cache.find(key) == cache.end()){
    		return -1;
    	}
    	order.erase(findIt[key]);
    	order.push_back(key);
    	list<int>::iterator it = order.end();
    	it--;
    	findIt[key] = it;
    	return cache[key];
    }
    
    void set(int key, int value) {
    	if (cache.find(key) == cache.end()) {
    		if (cache.size() >= cap) {
    			cache.erase(*(order.begin()));
    			order.erase(order.begin());
    			cache[key] = value;
    			order.push_back(key);
    			list<int>::iterator it = order.end();
    			it--;
    			findIt[key] = it;
    		}
    		else {
    			cache[key] = value;
    			order.push_back(key);
    			list<int>::iterator it = order.end();
    			it--;
    			findIt[key] = it;
    		}
    	}
    	else {
    		cache[key] = value;
    		order.erase(findIt[key]);
    		order.push_back(key);
    		list<int>::iterator it = order.end();
    		it--;
    		findIt[key] = it;
    	}
    }
    private:
    unordered_map<int, int> cache;
    unordered_map<int, list<int>::iterator> findIt;
    list<int> order;
    int cap;
    };

  • 0
    S

    This is guaranteed for std::list. Since "lists have the important property that insertion and splicing do not invalidate iterators to list elements" (http://www.sgi.com/tech/stl/List.html)


  • 0
    Y

    After looking for some informations, order.rbegin().base() means the front iterator of order.rbegin(), so order.rbegin().base() ==order.end().


Log in to reply
 

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