#include <iostream>
#include <unordered_map>
#include <list>
class LRUCache {
private:
int capacity;
std::unordered_map<int, std::pair<int, std::list<int>::iterator>> cache;
std::list<int> lruList;
public:
LRUCache(int capacity) : capacity(capacity) {}
int get(int key) {
auto it = cache.find(key);
if (it != cache.end()) {
// Move the accessed key to the front of the list
lruList.erase(it->second.second);
lruList.push_front(key);
it->second.second = lruList.begin();
return it->second.first;
}
return -1;
}
void put(int key, int value) {
if (cache.size() == capacity) {
// Remove the least recently used element from both the list and the cache
int lruKey = lruList.back();
lruList.pop_back();
cache.erase(lruKey);
}
// Insert the new key-value pair into the cache and the front of the list
lruList.push_front(key);
cache[key] = {value, lruList.begin()};
}
};
int main() {
// Example usage of LRUCache
LRUCache cache(2); // Capacity is 2
cache.put(1, 1); // Cache: {1=1}
cache.put(2, 2); // Cache: {2=2, 1=1}
std::cout << cache.get(1) << std::endl; // Output: 1
cache.put(3, 3); // Cache: {3=3, 2=2}
std::cout << cache.get(2) << std::endl; // Output: -1 (not found)
cache.put(4, 4); // Cache: {4=4, 3=3}
std::cout << cache.get(1) << std::endl; // Output: -1 (not found)
std::cout << cache.get(3) << std::endl; // Output: 3
std::cout << cache.get(4) << std::endl; // Output: 4
return 0;
}