Skip to content

Instantly share code, notes, and snippets.

@pidb
Created September 7, 2021 15:11
Show Gist options
  • Save pidb/b336fa33e0cbc7f6fe2ec152a80ce487 to your computer and use it in GitHub Desktop.
Save pidb/b336fa33e0cbc7f6fe2ec152a80ce487 to your computer and use it in GitHub Desktop.
Leetcode LRU Cache solution for hashmap + double-linked list, but it can continue to be optimized
struct LRUKV {
int key_;
int value_;
LRUKV(int key, int value) :key_(key), value_(value) {}
};
class LRUCache {
public:
LRUCache(int capacity)
:cache_size_(capacity),
caches_(std::list<LRUKV>()),
caches_table_(std::unordered_map<int, std::list<LRUKV>::iterator>()) {
}
int get(int key) {
auto cache_table_citer = caches_table_.find(key);
if (cache_table_citer != caches_table_.cend())
{
MoveToHead(cache_table_citer);
return cache_table_citer->second->value_;
}
return -1;
}
void put(int key, int value) {
auto cache_table_citer = caches_table_.find(key);
if (cache_table_citer != caches_table_.end()) {
if (cache_table_citer->second->value_ != value) {
cache_table_citer->second->value_ = value;
}
MoveToHead(cache_table_citer);
return;
}
if (caches_.size() < cache_size_)
{
caches_.emplace_front(LRUKV(key, value));
caches_table_[key] = caches_.begin();
}
else
{
caches_table_.erase(caches_.back().key_);
caches_.pop_back();
caches_.emplace_front(LRUKV(key, value));
caches_table_[key] = caches_.begin();
}
}
private:
void MoveToHead(const std::unordered_map<int, std::list<LRUKV>::iterator>::const_iterator& citer) {
caches_.splice(caches_.begin(), caches_, citer->second);
caches_table_[caches_.front().key_] = citer->second;
caches_table_[citer->first] = caches_.begin();
}
size_t cache_size_;
std::list<LRUKV> caches_;
std::unordered_map<int, std::list<LRUKV>::iterator> caches_table_;
};
/**
* 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);
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment