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 theleast 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 namedSolution with one or morepublic functions which we are not allowed to rename.
2 Answers2
Usesize_t for sizes
Although the LeetCode question specifies that the constructor takes anint capacity, using anint to hold a size is not appropriate for two reasons:
intmight not be big enough to handle all possible sizes that fit into the available memory.intis signed, and now you have to deal with potentially negative numbers.
Also note that the standard library usessize_t for things like.size(), and the result of thesizeof operator is also asize_t. So it's best to internally store the capacity as asize_t. This will avoid compiler warnings about comparisons between signed and unsigned values.
Use types consistently
The one place you usesize_t is instd::list<size_t> lru. But here, the list is actually holding keys. Everywhere else you writeint key, so you should writestd::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 negativekeys are allowed, it only mentions only positivevalues are stored.
Make helper functionsprivate
Helper functions likeupdate() andclear() are not part of the public API as specified by the LeetCode problem. So make themprivate.
Use proper names
The functionclear(), 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 likepop_lru(), or perhaps justpop().
Also, the nameupdate() does not match the comment above it. I would remove the comment, and give a more descriptive name:make_most_recent().
Useless use ofconst
It does not make sense to have a function returnconst void. Just writevoid.
- \$\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
lruto the front. That's actually not O(1) withstd::deque, although I don't know why it theerase()would throw an exception. I'll update the answer.\$\endgroup\$G. Sliepen– G. Sliepen2020-06-22 15:15:12 +00:00CommentedJun 22, 2020 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 usingintfor keys, since that is part of the API given by the LeetCode question.\$\endgroup\$G. Sliepen– G. Sliepen2020-06-22 15:19:36 +00:00CommentedJun 22, 2020 at 15:19
You can use only oneunordered_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); */
- \$\begingroup\$Nice use of
splice(). I would avoid the single-letter variable names though.\$\endgroup\$G. Sliepen– G. Sliepen2021-01-24 11:32:28 +00:00CommentedJan 24, 2021 at 11:32 - \$\begingroup\$If you would like your code reviewed, pls post it as a new question. Your answer does not actually review OP's code which is basically the purpose of Code Review.\$\endgroup\$bjg– bjg2023-01-09 12:38:12 +00:00CommentedJan 9, 2023 at 12:38
You mustlog in to answer this question.
Explore related questions
See similar questions with these tags.