LeetCode 146: LRU Cache I

Question

我正在为LeetCode的LRU缓存发布我的C++代码。如果您有时间和想复习，请这样做。谢谢!

问题

• 设计并实现了一种用于最小最近使用(LRU)缓存的数据结构。它应该支持以下操作: get和put。
• 获取(键)-如果键存在于缓存中，则获取键的值(将始终为正)，否则返回-1。
• 放置(键，值)-设置或插入的值，如果键还没有出现。当缓存达到其容量时，它应该在插入新项之前使最近使用最少的项失效。
• 缓存是以正容量初始化的。

后续行动：

• 你能用O(1)时间复杂度做这两种操作吗？

示例: LRUCache cache =新LRUCache( 2 /*容量*/ )；cache.put(1，1)；cache.put(2，2)；cache.get(1)；//返回1 cache.put(3，3)；//逐出键2 cache.get(2)；// returns 1(未找到) cache.put(4，4)；//逐出键1 cache.get(1)；//返回-1 (未找到) cache.get(3)；//返回3 cache.get(4)；//返回4

接受C++

#include <list>
#include <unordered_map>


class LRUCache {
public:
    const int size;
    std::list<size_t> lru;
    std::unordered_map<int, std::list<size_t>::iterator> cache;
    std::unordered_map<int, int> key_val_map;

    LRUCache(const int capacity) : size(capacity) {}

    // Getter constant memory
    int get(int key) {
        if (key_val_map.count(key) == 0) {
            return -1;
        }

        update(key);
        return key_val_map[key];
    }

    // Setter constant memory
    const void put(int key, int value) {
        if (key_val_map.size() == size && key_val_map.count(key) == 0) {
            clear();
        }

        update(key);

        key_val_map[key] = value;
    }

    // Add a new key
    const void update(int key) {
        if (key_val_map.count(key)) {
            lru.erase(cache[key]);
        }

        lru.push_front(key);
        cache[key] = lru.begin();
    }


    // Erase cache
    const void clear() {
        key_val_map.erase(lru.back());
        cache.erase(lru.back());
        lru.pop_back();
    }
};

参考

在LeetCode上，通常有一个名为Solution的类，它有一个或多个public函数，我们不允许重命名这些函数。

• 146.LRU缓存-问题
• 146.LRU缓存-讨论

Answer 1

使用size_t表示

大小

虽然LeetCode问题指定构造函数接受int capacity，但是使用int保持大小是不合适的，原因有二：

1. int可能不够大，无法处理适合可用内存的所有可能大小。
2. int已经签署，现在您必须处理潜在的负数。

还请注意，标准库将size_t用于像.size()这样的东西，sizeof运算符的结果也是size_t。所以最好在内部存储作为size_t的容量。这将避免编译器对有符号值和无符号值之间的比较发出警告。

一致使用类型

您使用size_t的唯一地方是std::list<size_t> lru。但在这里，名单上其实有钥匙。在任何地方都可以编写int key，所以您应该在这里编写std::list<int> lru，否则当对键使用负数时，缓存可能无法正常工作。LeetCode问题没有说明是否允许使用负键，它只提到了存储的正值。

使辅助函数private

像update()和clear()这样的助手函数不是由LeetCode问题指定的公共API的一部分。所以让他们private。

使用专有名称

函数clear()，尽管它的名称，甚至上面的注释，都不会删除缓存。相反，它只是删除了最近使用最少的元素。确保名称(以及注释)反映了这一点。我可以把它命名为pop_lru()，或者仅仅是pop()。

而且，名称update()与上面的注释不匹配。我会删除这个注释，并给出一个描述性更强的名称：make_most_recent()。

无用使用const

函数返回const void是没有意义的。写void就行了。

Answer 2

您只能使用一个unordered_map。

我的解决方案：

class LRUCache {
public:
    LRUCache(int capacity) {
        size_ = capacity;
    }
    
    int get(int key) {
        auto it = m_.find(key);
        if (it == m_.end()) {
            return -1;
        }
        l_.splice(begin(l_), l_, it->second);
        return it->second->second;
    }
    
    void put(int key, int value) {
        auto it = m_.find(key);
        if (it != m_.end()) {
            l_.erase(it->second);
        }
        l_.push_front({key, value});
        m_[key] = l_.begin();
        if (m_.size() > size_) {
            int key_delete = l_.rbegin()->first;
            m_.erase(key_delete);
            l_.pop_back();
        }
        
    }
private:
    int size_;
    list<pair<int, int>> l_; // key, val
    unordered_map<int, list<pair<int, int>>::iterator> m_;
};

/**
 * 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);
 */