Skip to content

Instantly share code, notes, and snippets.

@SF-Zhou SF-Zhou/lru.cc

Created Dec 6, 2019
Embed
What would you like to do?
C++11 LRU Cache
#include <list>
#include <unordered_map>
class LRUCache {
public:
LRUCache(int capacity) : capacity_(capacity) {}
int get(int key) {
auto it = used_.find(key);
if (it == used_.end()) {
return -1;
}
least_.splice(least_.begin(), least_, it->second);
return it->second->second;
}
void put(int key, int value) {
auto it = used_.find(key);
if (it != used_.end()) {
least_.splice(least_.begin(), least_, it->second);
it->second->second = value;
} else {
least_.push_front(std::make_pair(key, value));
used_[key] = least_.begin();
if (used_.size() > capacity_) {
used_.erase(least_.back().first);
least_.pop_back();
}
}
}
private:
int capacity_;
std::list<std::pair<int, int>> least_;
std::unordered_map<int, decltype(least_)::iterator> used_;
};
int main() {
LRUCache cache(2);
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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.