Simple LRU Cache Implementation

Oct 13, 2025 by leolavanderia.com.br 107 views

Introduction

In this article, we will explore a simple implementation of a Least Recently Used (LRU) cache in C++20. The LRU cache is a data structure that stores a limited number of items, and when the cache is full, it discards the least recently used items to make room for new ones. This implementation is a basic example of a cache and can be used as a starting point for more complex cache implementations.

LRU Cache Overview

The LRU cache is a type of cache that uses a combination of a hash table and a doubly linked list to store and manage cache items. The hash table is used to store the cache items with their keys, and the doubly linked list is used to keep track of the order in which the items were accessed.

Simple LRU Cache Implementation

Here is a simple implementation of an LRU cache class template in C++20:

#pragma once
#include <cassert>
#include <optional>
#include <unordered_map>
#include <memory>
template <typename Key, typename Value, size_t Capacity>
class LRUCache 
public
// Constructor
LRUCache() : capacity_(Capacity) {
// Destructor
~LRUCache() = default;

// Copy constructor and assignment operator are deleted
LRUCache(const LRUCache&amp;) = delete;
LRUCache&amp; operator=(const LRUCache&amp;) = delete;

// Move constructor and assignment operator are deleted
LRUCache(LRUCache&amp;&amp;) = delete;
LRUCache&amp; operator=(LRUCache&amp;&amp;) = delete;

// Get a value from the cache
std::optional&lt;Value&gt; get(const Key&amp; key) {
    auto it = cache_.find(key);
    if (it != cache_.end()) {
        // Move the accessed item to the front of the list
        list_.splice(list_.begin(), list_, it-&gt;second);
        return it-&gt;second-&gt;second;
    }
    return std::nullopt;
}

// Set a value in the cache
void set(const Key&amp; key, const Value&amp; value) {
    // Check if the key already exists in the cache
    auto it = cache_.find(key);
    if (it != cache_.end()) {
        // Update the value and move the accessed item to the front of the list
        it-&gt;second-&gt;second = value;
        list_.splice(list_.begin(), list_, it-&gt;second);
    } else {
        // Check if the cache is full
        if (list_.size() &gt;= capacity_) {
            // Remove the least recently used item from the back of the list
            cache_.erase(list_.back()-&gt;first);
            list_.pop_back();
        }
        // Add the new item to the front of the list
        list_.emplace_front(key, value);
        cache_[key] = list_.begin();
    }
}

// Remove a value from the cache
void remove(const Key&amp; key) {
    auto it = cache_.find(key);
    if (it != cache_.end()) {
        // Remove the item from the list
        list_.erase(it-&gt;second);
        // Remove the item from the cache
        cache_.erase(it);
    }
}

private:
// The cache is implemented as an unordered map
std::unordered_map<Key, std::list_node_ptr> cache_;
// The list is implemented as a doubly linked list
std::list<std::pair<Key, Value>, std::allocator<std::pair<Key, Value>>> list_;
// The capacity of the cache
size_t capacity_;
};
// A node in the doubly linked list
struct list_node {
Key key;
Value value;
list_node* prev;
list_node* next;
};
// A pointer to a node in the doubly linked list
using list_node_ptr = std::unique_ptr<list_node>;

Explanation

The LRU cache implementation uses a combination of an unordered map and a doubly linked list to store and manage cache items. The unordered map is used to store the cache items with their keys, and the doubly linked list is used to keep track of the order in which the items were accessed.

The get function is used to retrieve a value from the cache. If the key is found in the cache, the accessed item is moved to the front of the list, and the value is returned. If the key is not found in the cache, an empty optional is returned.

The set function is used to add a new item to the cache. If the key already exists in the cache, the value is updated, and the accessed item is moved to the front of the list. If the cache is full, the least recently used item is removed from the back of the list, and the new item is added to the front of the list.

The remove function is used to remove a value from the cache. If the key is found in the cache, the item is removed from the list, and the item is removed from the cache.

Example Use Cases

Here are some example use cases for the LRU cache implementation:

