LRU缓存

分类：程序员面试金典题解标签：设计发布于：2020-05-20 ID：16.25

难度：Medium
题目链接：https://leetcode-cn.com/problems/lru-cache-lcci/

题目描述

设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。

它应该支持以下操作：获取数据 get 和写入数据 put 。

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

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

解法：

要想使用 key 快速获得 val，因此需要一个散列表。要想体现出 key 的新旧，需要一个列表。要想快速使用快速地把刚刚使用过的 key 放置到列表首位，需要使用链表。要想使用 key 快速取得链表中的元素，散列表中的 val 应该是链表的节点。实际的值存放在链表中。

class LRUCache {
public:
    LRUCache(int capacity):cap_(capacity) {
    }

    int get(int key) {
        auto it = mp_.find(key);
        if(it == mp_.end()){
            return -1;
        }
        list_.splice(list_.begin(), list_, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = mp_.find(key);
        if(it != mp_.end()){
            list_.splice(list_.begin(), list_, it->second);
            it->second->second = value;
        }else {
            if (mp_.size() == cap_) {
                mp_.erase(list_.rbegin()->first);
                list_.pop_back();
            }
            list_.emplace_front(key, value);
            mp_[key] = list_.begin();
        }
    }
private:
    using Node = pair<int, int>;
    list<Node> list_;
    unordered_map<int, list<Node>::iterator> mp_;
    int cap_;
};

下面是一个可用的 lru_cache 的实现。

#include <list>
#include <unordered_map>
#include <stdexcept>
#include <exception>

template <typename key_t, typename value_t>
class lru_cache{
private:
    struct Node{
        Node(key_t key, value_t value):key(key),value(value){}
        key_t key;
        value_t value;
    };
    using node_t = Node;
    using list_iterator = typename std::list<node_t>::iterator;
    using map_iterator = typename std::unordered_map<key_t, list_iterator>::iterator;

public:
    explicit lru_cache(size_t max_size): max_size_(max_size){
    }

    value_t get(const key_t& key){
        map_iterator it = map_.find(key);
        if(it == map_.end()){
            throw std::out_of_range("no suck key in cache");
        }
        list_.splice(list_.begin(), list_, it->second);
        return it->second->value;
    }

    void put(const key_t& key, const value_t& value){
        map_iterator it = map_.find(key);
        if(it != map_.end()){
            list_.erase(map_[key]);
        }
        list_.emplace_front(key, value);
        map_[key] = list_.begin();
        
        if(this->size() > max_size_){
            map_.erase(list_.back().key);
            list_.pop_back();
        }
    }

    size_t size() const{
        return map_.size();
    }

    bool contains(const key_t& key) const{
        return map_.find(key) != map_.end();
    }
private:
    size_t max_size_;
    std::list<node_t> list_;
    std::unordered_map<key_t, list_iterator> map_;
};

LeetCode 题解

积跬步，至千里。

LRU缓存

题目描述

解法：