Readable C++ implementation by unordered_map and list with detail comments


  • 0
    C

    The basic idea is to use list to store the sequence of the key, whenever a key is called, update it's sequence in the list.
    Use iterator is better than it's direct index, since iterator will automatically shift position when it's former elements removed.

    class LRUCache {
    public:
        LRUCache(int capacity) : _capacity(capacity) {}
        
        int get(int key) {
            auto it = _cache.find(key);
            if (it != _cache.end()){
                // if find the key, update it's sequence and return the key
                _sequence.erase(it->second.second); // it.second.second is the iterator in the list
                _sequence.push_front(key); 
                auto p = Pair(it->second.first, _sequence.begin()); // it.second.first is the value of the key
                _cache[key] = p;
                return it->second.first;
            }else{
                return -1;
            }
        }
        
        void put(int key, int value) {
            auto it = _cache.find(key);
            if (it != _cache.end()){
                // if find the key in the cache map
                _sequence.erase(it->second.second);
            }else{
                // if can't find the key, and capacity reached, remove the back element
                if (_sequence.size() >= _capacity){
                    _cache.erase(_sequence.back());
                    _sequence.pop_back();
                }
            }
            // update the key's new value
            _sequence.push_front(key);
            auto p = Pair(value, _sequence.begin());
            _cache[key] = p;
        }
        
    private:
        typedef list<int> List;
        typedef pair<int, List::iterator> Pair; // pair< value, iterator in list>
        typedef unordered_map<int, Pair> Map; // map< key, pair>
        
        Map _cache;     // cahce implemented by unordered map
        List _sequence; // a list to hold the key
        int _capacity;
    };
    

Log in to reply
 

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