int main() {
    // Create an LRU cache with a capacity of 5
    LRUCache<int, std::string, 5> cache;
// Add some items to the cache
cache.set(1, &quot;one&quot;);
cache.set(2, &quot;two&quot;);
cache.set(3, &quot;three&quot;);
cache.set(4, &quot;four&quot;);
cache.set(5, &quot;five&quot;);

// Get some values from the cache
std::cout &lt;&lt; cache.get(1).value_or(&quot;Not found&quot;) &lt;&lt; std::endl;  // Output: one
std::cout &lt;&lt; cache.get(2).value_or(&quot;Not found&quot;) &lt;&lt; std::endl;  // Output: two
std::cout &lt;&lt; cache.get(3).value_or(&quot;Not found&quot;) &lt;&lt; std::endl;  // Output: three
std::cout &lt;&lt; cache.get(4).value_or(&quot;Not found&quot;) &lt;&lt; std::endl;  // Output: four
std::cout &lt;&lt; cache.get(5).value_or(&quot;Not found&quot;) &lt;&lt; std::endl;  // Output: five

// Remove some items from the cache
cache.remove(2);
cache.remove(3);

// Get some values from the cache after removal
std::cout &lt;&lt; cache.get(1).value_or(&quot;Not found&quot;) &lt;&lt; std::endl;  // Output: one
std::cout &lt;&lt; cache.get(2).value_or(&quot;Not found&quot;) &lt;&lt; std::endl;  // Output: Not found
std::cout &lt;&lt; cache.get(3).value_or(&quot;Not found&quot;) &lt;&lt; std::endl;  // Output: Not found
std::cout &lt;&lt; cache.get(4).value_or(&quot;Not found&quot;) &lt;&lt; std::endl;  // Output: four
std::cout &lt;&lt; cache.get(5).value_or(&quot;Not found&quot;) &lt;&lt; std::endl;  // Output: five

return 0;

}

Conclusion

In this article, we explored a simple implementation of a Least Recently Used (LRU) cache in C++20. The LRU cache is a data structure that stores a limited number of items, and when the cache is full, it discards the least recently used items to make room for new ones. This implementation is a basic example of a cache and can be used as a starting point for more complex cache implementations.

The get function is used to retrieve a value from the cache, the set function is used to add a new item to the cache, and the remove function is used to remove a value from the cache.

The example use cases demonstrate how to use the LRU cache implementation to add and retrieve items from the cache, and how to remove items from the cache.

Future Work

In the future, we can improve the LRU cache implementation by adding more features, such as:

Eviction policy: Implement a custom eviction policy to determine which items to remove from the cache when it is full.
Cache size: Allow the cache size to be dynamically adjusted based on the number of items in the cache.
Cache expiration: Implement a cache expiration mechanism to automatically remove items from the cache after a certain period of time.
Multi-threading: Make the LRU cache implementation thread-safe to allow multiple threads to access the cache simultaneously.

Q: What is an LRU cache?

A: An LRU (Least Recently Used) cache is a data structure that stores a limited number of items, and when the cache is full, it discards the least recently used items to make room for new ones.

Q: Why do we need an LRU cache?

A: An LRU cache is useful when we need to store a large amount of data, but we only need to access a small portion of it at a time. By storing the most recently used items in the cache, we can improve the performance of our application by reducing the number of times we need to access the underlying data.

Q: How does an LRU cache work?

A: An LRU cache works by using a combination of a hash table and a doubly linked list to store and manage cache items. The hash table is used to store the cache items with their keys, and the doubly linked list is used to keep track of the order in which the items were accessed.

Q: What are the benefits of using an LRU cache?

A: The benefits of using an LRU cache include:

Improved performance: By storing the most recently used items in the cache, we can improve the performance of our application by reducing the number of times we need to access the underlying data.
Reduced memory usage: By storing only the most recently used items in the cache, we can reduce the amount of memory used by our application.
Simplified code: By using a cache, we can simplify our code by reducing the number of times we need to access the underlying data.

Q: What are the limitations of using an LRU cache?

A: The limitations of using an LRU cache include:

Cache size: The cache size is limited, and we need to carefully manage the cache size to ensure that we have enough space to store the most recently used items.
Cache eviction: When the cache is full, we need to evict the least recently used items to make room for new ones, which can lead to performance issues if not implemented correctly.
Cache expiration: We need to implement a cache expiration mechanism to automatically remove items from the cache after a certain period of time.

Q: How do I implement an LRU cache in C++?

A: To implement an LRU cache in C++, you can use a combination of a hash table and a doubly linked list to store and manage cache items. Here is an example implementation:

