Implement LRU cache in cpp
- User
Implement LRU cache in cpp
- Assistant
An LRU (Least Recently Used) cache is a cache data structure that removes the least recently used items first when the cache reaches its maximum capacity. Here's one way to implement an LRU cache in C++ using STL containers (unordered_map and list):
#include <iostream> #include <list> #include <unordered_map> class LRUCache { public: LRUCache(int capacity): _capacity(capacity) {} int get(int key) { // If key is not in the cache, return -1 if (_cache.find(key) == _cache.end()) { return -1; } // Move the accessed element to the front of the list _lru.splice(_lru.begin(), _lru, _cache[key].second); // Return the value of the key return _cache[key].first; } void put(int key, int value) { // If key is already in the cache, update the value and move to the front if (_cache.find(key) != _cache.end()) { _cache[key].first = value; _lru.splice(_lru.begin(), _lru, _cache[key].second); return; } // If the cache is full, remove the least recently used element if (_cache.size() == _capacity) { int lruKey = _lru.back(); _lru.pop_back(); _cache.erase(lruKey); } // Add the new key-value pair to the cache and the list _lru.push_front(key); _cache[key] = {value, _lru.begin()}; } private: int _capacity; std::list<int> _lru; std::unordered_map<int, std::pair<int, std::list<int>::iterator>> _cache; }; int main() { LRUCache cache(2); cache.put(1, 1); cache.put(2, 2); std::cout << cache.get(1) << std::endl; // returns 1 cache.put(3, 3); // evicts key 2 std::cout << cache.get(2) << std::endl; // returns -1 (not found) cache.put(4, 4); // evicts key 1 std::cout << cache.get(1) << std::endl; // returns -1 (not found) std::cout << cache.get(3) << std::endl; // returns 3 std::cout << cache.get(4) << std::endl; // returns 4 return 0; }This implementation uses an unordered_map (_cache) to store key-value pairs and their iterators to the corresponding elements in a list (_lru). The list is used to track the order of usage, with the front being the most recently used and the back being the least recently used element. When the cache reaches its capacity, the least recently used element is removed from both the unordered_map and the list.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.