LeetCode 146: LRU Cache I

Question

I'm posting my C++ code for LeetCode's LRU Cache. If you have time and would like to review, please do so. Thank you!

Problem

• Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

• get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

• put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

• The cache is initialized with a positive capacity.

Follow up:

• Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);  
cache.put(2, 2);  
cache.get(1);       // returns 1  
cache.put(3, 3);    // evicts key 2  
cache.get(2);       // returns -1 (not found)  
cache.put(4, 4);    // evicts key 1  
cache.get(1);       // returns -1 (not found)  
cache.get(3);       // returns 3  
cache.get(4);       // returns 4

Accepted 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();
    }
};

Reference

On LeetCode, there is a class usually named Solution with one or more public functions which we are not allowed to rename.

• 146. LRU Cache - Problem

• 146. LRU Cache - Discuss

Answer 1

Use size_t for sizes

Although the LeetCode question specifies that the constructor takes an int capacity, using an int to hold a size is not appropriate for two reasons:

1. int might not be big enough to handle all possible sizes that fit into the available memory.
2. int is signed, and now you have to deal with potentially negative numbers.

Also note that the standard library uses size_t for things like .size(), and the result of the sizeof operator is also a size_t. So it's best to internally store the capacity as a size_t. This will avoid compiler warnings about comparisons between signed and unsigned values.

Use types consistently

The one place you use size_t is in std::list<size_t> lru. But here, the list is actually holding keys. Everywhere else you write int key, so you should write std::list<int> lru here, otherwise your cache might not work correctly when using negative numbers for keys. The LeetCode question does not say whether or not negative keys are allowed, it only mentions only positive values are stored.

Make helper functions private

Helper functions like update() and clear() are not part of the public API as specified by the LeetCode problem. So make them private.

Use proper names

The function clear(), despite its name and even the comment above it, does not erase the cache. Instead, it just removes the least recently used element. Make sure the name (and also the comment) reflects this. I would name it something like pop_lru(), or perhaps just pop().

Also, the name update() does not match the comment above it. I would remove the comment, and give a more descriptive name: make_most_recent().

Useless use of const

It does not make sense to have a function return const void. Just write void.

Answer 2

You can use only one unordered_map

My solution:

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