date: 2020/02/07


利用基本的数据结构的算法,设计实现某些简单系统


基本概念

常见的内存页置换策略:

image.png


LRU可以用哈希表+双向链表实现,读/写时间复杂度均只有O(1)

image.png


146LRU缓存机制(中等)

https://leetcode-cn.com/problems/lru-cache

为了提高效率,这里有一些个小技巧

    1. 记录value的同时还存在在list里的iterator,方便操作
    2. 转移结点到头/尾部的时候直接使用splice,而不是先remove后push(remove需要遍历,push还得新建)
// 保存值的同时,还保存在list里的对应的迭代器
struct ValueIter {
    int val;
    list<int>::iterator iter;
    ValueIter(int v, list<int>::iterator i) : val(v), iter(i){}
};

class LRUCache {
private:
    unordered_map<int, ValueIter> data;  // 键值对的数据存储结构
    list<int> queue;    // 双向列表,记录访问次序(front进,back出)
    int capacity;
public:
    LRUCache(int capacity) : capacity(capacity) {}
    
    // 从map获取元素,同时把list中对应结点提到头部
    int get(int key) {
        unordered_map<int, ValueIter>::iterator it = data.find(key);
        if(it == data.end())
            return -1;
        // 把对应结点提到queue的头部位置(迭代器的值不会随之改变)
        queue.splice(queue.begin(), queue, it->second.iter);
        return it->second.val;
    }
    
    // 如果已在map里,把list中对应结点提到头部,然后更新value
    // 如果不在map里,且未达到容量,则直接插入
    // 如果不在map里,但达到容量,从list和map移除尾部元素,然后从front插入
    void put(int key, int value) {
        unordered_map<int, ValueIter>::iterator it = data.find(key);
        if(it != data.end()){
            queue.splice(queue.begin(), queue, it->second.iter);
            it->second.val = value;
        }else{
            if(data.size() == capacity){
                data.erase(queue.back());
                queue.pop_back();
            }
            queue.push_front(key);
            // 奇怪,这里只能insert来增加元素(为了便捷获取迭代器,list最好是front进back出
            data.insert(make_pair(key, ValueIter(value, queue.begin())));
            // data[key] = ValueIter(value, queue.begin());    // error!!
        }
    }
};