5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Ah, it seems the review was less impressive than you might have thought: I forgot that you need to move an entry in the middle of lru to the front. That's actually not O(1) with std::deque, although I don't know why it the erase() would throw an exception. I'll update the answer. \$\endgroup\$ – G. Sliepen Jun 22 at 15:15
  • 1
    \$\begingroup\$ Your changes look fine for the most part, but now you've changed the type of the key to size_t. You should keep using int for keys, since that is part of the API given by the LeetCode question. \$\endgroup\$ – G. Sliepen Jun 22 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.