template <typename Key, typename Value, size_t Capacity>
class LRUCache {
public:
    // Constructor
    LRUCache() : capacity_(Capacity) {}
// Destructor
~LRUCache() = default;

// Copy constructor and assignment operator are deleted
LRUCache(const LRUCache&amp;) = delete;
LRUCache&amp; operator=(const LRUCache&amp;) = delete;

// Move constructor and assignment operator are deleted
LRUCache(LRUCache&amp;&amp;) = delete;
LRUCache&amp; operator=(LRUCache&amp;&amp;) = delete;

// Get a value from the cache
std::optional&lt;Value&gt; get(const Key&amp; key) {
    auto it = cache_.find(key);
    if (it != cache_.end()) {
        // Move the accessed item to the front of the list
        list_.splice(list_.begin(), list_, it-&gt;second);
        return it-&gt;second-&gt;second;
    }
    return std::nullopt;
}

// Set a value in the cache
void set(const Key&amp; key, const Value&amp; value) {
    // Check if the key already exists in the cache
    auto it = cache_.find(key);
    if (it != cache_.end()) {
        // Update the value and move the accessed item to the front of the list
        it-&gt;second-&gt;second = value;
        list_.splice(list_.begin(), list_, it-&gt;second);
    } else {
        // Check if the cache is full
        if (list_.size() &gt;= capacity_) {
            // Remove the least recently used item from the back of the list
            cache_.erase(list_.back()-&gt;first);
            list_.pop_back();
        }
        // Add the new item to the front of the list
        list_.emplace_front(key, value);
        cache_[key] = list_.begin();
    }
}

// Remove a value from the cache
void remove(const Key&amp; key) {
    auto it = cache_.find(key);
    if (it != cache_.end()) {
        // Remove the item from the list
        list_.erase(it-&gt;second);
        // Remove the item from the cache
        cache_.erase(it);
    }
}

private:
// The cache is implemented as an unordered map
std::unordered_map<Key, std::list_node_ptr> cache_;
// The list is implemented as a doubly linked list
std::list<std::pair<Key, Value>, std::allocator<std::pair<Key, Value>>> list_;
// The capacity of the cache
size_t capacity_;
};

Q: How do I use an LRU cache in C++?

A: To use an LRU cache in C++, you can create an instance of the LRUCache class and use the get and set functions to access and store items in the cache. Here is an example:

int main() {
    // Create an LRU cache with a capacity of 5
    LRUCache<int, std::string, 5> cache;
// Add some items to the cache
cache.set(1, &quot;one&quot;);
cache.set(2, &quot;two&quot;);
cache.set(3, &quot;three&quot;);
cache.set(4, &quot;four&quot;);
cache.set(5, &quot;five&quot;);

// Get some values from the cache
std::cout &lt;&lt; cache.get(1).value_or(&quot;Not found&quot;) &lt;&lt; std::endl;  // Output: one
std::cout &lt;&lt; cache.get(2).value_or(&quot;Not found&quot;) &lt;&lt; std::endl;  // Output: two
std::cout &lt;&lt; cache.get(3).value_or(&quot;Not found&quot;) &lt;&lt; std::endl;  // Output: three
std::cout &lt;&lt; cache.get(4).value_or(&quot;Not found&quot;) &lt;&lt; std::endl;  // Output: four
std::cout &lt;&lt; cache.get(5).value_or(&quot;Not found&quot;) &lt;&lt; std::endl;  // Output: five

// Remove some items from the cache
cache.remove(2);
cache.remove(3);

// Get some values from the cache after removal
std::cout &lt;&lt; cache.get(1).value_or(&quot;Not found&quot;) &lt;&lt; std::endl;  // Output: one
std::cout &lt;&lt; cache.get(2).value_or(&quot;Not found&quot;) &lt;&lt; std::endl;  // Output: Not found
std::cout &lt;&lt; cache.get(3).value_or(&quot;Not found&quot;) &lt;&lt; std::endl;  // Output: Not found
std::cout &lt;&lt; cache.get(4).value_or(&quot;Not found&quot;) &lt;&lt; std::endl;  // Output: four
std::cout &lt;&lt; cache.get(5).value_or(&quot;Not found&quot;) &lt;&lt; std::endl;  // Output: five

return 0;

}

Conclusion

In this article, we explored the concept of an LRU cache and how it can be implemented in C++. We also discussed the benefits and limitations of using an LRU cache, and provided an example implementation and usage of the LRUCache class.