Easy to understand C++ solution using splice function


  • 0
    W

    This is a classic example of LRU implementation using list splice function. You may easily change this to a generic implementation of LRU cache with arbitrary data containers. Currently beats >80% submissions.

    class LRUCache {
    public:
        LRUCache(int capacity) : _c(capacity) {}     
        
        int get(int key) {
            auto itr = _s.find(key);
            if(itr == _s.end()) return -1;
            auto l_itr = itr->second;
            _l.splice(_l.begin(), _l, l_itr);
            return l_itr->second;
        }
        
        void put(int key, int value) {
            auto sitr = _s.find(key);
            if(sitr != _s.end()){
                _s.erase(sitr);
                _l.erase(sitr->second);
            }
            else if(_l.size() >= _c){
                auto itr = _l.end();
                --itr;
                _s.erase(itr->first);
                _l.erase(itr);
            }
            _l.emplace_front(key, value);
            _s[key] = _l.begin();
        }
    
    private:
        typedef pair<int, int> item; // key, value
        list<item> _l;
        typedef list<item>::iterator itype;
        unordered_map<int, itype> _s;
        int _c;
    };
    

Log in to reply
 

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