C++11 code 74ms - Hash table + List


  • 77
    A

    There is a similar example in Java, but I wanted to share my solution using the new C++11 unordered_map and a list. The good thing about lists is that iterators are never invalidated by modifiers (unless erasing the element itself). This way, we can store the iterator to the corresponding LRU queue in the values of the hash map. Since using erase on a list with an iterator takes constant time, all operations of the LRU cache run in constant time.

    class LRUCache {
    public:
        LRUCache(int capacity) : _capacity(capacity) {}
        
        int get(int key) {
            auto it = cache.find(key);
            if (it == cache.end()) return -1;
            touch(it);
            return it->second.first;
        }
        
        void set(int key, int value) {
            auto it = cache.find(key);
            if (it != cache.end()) touch(it);
            else {
    			if (cache.size() == _capacity) {
    				cache.erase(used.back());
    				used.pop_back();
    			}
                used.push_front(key);
            }
            cache[key] = { value, used.begin() };
        }
        
    private:
        typedef list<int> LI;
        typedef pair<int, LI::iterator> PII;
        typedef unordered_map<int, PII> HIPII;
        
        void touch(HIPII::iterator it) {
            int key = it->first;
            used.erase(it->second.second);
            used.push_front(key);
            it->second.second = used.begin();
        }
        
        HIPII cache;
        LI used;
        int _capacity;
    };

  • 3
    L

    I used the same method as yours, but runs double time. Then I find out the only difference is that I compare capacity with used.size() instead of cache.size(). After fixing the problem my program runs as fast as yours. But why does this make such a difference in running time?


  • 10
    A

    It makes sense, as you can see here: { http://en.cppreference.com/w/cpp/container/list/size }
    Depending on which C++ standard is used on the compiler, the size of a list is not stored explicitly, thus requiring a complete traversal to compute its size. On newer versions, all STL containers (including list) keep stored its size value, which makes the size() operation constant cost.


  • 0
    T

    Thanks for your answer. This tip also works for my cpp code, which can shorten a half time.


  • 0
    R

    The time cost difference for list.size() vs map.size() can be huge. I did not know that before. Your tip really helps! Thank you!

    @afernandez90


  • 6
    M

    Thanks for sharing this concise solution. Previously I used the splice method of std::list to update an element to the head of list. In this way the iterator stored in the hash table does not need to be updated. This is all good, but I sometimes forget the prototype of splice and needs to check. The way you use erase and push_front is certainly a good alternative (both are O(1) time).

    Here is the code (I used a bit different data structure).

    class LRUCache{
    public:
        LRUCache(int capacity):cap(capacity) {
            
        }
        
        int get(int key) {
            if(map.find(key) == map.end()) {
                return -1;
            }
            else {
                //lst.splice(lst.begin(),lst,map[key]);
                touch(map[key]);
                return lst.begin()->second;
            }
        }
        
        void set(int key, int value) {
            if(map.find(key) != map.end()) {
                //lst.splice(lst.begin(),lst,map[key]);
                touch(map[key]);
                lst.begin()->second = value;
            }
            else {
                if(map.size() == cap) {
                    int dkey = lst.back().first;
                    map.erase(dkey);
                    lst.pop_back();
                }
                lst.push_front({key,value});
                map[key] = lst.begin();
            }
        }
    private:
        typedef std::list<std::pair<int,int>> PList; // PAIR IS THE (KEY,VALUE) PAIR
        
        int cap;
        PList lst;
        std::unordered_map<int,PList::iterator> map;
        
        // UPDATE THE LIST AND THE MAP (AFTER UPDATE, IT WILL BE THE LIST HEAD)
        void touch(PList::iterator it) {
            int key = it->first;
            int value = it->second;
            lst.erase(it);
            lst.push_front({key,value});
            map[key] = lst.begin();
        }
    };
    

  • 0
    X

    This is a really helpful tip!


  • 1

    Hi, afernandez90. Great code! BTW, I want to know where comes the names LI, PII, HIPII? Are they abbreviations of some terminologies or just made up by yourself?


  • 0
    S

    May I ask is it possible to use iterator in Java? Since I didn't find a Java solution using iterator on solution share.


  • 0
    S

    I looked up the Java listIterator in LinkedList, the code of remove() is LinkedList.this.remove(lastReturned); which still call the remove() of LinkedList, which may take O(n). I don't know if it's different in C++. Please tell me if there's another way in Java


  • 0
    A

    Check out this: http://stackoverflow.com/questions/5732974/in-java-why-is-insertion-or-deletion-in-a-linked-list-a-constant-time-operation
    In Java, you can delete elements in constant time using iterators too.


  • 0
    A

    @jianchao.li.fighter Yes, they come from: LI = List on Integers, PII = Pair of Integer and Integer, HIPII = Hashtable of Integer to Pair of Integer and Integer. :)


  • 0
    L

    Really helpful discovery!


  • 0
    X

    One of the most elegant answer in this forum! Really like how you implement touch()!


  • 0
    S

    Hi @afernandez90 , I don't understand you notation. As far as LRU cache implementation is concerned, we have a page number associated with each page. When we access a page not present in the cache, we bring it into the cache...and so on. What is your notation here for a pageNumber and a page? Does the 'int' in list<int> signify page number? What do 'int's in unordered_map<int, pair<int, list<int>::iterator> > signify?


  • 0
    C

    It's a subtle but really helpful finding! I was also wondering the time differences until I read your reply. Thanks.


  • 0
    Y

    At first, I didn't understand this solution, but when you get it, you appreciate the smartness of it :)

    For those people who still have trouble understanding it, I put up a youtube video trying my best to explain this solution thoroughly and why it is fast

    LRU Cache explanation


  • 0
    A

    Yes, LI = List of Int, PII = Pair of (Int,Int), HIPII = Hashtable mapping from Int to PII :D


  • 0
    A

    Thanks buddy! Happy to help!


  • 0
    A

    your solution looks nice,but i think you should consider the test case : _capacity == 0, your code
    maybe get a runtime error.

    if (cache.size() == _capacity) {
    	cache.erase(used.back());
    	used.pop_back();
    }
    

Log in to reply
 

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