C++, map + reference count


  • 0
    P

    Every time user gets or sets the value, key is being inserted into the queue. Total number of references is preserved to update the queue when inserting a new item (we keep removing items until there is one with ref count ==0). Total number of duplicates is combined with capacity to see if older items should be removed.

    class LRUCache{
        map<int, int> _map;
        queue<int> _items;
        map<int, int> _refCount;
        int _dups = 0;
        int _cap;
    public:
        LRUCache(int capacity): _cap(capacity){
            
        }
        
        int get(int key) {
            if(exist(key))
            {
                _items.push(key);
                addRef(key);
                
                return _map[key];
            }
            return -1;
        }
        
        void set(int key, int value) {
            _items.push(key);
            
            if(!exist(key))
            {
                _refCount[key]=0;
                
                if(_items.size()>_cap+_dups)
                {
                    bool removed = false;
                    while(!removed)
                    {
                        int oldKey = _items.front();
                        _items.pop();
                        if(_refCount[oldKey]==0)
                        {
                            _map.erase(oldKey);
                            removed = true;
                        }
                        else
                        {
                            removeRef(oldKey);
                        }
                    }
                }
            }
            else
            {
                addRef(key);
            }
            _map[key] = value;
        }
        void addRef(int key)
        {
            _dups++;
            _refCount[key]++;
        }
        void removeRef(int key)
        {
            _dups--;
            _refCount[key]--;
        }
        bool exist(int key)
        {
            return _map.find(key) != _map.end();
        }
    };

Log in to reply
 

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