Untitled
unknown
c_cpp
4 months ago
952 B
6
Indexable
struct Node { int key; int value; }; class LRUCache { public: LRUCache(int capacity) : capacity(capacity) {} int get(int key) { const auto it = keyToIterator.find(key); if (it == keyToIterator.cend()){ return -1; } const auto& listIt = it->second; cache.splice(cache.begin(), cache, listIt); return listIt->value; } void put(int key, int value) { if (const auto it = keyToIterator.find(key); it != keyToIterator.cend()) { const auto& listIt = it->second; cache.splice(cache.begin(), cache, listIt); listIt->value = value; return; } if (cache.size() == capacity) { const Node& lastNode = cache.back(); keyToIterator.erase(lastNode.key); cache.pop_back(); } cache.emplace_front(key, value); keyToIterator[key] = cache.begin(); } private: const int capacity; list<Node> cache; unordered_map<int, list<Node>::iterator> keyToIterator; };
Editor is loading...
Leave a Comment