LRUCache - C++

LRUCache是一种常用的缓存替换算法，其原理是根据使用率淘汰数据，一般会实现为一个队列，如果一个cache命中，则将这个数据移动到队列的头部，这样，不经常使用的cache就会逐渐移向队列尾部，当cache容量满时，就从队列尾部取出一个数据丢掉。总的来说，涉及到了数据在头部插入、尾部移除、随机取出数据这样几个主要的操作，所以双向链表是一个不错的选择。但是我们再考虑到这样一个问题：如果直接使用LinkedList，从Cache中取数据时每次都要遍历队列，无谓的消耗了大量时间，所以我们自然而然的加上了HashMap，HashMap中存储了指向LinkedList的指针，这样就可以保证在O(1)的访问复杂度。一个具体的实现如下(C++)：

template<typename Key, typename Value>
class LRUCache {
public:
    // err为当cache查找失败时返回的值
    LRUCache(int capacity, Value err) {
        err_ = err;
        capacity_ = capacity;
        head_.next = &tail_;
        tail_.prev = &head_;
    }

    Value get(Key key) {
        auto it = vmap_.find(key);
        if(it == vmap_.end()) {
            return err_;
        } else {
            Cache *c = it->second;
            move_cache_to_head(c);
            return c->value;
        }
    }

    void set(Key key, Value value) {
        auto it = vmap_.find(key);
        if(it != vmap_.end()) {
            Cache *c = it->second;
            c->value = value;
            move_cache_to_head(c);
        } else {
            if(capacity_ == vmap_.size()) {
                Cache *c = remove_last_cache();
                vmap_.erase(c->key);
                c->key = key;
                c->value = value;
                cache_push(c);
                vmap_[key] = c;
            } else {
                Cache *c = new Cache(key, value);
                cache_push(c);
                vmap_[key] = c;
            }
        }
    }

private:
    struct Cache {
        Cache() = default;
        Cache(Key key, Value value) : key(key), value(value) {}
        Key key;
        Value value;
        Cache *prev;
        Cache *next;
    };

    void cache_push(Cache *c) {
        c->next = head_.next;
        head_.next = c;
        c->next->prev = c;
        c->prev = &head_;
    }

    void cache_push(Key key, Value value) {
        Cache *c = new Cache(key, value);
        cache_push(c);
    }

    void move_cache_to_head(Cache *c) {
        c->prev->next = c->next;
        c->next->prev = c->prev;
        cache_push(c);
    }

    Cache *remove_last_cache() {
        Cache *c = tail_.prev;
        tail_.prev = c->prev;
        c->prev->next = &tail_;
        return c;
    }

private:
    Cache head_;
    Cache tail_;
    Value err_;
    int capacity_;
    unordered_map<Key, Cache *> vmap_;
};

其中capacity为Cache容量，err为查找失败时默认的返回值，比如cache的数据类型为int，容量为10，查找失败时返回-1，则LRUCache的定义如下：

LRUCache<int, int> lru(10, -1);