LRU和LFU

LRU(Least Recently Used)最新最少使用，缓存机制之一。

class LRUCache {
public:
    struct node {
        int val;
        node *prev;
        node *next;
        node(int value):val(value),prev(NULL),next(NULL){}
    };
    int cap;
    int cur;
    map<int, node*>cachetable;
    node *head;
    node *tail;
    void moveNodeIntoHead(int key)
    {
        node* tmp = head->next;
        if(tmp == cachetable[key])
            return;
        node* prevnode = cachetable[key]->prev;
        node* nextnode = cachetable[key]->next;
        prevnode->next = nextnode;
        nextnode->prev = prevnode;
        head->next = cachetable[key];
        cachetable[key]->prev = head;
        cachetable[key]->next = tmp;
        tmp->prev = cachetable[key];
        return;
    }
    void appendNodeIntoFront(int key, int value)
    {
        cachetable[key] = new node(value);
        node* tmp = head->next;
        head->next = cachetable[key];
        cachetable[key]->next = tmp;
        tmp->prev = cachetable[key];
        cachetable[key]->prev = head;
    }
    void removeNodeFromTail()
    {
        node* lastnode = tail->prev;
        node* prevnode = lastnode->prev;
        lastnode->val = INT_MAX;
        prevnode->next = tail;
        tail->prev = prevnode;
    }
    LRUCache(int capacity) {
        cachetable.clear();
        cap = capacity;
        cur = 0;
        head = new node(0);
        tail = new node(0);
        head->next = tail;
        tail->prev = head;
    }
    int get(int key) {
         if(cachetable.find(key) != cachetable.end() && cachetable[key]->val != INT_MAX)
         {
             moveNodeIntoHead(key); 
             return head->next->val;
         }
         return -1;
    }
    void put(int key, int value) {
        if(cachetable.find(key) != cachetable.end() && cachetable[key]->val != INT_MAX)
        {
            moveNodeIntoHead(key);
            head->next->val = value;
        }
        else
        {
            if (cur < cap)
            {
                appendNodeIntoFront(key, value);
                cur++;
            }
            else
            {
                removeNodeFromTail();
                appendNodeIntoFront(key, value);
            }
        }
    }
};

LFU(Least Frequently Used)最不经常使用，缓存算法之一。

class LFUCache {
    int cap;
    int size;
    int minFreq;
    unordered_map<int, pair<int, int>> m; //key to {value,freq};
    unordered_map<int, list<int>::iterator> mIter; //key to list iterator;
    unordered_map<int, list<int>>  fm;  //freq to key list;
public:
    LFUCache(int capacity) {
        cap=capacity;
        size=0;
    }

    int get(int key) {
        if(m.count(key)==0) return -1;

        fm[m[key].second].erase(mIter[key]);
        m[key].second++;
        fm[m[key].second].push_back(key);
        mIter[key]=--fm[m[key].second].end();

        if(fm[minFreq].size()==0 ) 
              minFreq++;

        return m[key].first;
    }

   void set(int key, int value) {
        if(cap<=0) return;

        int storedValue=get(key);
        if(storedValue!=-1)
        {
            m[key].first=value;
            return;
        }

        if(size>=cap )
        {
            m.erase( fm[minFreq].front() );
            mIter.erase( fm[minFreq].front() );
            fm[minFreq].pop_front();
            size--;
        }

        m[key]={value, 1};
        fm[1].push_back(key);
        mIter[key]=--fm[1].end();
        minFreq=1;
        size++;
    }
};