LeetCode: LRU Cache

思路分析

非常重要的一道面试题，要求给出一种数据结构来支持LRU(Least Recently Used)缓存策略，即：支持初始化缓存容量；支持key-value的插入与删除；当达到最大容量时，自动删除最不常用的缓存区。
一般而言，对于Cache的设计需要达到均摊O(1)的时间复杂度，想要做到这一点就只能用hashTable+双向链表来实现了。对于这道题目，我个人偏好用STL提供的一些“重量级”高级数据结构来写，可以达到最坏O(logn)的时间复杂度，但是代码实现出来有点Ugly。
大体思路是，定义结构体Node用于记录实际的key和value，使用一个map存放key到Node *的映射，同时定义一个set存放所有Node *，但是要以时间戳来排序。对于每一个get操作，直接利用map找到对应的Node *指针，更新其时间戳后重新加入set；对于每一个set操作，如果能够在map中找到key对应的value，就更新时间戳和value，否则就插入一个新的key-value键值。如果插入时发现容量已满，就要先移除一个set中时间戳最靠前的，这可以利用set自动维护的有序性来做到，然后再插入新的。实现时需要注意很多细节，此处就不再赘述了。

有必要再说一下hashMap的思路。由于LRU要移除长期未使用的内存块，因此我们完全可以用一个双向链表记录最近使用过的内存块，因为将链表中任何一个元素移动到开头，或者是移除链表尾部的元素，都只需要O(1)的复杂度，在C++中可以用splice函数来实现。接下来的问题就是，如何根据key来找到链表中对应的内存块呢？这就很简单了，放一个unordered_map上去，一下子就是均摊O(1)的复杂度。

代码

下面这份代码是较为粗糙的思路，每个操作最坏复杂度只能达到O(logn)。

struct Node
{
    int key;
    int val;
    int TimeStamp;
    Node(int k, int v, int t) {
        key = k;
        val = v;
        TimeStamp = t;
    }
};

class orderByTimeStamp: greater<Node *>
{
public:
    bool operator()( const Node *a, const Node *b ) const {
        return a->TimeStamp < b->TimeStamp;
    }
};

class LRUCache{
public:
    std::map<int, Node *> RB_Tree;
    std::set<Node *, orderByTimeStamp> Time;
    int TimeStamp;
    int capacity;
    LRUCache(int capacity) {
        this->capacity = capacity;
        this->TimeStamp = 0;
    }

    int get(int key) {
        std::map<int, Node *> :: iterator iter;
        std::set<Node *> :: iterator it;
        if ( ( iter = this->RB_Tree.find(key) ) != RB_Tree.end() ) {
            it = this->Time.find(iter->second);
            this->Time.erase(it);
            iter->second->TimeStamp = ++this->TimeStamp;
            this->Time.insert(iter->second);
            return iter->second->val;
        } else {
            return -1;
        }
    }

    void set(int key, int value) {
        std::map<int, Node *> :: iterator iter;
        std::set<Node *> :: iterator it;
        if ( ( iter = this->RB_Tree.find(key) ) != RB_Tree.end() ) {
            iter->second->val = value;
            it = this->Time.find(iter->second);
            this->Time.erase(it);
            iter->second->TimeStamp = ++this->TimeStamp;
            this->Time.insert(iter->second);
        } else {
            if ( this->RB_Tree.size() + 1 > this->capacity ) {
                int erase_key = (*Time.begin())->key;
                //delete *this->Time.begin();
                this->Time.erase(this->Time.begin());
                this->RB_Tree.erase(erase_key);
            }
            Node *new_node = new Node(key, value, ++this->TimeStamp);
            this->RB_Tree[key] = new_node;
            this->Time.insert(new_node);
        }
    }
};