C++ Template solution, do not store key in the List


  • 0
    J

    store iterator in the list in case the key is large

    template<typename KeyType, typename ValType>
    struct item_t {
        typename unordered_map<KeyType, typename list<item_t<KeyType, ValType> >::iterator>::iterator key;
        ValType val;
        item_t(typename unordered_map<KeyType, typename list<item_t<KeyType, ValType> >::iterator>::iterator k, ValType v) :key(k), val(v){}
    };
    
    
    template<class KeyType, class ValType>
    class MyLRUCache {
    public:
        MyLRUCache(int capacity) {
            capacity_ = capacity;
        }
        
        bool get(int key, ValType& val) {
            auto iter = map_.find(key);
            if (iter == map_.end()) {
                return false;
            } else {
                auto list_iter = iter->second;
                list_.splice(list_.begin(), list_, list_iter);
                val = list_.front().val;
    			return true;
            }
        }
        
        void put(KeyType key, ValType value) {
            auto iter = map_.find(key);
            if (iter != map_.end()) {
                auto list_iter = iter->second;
                list_.splice(list_.begin(), list_, list_iter);
                list_.front().val = value;
            } else {
                if (list_.size() >= capacity_) {
                    map_.erase(list_.back().key);
                    list_.pop_back();
                } 
                list_.push_front(item_t<KeyType, ValType>(map_.end(), value));            
                list_.front().key = map_.insert(make_pair(key, list_.begin())).first;
            }
        }
        unordered_map<KeyType, typename list<item_t<KeyType, ValType> >::iterator> map_;
        int capacity_;
        list<item_t<KeyType, ValType> > list_;
    };
    
    
    
    class LRUCache {
    public:
        LRUCache(int capacity) : cache_(capacity) {
    
        }
        
        int get(int key) {
            int val;
            if (cache_.get(key, val)) {
                return val;
            } else {
                return -1;
            }
        }
        
        void put(int key, int value) {
            cache_.put(key, value);
        }
        MyLRUCache<int, int> cache_;
    };
    

Log in to reply
 

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