Mastering LRUCache: How to Build a High‑Performance Cache in C++

What Is LRUCache?

LRUCache (Least Recently Used Cache) is a common cache replacement policy that evicts the data that has not been accessed for the longest time when the cache is full. By discarding rarely accessed items, it improves hit rate and overall efficiency.

LRUCache appears in operating system memory management, browser resource caching, and many other scenarios. For example, an OS swaps out pages that have not been used recently, and a browser removes stale resources based on LRU to keep frequently visited pages fast.

Why Use LRUCache?

Caches sit between fast but small CPU caches and slower but larger main memory, dramatically speeding up data access. Compared with FIFO (first‑in‑first‑out) and LFU (least‑frequently‑used), LRU better captures recent usage patterns, avoiding the pitfalls of evicting frequently accessed items that entered the cache early.

Implementation Principle

The core of an LRUCache relies on two data structures: a hash table for O(1) key lookup and a doubly linked list to maintain access order. The hash table maps keys to nodes in the list; the list head holds the most recently used item, the tail holds the least recently used.

Core Data Structures

Hash Table : Stores key → node pairs, enabling constant‑time retrieval.

Doubly Linked List : Allows O(1) insertion and removal of nodes. When an item is accessed, its node is moved to the front; when eviction is needed, the node at the tail is removed.

Operation Flow

get(key) : Look up the key in the hash table. If missing, return -1. If found, detach the node from its current position and insert it at the front, then return its value.

/**
 * Retrieve the item for a given key, moving it to the tail of the queue.
 * Returns null if the value cannot be cached or created.
 */
public final V get(K key) {
    if (key == null) {
        throw new NullPointerException("key == null");
    }
    V mapValue;
    synchronized (this) {
        mapValue = map.get(key);
        if (mapValue != null) {
            hitCount++;
            return mapValue;
        }
        missCount++;
    }
    V createdValue = create(key);
    if (createdValue == null) {
        return null;
    }
    synchronized (this) {
        createCount++;
        mapValue = map.put(key, createdValue);
        if (mapValue != null) {
            map.put(key, mapValue);
        } else {
            size += safeSizeOf(key, createdValue);
        }
    }
    if (mapValue != null) {
        entryRemoved(false, key, createdValue, mapValue);
        return mapValue;
    } else {
        trimToSize(maxSize);
        return createdValue;
    }
}

put(key, value) : If the key exists, update its value and move the node to the front. If the key is new and the cache is full, evict the tail node, then insert the new node at the front.

void LRUCache::set(int key, int value) {
    if (m.find(key) == m.end()) {
        LRUCacheNode* node = new LRUCacheNode;
        if (count == capacity)
            removeLRUNode();
        node->key = key;
        node->value = value;
        m[key] = node;
        insertToFront(node);
        ++count;
    } else {
        LRUCacheNode* node = m[key];
        detachNode(node);
        node->value = value;
        insertToFront(node);
    }
}

Auxiliary Methods

removeLRUNode() : Removes the node just before the tail (the least recently used) and updates the hash table.

void LRUCache::removeLRUNode() {
    LRUCacheNode* node = tail->prev;
    detachNode(node);
    m.erase(node->key);
    --count;
}

detachNode(node) : Unlinks a node from the list.

void LRUCache::detachNode(LRUCacheNode* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

insertToFront(node) : Inserts a node right after the head, marking it as most recently used.

void LRUCache::insertToFront(LRUCacheNode* node) {
    node->prev = head;
    node->next = head->next;
    head->next = node;
    node->next->prev = node;
}

C++ Code Implementation

Define the node structure:

// Doubly linked list node
struct LRUCacheNode {
    int key;
    int value;
    LRUCacheNode* prev;
    LRUCacheNode* next;
    LRUCacheNode() : key(0), value(0), prev(nullptr), next(nullptr) {}
};

Define the cache class with members unordered_map<int, LRUCacheNode*> m, head, tail, capacity, and count. The constructor creates dummy head and tail nodes and links them.

class LRUCache {
private:
    unordered_map<int, LRUCacheNode*> m;
    LRUCacheNode* head;
    LRUCacheNode* tail;
    int capacity;
    int count;
public:
    LRUCache(int capacity);
    ~LRUCache();
    int get(int key);
    void set(int key, int value);
private:
    void removeLRUNode();
    void detachNode(LRUCacheNode* node);
    void insertToFront(LRUCacheNode* node);
};

LRUCache::LRUCache(int capacity) {
    this->capacity = capacity;
    this->count = 0;
    head = new LRUCacheNode;
    tail = new LRUCacheNode;
    head->next = tail;
    tail->prev = head;
}

Destructor releases all allocated nodes.

LRUCache::~LRUCache() {
    for (auto it : m) {
        delete it.second;
    }
    delete head;
    delete tail;
}

Testing and Optimization

Sample test program demonstrates insertion, retrieval, eviction, and update.

#include <iostream>
using namespace std;

int main() {
    LRUCache cache(3);
    cache.set(1, 100);
    cache.set(2, 200);
    cache.set(3, 300);
    cout << "Get 1: " << cache.get(1) << endl; // 100
    cout << "Get 2: " << cache.get(2) << endl; // 200
    cout << "Get 4: " << cache.get(4) << endl; // -1
    cache.set(4, 400); // evicts key 3
    cout << "Get 3: " << cache.get(3) << endl; // -1
    cache.set(1, 101);
    cout << "Get 1: " << cache.get(1) << endl; // 101
    return 0;
}

Performance Analysis

Both get and put run in O(1) time because they involve a constant‑time hash lookup and constant‑time list manipulation. Space complexity is O(n) for n cached items, due to the hash table and linked list.

Possible optimizations include using a memory pool to reduce frequent allocations for new nodes and tuning the unordered_map's load factor to minimize hash collisions.