Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class LRUCache {
- public:
- LRUCache(int c)
- : capacity{size_t(c)}
- {}
- int get(int key) const
- {
- auto it = cache.find(key);
- if (it == std::end(cache)) {
- return -1;
- }
- lru.splice(std::cend(lru), lru, *it->second.lru);
- return it->second.value;
- }
- void put(int key, int value)
- {
- auto it = cache.find(key);
- if (it == std::end(cache)) {
- it = cache.insert(it, {key, Value{value, nullptr}});
- if (cache.size() > capacity) {
- cache.erase(lru.front());
- lru.splice(std::cend(lru), lru, std::cbegin(lru));
- lru.back() = it;
- } else {
- lru.push_back(it);
- }
- it->second.lru = std::make_unique<Iterator>(std::prev(std::end(lru)));
- } else {
- it->second.value = value;
- lru.splice(std::cend(lru), lru, *it->second.lru);
- }
- }
- private:
- struct Iterator;
- struct Value
- {
- int value;
- std::unique_ptr<Iterator> lru;
- };
- using Cache = std::unordered_map<int /* key */, Value>;
- using LRU = std::list<typename Cache::iterator>;
- struct Iterator : LRU::iterator
- {
- Iterator(LRU::iterator it)
- : LRU::iterator{it}
- {}
- };
- const size_t capacity;
- Cache cache;
- mutable LRU lru;
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement