Least Recently Used (LRU) Cache Implementation – C++

This C++ program implements a Least Recently Used (LRU) cache. The LRU cache mechanism is used to maintain a set of items such that the least recently used items are discarded first when the cache reaches its capacity limit.

Program Code

#include <iostream>
#include <list>
#include <unordered_map>
#include <cassert>

class LRUCache {
private:
    int capacity;
    std::list<int> recent;
    std::unordered_map<int, std::pair<int, std::list<int>::iterator>> cache;

public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) return -1;
        recent.erase(it->second.second);
        recent.push_front(key);
        it->second.second = recent.begin();
        return it->second.first;
    }

    void put(int key, int value) {
        auto it = cache.find(key);
        if (it != cache.end()) {
            recent.erase(it->second.second);
        }
        recent.push_front(key);
        if (cache.size() == capacity) {
            int old_key = recent.back();
            recent.pop_back();
            cache.erase(old_key);
        }
        cache[key] = {value, recent.begin()};
    }

    void display() {
        for (int key : recent) {
            std::cout << key << ":" << cache[key].first << " ";
        }
        std::cout << std::endl;
    }
};

int main() {
    LRUCache cache(2); // capacity 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;
}

Function Documentation

Constructor: LRUCache(int capacity)

Initializes the cache with the specified capacity. The capacity must be a positive integer indicating the maximum number of items the cache can hold.

int get(int key)

Retrieves the value associated with the key if present in the cache. If the key is not found, it returns -1. This operation also marks the key as recently used.

void put(int key, int value)

Adds a key-value pair to the cache. If the cache is full, the least recently used item is removed. This operation also marks the key as recently used.

void display()

Prints the current content of the cache for debugging purposes, displaying the keys and their corresponding values in the order of their usage from most recently used to least recently used.

Example Usage

    // Create a cache with capacity for 2 items
    LRUCache cache(2);

    // Add some items to the cache
    cache.put(1, 1);
    cache.put(2, 2);

    // Retrieve items from the cache
    std::cout << cache.get(1) << std::endl;  // Outputs: 1
    cache.put(3, 3);  // Evicts key 2
    std::cout << cache.get(2) << std::endl;  // Outputs: -1 (not found)