LRU缓存 C++实现

LRU缓存

Least Recently Used (LRU) cache.
运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。

获取数据 get(key) – 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) – 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

为了让取的效率达到O(1),需要用hash。为了使得顺序存储,删除操作O(1),需要用链表。 所以需要用一个叫哈希链表的数据结构。

C++实现

键值对直接采用自带的pair实现。

list.front back 直接拿到 kv。
list.begin. back 拿到迭代器。
mp.erase(key) 根据key删除。

获取的时候,直接通过map,根据键,获取到链表的节点,并将该节点放到头部节点(先删后方),再返回该节点的value。

放入的时候。
如果有键,删除,将新的插入开头。

如果没有键,则看是否已经满了,
如果没有满,则直接放到开头。
如果满了,则删除链表尾部元素,接着放入开头。

class LRUCache {
private:
    int cap;
    list<pair<int,int>>cache;
    unordered_map<int,list<pair<int,int>>::iterator  >mp;
public:
    LRUCache(int capacity) {
        this->cap = capacity;
    }
    int get(int key){
        auto it = mp.find(key);
        if(it == mp.end()) return -1;
        pair<int,int> kv = *mp[key];
        cache.erase(mp[key]);
        cache.push_front(kv);
        mp[key] = cache.begin();
        return kv.second;
    }
    void put(int key,int value){
        auto it = mp.find(key);
        if(it != mp.end()){ // 有键
            cache.erase(mp[key]);
            cache.push_front(make_pair(key,value));
            mp[key] = cache.begin();// 更新hash
        }else{
            if(cache.size() == this->cap){// 满了
                auto last = cache.back();
                int lastKey = last.first;
                mp.erase(lastKey); // mp
                cache.pop_back();

            }
            cache.push_front(make_pair(key,value));
            mp[key] = cache.begin();
        }
    }
};

参考

labudadong的算法小抄。

点赞