My accepted C++ solution, in 348ms


  • 0
    T

    This solution uses the "map", a balanced binary search tree.
    We could change the map to unordered_map, that is the hash table in STL, and will save 32ms.

    Questions:

    1. Do we have a better way to move an element to the end of a list?
    2. Could anyone provide a free/open source profiler for C++?

    Thanks!

    #include <map>
    #include <list>
    #include <iostream>
    
    using namespace std;
    
    struct Node {
        int key, value;
        Node(int k, int v) : key(k), value(v) {};
    };
    
    class LRUCache {
        private:
            size_t mCapacity;
            size_t mSize;
            map<int, list<Node>::iterator> mKey;
            list<Node> mValue;
            typedef list<Node>::iterator value_iterator;
    
            // move the element i, to the end
            value_iterator moveBack(value_iterator i) {
                Node node = *i;
                mValue.erase(i);
                return mValue.insert(mValue.end(), node);
            }
        public:
            LRUCache(size_t capacity) : mCapacity(capacity), mSize(0) {
            }
    
            int get(int key)
            {
                map<int, list<Node>::iterator>::iterator iter = mKey.find(key);
                if (iter == mKey.end()) {
                    // cout << "No such node: " << key << endl;
                    return -1;
                }
                iter->second = moveBack(iter->second);
                // cout << "Got " << iter->second->value << " for key: " << key << endl;
                return iter->second->value;
            }
    
            void set(int key, int value)
            {
                list<Node>::iterator iNode;
                map<int, value_iterator>::iterator j = mKey.find(key);
    
                if (j != mKey.end()) {
                    // cout << "Already existed, key: " << key << endl;
                    iNode = moveBack(j->second);
                    // cout << "update from " << iNode->value << " to " << value << endl;
                    iNode->value = value;
                    j->second = iNode;
    
                    return;
                }
    
                if (mCapacity <= mSize) {
                    // The least used node is at the first place.
                    iNode = mValue.begin();
                    // cout << "Exceeded, the beginning node (" << iNode->key << ", " << iNode->value << ")." << endl;
    
                    j = mKey.find(iNode->key);
                    iNode = moveBack(iNode);
                    iNode->key = key;
                    iNode->value = value;
    
                    mKey.erase(j);
                    mKey.insert(pair<int, value_iterator>(key, iNode));
                    // cout << "Replace the least used node with (" << key << ", " << value << ")" << endl;
                    return;
                }
    
                // Add new node as the capacity is not exceeded.
                Node node(key, value);
                iNode = mValue.insert(mValue.end(), node);
                mKey.insert(pair<int, value_iterator>(key, iNode));
                // cout << "Added a brand new node: (" << key << ", " << value << ")" << endl;
                mSize++;
            }
    };

  • -1
    Z

    1.Check std::list::splice out.
    2.Boost.Bimap also is a great implement to do this.

    Here is my code. 320 ms, std::unordered_map + std::list approach.

    class LRUCache{
    

    public:
    LRUCache(int capacity):capacity_(capacity) {}

    int get(int key) {
    	auto i = cache_.find(key);
    
    	if(i != cache_.end()){
    		//find the key
    		//move it to the head of linked list
    		LRU.splice(LRU.begin(),LRU,i->second);
    		return i->second->second;
    	}else{
    		return -1;
    	}
    }
    
    void set(int key, int value) {
    	//already exist
    	if(cache_.find(key) != cache_.end()){
    	    //update value
    		cache_[key]->second = value;
    		//move to head
    		LRU.splice(LRU.begin(),LRU,cache_[key]);
    		return;
    	}
    
    	if(cache_.size() == capacity_){
    		//cache is full
    		//delete key,pointer in hash table
    		int tail_key = LRU.back().first;
    		cache_.erase(tail_key);
    		//delete tail node in linked list
    		LRU.pop_back();
    	}
    	//add new node at the head of linked list
    	LRU.push_front(std::make_pair(key,value));
    	//insert new node into hash map
    	cache_[key] = LRU.begin();
    }
    

    private:
    std::unordered_map<int, std::list<std::pair<int,int>>::iterator> cache_;
    std::list<std::pair<int,int>> LRU;
    int capacity_;
    };


  • 1
    L

    This take 264ms. I just utilize list and unordered_map, which is faster than map. Logic basically the same.

    typedef list<int> List;
    typedef list<int>::iterator Iterator;
    typedef pair<int,Iterator> Pair;
    typedef unordered_map<int, Pair> Map;
    
    class LRUCache{
    public:
        Map map;
        List llist;
        int MAXCAP;
        LRUCache(int capacity):MAXCAP(capacity) {
        }
        
        int get(int key) {
            auto it = map.find(key);
            if(it==map.end()) return -1;
            auto &kv = it->second;
            llist.erase(kv.second);
            llist.push_front(key);
            kv.second=llist.begin();
            return kv.first;
        }
        
        void set(int key, int value) {
            auto it = map.find(key);
            if(it==map.end()){
                if(map.size()>=MAXCAP){
                    map.erase(llist.back());
                    llist.pop_back();
                }
                llist.push_front(key);
                map.insert(make_pair(key,Pair(value,llist.begin())));
            }
            else{
                auto &kv = it->second;
                llist.erase(kv.second);
                llist.push_front(key);
                kv.second=llist.begin();
                kv.first=value;
            }
        }
    };

  • 0
    L

    I think the key different is that in my code, value is stored in map while key is stored in both map and list. It takes more space but is faster.


  • 0
    W

    where is your i in get()????


Log in to reply
 

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