struct ListNodel {
    int key;
    ListNodel *before;
    ListNodel *next;
    ListNodel(int x) : key(x),before(NULL),next(NULL) {}
};
class LRUCache{
public: 
    map<int,int>mapkv;
    map&lt;int,ListNodel</em>&gt;mapkl;
    int capacityq;
    ListNodel * head,*tail;
    LRUCache(int capacity) {
        capacityq = capacity;
        mapkv.clear();
        mapkl.clear();
        head = NULL;
        tail = NULL;
    }</p>

<pre><code>int get(int key) {
    map&amp;lt;int,int&amp;gt;::iterator it = mapkv.find(key);
    if(it != mapkv.end()) {
        update(key);
        return it-&amp;gt;second;
    }
    else {
        return -1;
    }
}

void set(int key, int value) {
    map&amp;lt;int,int&amp;gt;::iterator it = mapkv.find(key);
    if(it != mapkv.end()) {
        it-&amp;gt;second = value;
        update(key);
    }
    else {
        if(mapkv.size() &amp;lt; capacityq) {
            insertKeyValue(key,value);  
        }
        else {
            ListNodel * tmp = head;
            head = head-&amp;gt;next;
            mapkl.erase(tmp-&amp;gt;key);
            mapkv.erase(tmp-&amp;gt;key);
            delete(tmp);
            insertKeyValue(key,value);
        }
    }
}
</code></pre>

<p>private:
    void insertKeyValue(int key,int value) {
        mapkv.insert(map&lt;int,int&gt;::value_type(key,value));
        if(head == NULL) {
            ListNodel * tmp = new ListNodel(key);
            mapkl.insert(map&lt;int,ListNodel<em>&gt;::value_type(key,tmp));
            head = tmp;
            tail = tmp;
            head-&gt;next = tail;
            tail-&gt;before = head;
            tail-&gt;next = NULL;
        }
        else {
            ListNodel * tmp = new ListNodel(key);
            mapkl.insert(map&lt;int,ListNodel</em>&gt;::value_type(key,tmp));
            tmp-&gt;before = tail;
            tail-&gt;next = tmp;
            tmp-&gt;next = NULL;
            tail = tmp;
        }
    }
    void update(int key) {
        map&lt;int,ListNodel*&gt;::iterator it = mapkl.find(key);
        ListNodel * tmp = it-&gt;second;
        if(tmp == head) {
            if(head-&gt;next != NULL) {
                head = head-&gt;next;
                tail-&gt;next = tmp;
                tmp-&gt;before = tail;
                tmp-&gt;next = NULL;
                tail = tmp;
            }
            //delete(tmp);
        } 
        else 
            if(tmp == tail){</p>

<pre><code>        }
        else {
            ListNodel * tmpb = tmp-&amp;gt;before;
            ListNodel * tmpn = tmp-&amp;gt;next;
            tmpb-&amp;gt;next = tmpn;
            tmpn-&amp;gt;before = tmpb;
            tmp-&amp;gt;before = tail;
            tail-&amp;gt;next = tmp;
            tmp-&amp;gt;next = NULL;
            tail = tmp;
        }
}
</code></pre>

<p>};