学步园

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) -
Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

set(key, value) - Set or insert the value if the key is not already
present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

      模拟近期最少使用算法。首先分析近期最少使用算法的特点：1.需要有一个时间链表，来存储并排序最近使用过的一些单元；2.对于新的单元，要能够查询时间链表中是否存在这个单元，如果存在，则操作这个单元并把这个单元放在时间链表的最前面，如果不存在，则插入这个单元到时间链表的最前面，此时，如果列表已经满了，需要删除队尾元素。

       所以，数据结构需要能实现一个时间链表来表示单元的先后顺序，同时需要能尽快的查询到这个链表中是否存在要操作的单元。

       查询操作，用map<key,value>结构，时间复杂度是O(1)，对于时间链表，我们可以通过构造链表来完成，于是map<key,value>结构应该为map<key,Node>，其中Node为结构体，存储value的同时实现一个链表结构。

        代码如下：

class LRUCache{
private:
    int maxCapacity;
    int curCapacity;
    int headKey;
    int tailKey;
    struct LRU{
        int value;
        int preKey;
        int nextKey;
        LRU(int value):value(value),preKey(-1),nextKey(-1){}
    };
    unordered_map<int, LRU*> lruMap;
public:
   LRUCache(int capacity) {
        maxCapacity=capacity;
        curCapacity=0;
    }
    
    int get(int key) {
        if(lruMap.find(key)==lruMap.end())return -1;
        else{
            if(maxCapacity==1)return lruMap[key]->value;
            else{
                if(headKey==key)return lruMap[key]->value;
                else if(tailKey==key){
                    tailKey=lruMap[key]->preKey;
                    lruMap[key]->nextKey=headKey;
                    lruMap[headKey]->preKey=key;
                    headKey=key;
                    return lruMap[key]->value;
                }else{
                    int preKey=lruMap[key]->preKey;
                    int nextKey=lruMap[key]->nextKey;
                    lruMap[preKey]->nextKey=nextKey;
                    lruMap[nextKey]->preKey=preKey;
                    lruMap[key]->nextKey=headKey;
                    lruMap[headKey]->preKey=key;
                    headKey=key;
                    return lruMap[key]->value;
                }
            }
        }
    }
    
    void set(int key, int value) {
        if(maxCapacity<=0)return;
        if(lruMap.find(key)==lruMap.end()){
            LRU* Node = new LRU(value);
            if(maxCapacity==1){
                lruMap.clear();
                lruMap.insert(make_pair(key,Node));
            }else{
                if(curCapacity==0){
                    lruMap.insert(make_pair(key,Node));
                    curCapacity++;
                    headKey=tailKey=key;
                }else if(curCapacity<maxCapacity){
                    lruMap.insert(make_pair(key,Node));
                    lruMap[key]->nextKey=headKey;
                    lruMap[headKey]->preKey=key;
                    headKey=key;
                    curCapacity++;
                }else{
                    tailKey=lruMap[tailKey]->preKey;
                    lruMap.erase(lruMap[tailKey]->nextKey);
                    lruMap.insert(make_pair(key,Node));
                    lruMap[key]->nextKey=headKey;
                    lruMap[headKey]->preKey=key;
                    headKey=key;
                }
            }
        }else{
            if(maxCapacity==1)lruMap[key]->value=value;
            else{
                if(headKey==key)lruMap[key]->value=value;
                else if(tailKey==key){
                    tailKey=lruMap[key]->preKey;
                    lruMap[key]->nextKey=headKey;
                    lruMap[headKey]->preKey=key;
                    headKey=key;
                    lruMap[key]->value=value;
                }else{
                    int preKey=lruMap[key]->preKey;
                    int nextKey=lruMap[key]->nextKey;
                    lruMap[preKey]->nextKey=nextKey;
                    lruMap[nextKey]->preKey=preKey;
                    lruMap[key]->nextKey=headKey;
                    lruMap[headKey]->preKey=key;
                    headKey=key;
                    lruMap[key]->value=value;
                }
            }
        }
    }
};