Created
September 7, 2021 15:11
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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