LRU Caching Algorithm
Description
LRU (Least Recently Used) caching algorithm is used to maintain a cache of limited size. It discards the least recently used items first when the cache reaches its limit. This algorithm is commonly used in operating systems and web browsers to manage memory efficiently.
C++ Code
#include <iostream>
#include <unordered_map>
#include <list>
using namespace std;
class LRUCache {
private:
int capacity;
unordered_map<int, list<pair<int, int>>::iterator> cacheMap;
list<pair<int, int>> cacheList;
public:
LRUCache(int capacity) {
this->capacity = capacity;
}
int get(int key) {
if (cacheMap.find(key) == cacheMap.end()) {
return -1;
} else {
// Move accessed item to the front of the list
auto it = cacheMap[key];
int value = it->second;
cacheList.erase(it);
cacheList.push_front(make_pair(key, value));
cacheMap[key] = cacheList.begin();
return value;
}
}
void put(int key, int value) {
if (cacheMap.find(key) != cacheMap.end()) {
// Update the value and move it to the front
auto it = cacheMap[key];
cacheList.erase(it);
cacheList.push_front(make_pair(key, value));
cacheMap[key] = cacheList.begin();
} else {
// Insert new (key, value) pair
if (cacheList.size() >= capacity) {
// Evict the least recently used item
int lastKey = cacheList.back().first;
cacheList.pop_back();
cacheMap.erase(lastKey);
}
cacheList.push_front(make_pair(key, value));
cacheMap[key] = cacheList.begin();
}
}
};
int main() {
LRUCache cache(2);
cache.put(1, 1);
cache.put(2, 2);
cout << cache.get(1) << endl;
cache.put(3, 3);
cout << cache.get(2) << endl;
cache.put(4, 4);
cout << cache.get(1) << endl;
cout << cache.get(3) << endl;
cout << cache.get(4) << endl;
return 0;
}
Time and Space Complexity
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Get(key) | O(1) | O(1) |
| Put(key, value) | O(1) | O(1) |
Where:
- n: Number of items in the cache.
- m: Capacity of the cache.