Last active
July 31, 2024 16:56
-
-
Save lsem/cc5d7f8fadacfb37ea458b95ef69ee1c to your computer and use it in GitHub Desktop.
lru_cache.cpp
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
| #include <list> | |
| #include <unordered_map> | |
| using namespace std; | |
| class LRUCache { | |
| private: | |
| struct keyval { | |
| int key, val; | |
| }; | |
| public: | |
| explicit LRUCache(int capacity) : m_capacity(capacity) {} | |
| int get(int key) const { | |
| if (auto it = m_map.find(key); it != m_map.end()) { | |
| touch(it->second); | |
| return it->second->val; | |
| } | |
| return -1; | |
| } | |
| void put(int key, int value) { | |
| if (auto it = m_map.find(key); it != m_map.end()) { | |
| it->second->val = value; | |
| touch(it->second); | |
| } else { | |
| if (m_map.size() == m_capacity) { | |
| m_map.erase(m_usages.front().key); | |
| m_usages.pop_front(); | |
| } | |
| m_usages.push_back({key, value}); | |
| m_map.insert({key, std::prev(m_usages.end())}); | |
| } | |
| } | |
| private: | |
| void touch(list<keyval>::iterator it) const { | |
| m_usages.splice(m_usages.end(), m_usages, it); | |
| } | |
| private: | |
| unordered_map<int, list<keyval>::iterator> m_map; | |
| int m_capacity{}; | |
| mutable list<keyval> m_usages; | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment