LRU：least recently used

• 最近最少使用算法，即选择最近最久未使用的页面予以淘汰

实现：

• 使用hash_map+双向链表，实现复杂度O(1)

应用场景：

• 底层的内存管理，页面置换算法
• 一般的缓存服务，memcache/redis等
• 部分业务场景

缺点：

• 向前看，但过去与未来之间并无必然的联系
• 偶然性、周期性的批量操作会导致命中率急剧下降，缓存污染的情况比较严重

代码示例：

#include <unordered_map>

template <typename TypeK, typename TypeV>
struct CacheNode{
    TypeK key;
    TypeV value;
    CacheNode *pre, *next;
    CacheNode(TypeK k, TypeV v) : key(k),value(v),pre(NULL),next(NULL){};
};

template <typename TypeK, typename TypeV>
class LruCache{
public:
    LruCache(int capacity = 100):size(capacity),head(NULL),tail(NULL){}
    TypeV *get(TypeK key){
       typename LRU_MAP::iterator it = mapCache.find(key);
        if (it == mapCache.end()){
            return NULL;
        } else {
            TemplateNode *node = it->second;
            remove(node);
            setHead(node);
            return &node->value;
        }
    }
    void set(TypeK key, TypeV value){
        typename LRU_MAP::iterator it = mapCache.find(key);
        if (it != mapCache.end()){
            TemplateNode *node = it->second;
            remove(node);
            setHead(node);
        } else {
            if (mapCache.size()>=size){
                typename LRU_MAP::iterator it_tail = mapCache.find(tail->key);
                TemplateNode *old = tail;
                remove(tail);
                mapCache.erase(it_tail);
                delete old;
            }
            TemplateNode *newNode = new TemplateNode(key, value);
            setHead(newNode);
            mapCache[key] = newNode;
        }
    }
private:
    int size;
    typedef CacheNode<TypeK, TypeV> TemplateNode;
    typedef unordered_map<TypeK, TemplateNode*> LRU_MAP;
    
    TemplateNode *head, *tail;
    LRU_MAP mapCache;
private:
    void remove(TemplateNode *node){
        if (node->pre){
            node->pre->next = node->next;
        } else {
            head = node->next;
        }
        if (node->next){
            node->next->pre = node->pre;
        } else {
            tail = node->pre;
        }
    }
    void setHead(TemplateNode *node){
        node->next = head;
        node->pre  = NULL;
        if (head){
            head->pre = node;
        }
        head = node;
        if (!tail){
            tail = head;
        }
    }
};