C++ double list and unorder_map 77ms,how to improve?


  • 0
    P
        class LRUCache{
        struct node {
            int key;
            int value;
            node *prev, *next;
        };
    
    private:
        int index, max;
        unordered_map<int, node*> hp;
        node *head, *tail;
        vector<node> cache;
    
    public:
        LRUCache(int capacity) {
            cache.reserve(capacity);
            max = capacity;
            index = 0;
            head = tail = NULL;
        }
    
        void refresh(node *tmp) {
            if (tmp == tail) {
                tail = tmp->prev;
                tail->next = NULL;
            } else {
                tmp->prev->next = tmp->next;
                tmp->next->prev = tmp->prev;
            }
        
            tmp->next = head;
            head->prev = tmp;
            head = tmp;
        }
    
        void addnode(node *tmp) {
            if (head == NULL) {
                head = tail = tmp;
                tmp->next = NULL;
            } else {
                tmp->next = head;
                head->prev = tmp;
                head = tmp;
            }
        }
    
        int get(int key) {
            unordered_map<int, node*>::iterator iter = hp.find(key);
            if (iter == hp.end()) {
                return -1;
            } else {
                node *tmp = iter->second;
                if (head != tmp) {
                    refresh(tmp);
                }
    
                return tmp->value;
            }
        }
    
        void set(int key, int value) {
            unordered_map<int, node*>::iterator iter = hp.find(key);
            if (iter == hp.end()) {
                if (index < max) {
                    node *tmp = &cache[index];;
                    index++;
                    tmp->value = value;
                    tmp->key = key;
                    hp[key] = tmp;
                    addnode(tmp);
                } else {
                    node *tmp = tail;
                    hp.erase(tmp->key);
                    hp[key] = tmp;
                    tmp->key = key;
                    tmp->value = value;
                    if (head != tmp)
                        refresh(tmp);
                }
            } else {
                node *tmp = iter->second;
                if (head != tmp) {
                    refresh(tmp);
                }
    
                tmp->value = value;
            }
        }
    };

  • 0
    C

    I did pretty much same thing (with 65~85ms runtime). However I only used unordered_map<>. There is no need of vector<Node> cache.
    In set() operation

        void set(int key, int value) {
        if (key < 0)
            throw std::out_of_range("Set Key < 0");
        auto i = hp.find( key);
        if (i != hp.end()) {
            node *p = i->second;
            p->_val = value; // override current value
    

    There is no need to update the Key because it's the same. Try these and hopefully your time will improve.


Log in to reply
 

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