Easy to understand C++ solution using splice function

  • 0

    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 {
        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()){
            else if(_l.size() >= _c){
                auto itr = _l.end();
            _l.emplace_front(key, value);
            _s[key] = _l.begin();
        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.