LRU Cache C++三种解法-菜鸟笔记

先说一下题意，总共有三个操作：

LRUCache obj = new LRUCache(capacity);
obj.put(1, 1);
obj.get(1);

第一个是创建大小为capacity的cache
第二个是在key=1的位置放入value=1的值
第三个是取出key=1位置的value
需要清楚的几点：若重复在某个key的位置放入值，则原值会被新值覆盖，例如现在又执行obj.put(1, 2)，则现在位置1存放的是2，而不是原先的1
此外，题目也写了是LRU，即最近最少使用，这是操作系统中非常常见的一道题，假设内存只能容纳3个页大小，按照 7 0 1 2 0 3 0 4 的次序访问页，则访问顺序为：

即一旦内存被放满，则首先淘汰距当前最远时间的页中的值
那么回到这道题本身，根据这个流程的理解，最容易想到的一个方法就是

用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。
每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。

这种方法实现很方便，就不写了，很明显，这样做每次都要访问内存页中的所有数据，复杂度太高，这道题如果用这种方法，也将超时，这时候就想到，这个<key, value>的对应形式不就是C++中map的方法，而同时，也可以用一个向量来保存每次读入的key，对于新key则置顶，实现如下：

class LRUCache {
public:
    LRUCache(int capacity) {
        cap = capacity, cur = 0; //cur表示已存放的容量
    }

    int get(int key) {
        vector<int>::iterator it = find(v.begin(), v.end(), key); //在vector中找对应的key
        if(it == v.end()) return -1; 
        v.erase(it); 
        v.emplace_back(key); //每次get都将该key置顶
        return m[key];
    }

    void put(int key, int value) {
        if(m[key])  //如果原先key中就有值，则覆盖原值，同时置顶该key
        {
            m[key] = value;
            vector<int>::iterator it = find(v.begin(), v.end(), key);
            v.erase(it);
            v.emplace_back(key);
            return;
        }

        if(cur == cap)
        {
            int p = v.front();
            m[p] = 0;
            v.erase(v.begin());
            m[key] = value;
            v.emplace_back(key);
        }
        else
        {
            cur++;
            v.emplace_back(key);
            m[key] = value;
        }
    }
    int cap, cur;
    vector<int> v;
    map<int, int> m;
};

然后想，这段代码能否再精简呢？可以看到

v.erase(v.begin());
v.emplace_back(key);

这一段重复了很多次，完全可以用一个函数代替，且vector在头尾的操作很不方便，C++有已实现的list双向链表。此外，既然每次都要找key的位置，为什么不把这个位置也用一个map存放起来呢？
于是有了下面这段代码：

class LRUCache {
public:
    LRUCache(int capacity) {
        cap = capacity, cur = 0;
    }

    int get(int key) {
        if (cache.find(key) == cache.end())
            return -1;
        set(key);
        return cache[key];
    }

    void put(int key, int value) {
        set(key);
        cache[key] = value;
    }

private:
    int cap, cur;
    list<int> recent;
    unordered_map<int, int> cache;
    unordered_map<int, list<int>::iterator> pos;
    void set(int key)
    {
        if (cache.find(key) != cache.end())
        {
            list<int>::iterator it = pos[key];
            recent.erase(it);
            pos.erase(key);
        }
        else
        {
            if (cur >= cap)
            {
                int last = recent.back();
                recent.pop_back();
                cache.erase(last);
                pos.erase(last);
            }
            else
            {
                cur++;
            }
        }
        recent.emplace_front(key);
        pos[key] = recent.begin();
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

set函数是将key置顶，由于无论是put还是get，都会使得“最近使用”的值更新，因此单独用一个函数封装
最后结果如下，当然这还不算最elegant最高效的，还有待学习~

面试题

LRU Cache C++三种解法

笔记导航