Introduction

The Least Recently Used (LRU) cache is a type of data structure that is particularly effective for managing data that may not fit entirely into memory. Implemented as part of various caching strategies, the LRU policy evicts the least recently accessed items to make space for new data. In this article, we'll explore how to implement an LRU cache in C++, along with technical explanations and examples to illustrate its functionality.

Why Use an LRU Cache?

An LRU cache can be invaluable when you're working with databases, operating systems, or any application where memory resources are constrained. The main idea is simple: track the recent usage patterns of data to make intelligent decisions about which data to keep and which to evict.

Data Structure

The optimal structure for an LRU cache combines a hash map for fast access and a doubly-linked list for quick updates to the cache order. Here's a breakdown of the components:

1. Hash Map: Provides average $O(1)$ time complexity for lookups, storing cache entries with keys and pointers to the positions in the doubly-linked list.
2. Doubly-Linked List: Facilitates efficient inserts and deletes with $O(1)$ time complexity, maintaining the order of usage from most to least recent.

C++ Implementation

Let's dive into a C++ implementation of an LRU cache that uses these data structures. We'll first define the core elements necessary to execute the LRU policy.

Example Code

1#include <iostream>
2#include <unordered_map>
3#include <list>
4
5class LRUCache {
6public:
7    LRUCache(int capacity) : capacity(capacity) {}
8
9    int get(int key) {
10        if (cacheMap.find(key) == cacheMap.end()) {
11            return -1; // Key not found
12        } else {
13            // Move the accessed node to the front
14            auto it = cacheMap[key];
15            cacheList.splice(cacheList.begin(), cacheList, it);
16            return it->second;
17        }
18    }
19
20    void put(int key, int value) {
21        if (cacheMap.find(key) != cacheMap.end()) {
22            // Update the existing node and move to the front
23            auto it = cacheMap[key];
24            it->second = value;
25            cacheList.splice(cacheList.begin(), cacheList, it);
26        } else {
27            if (cacheList.size() == capacity) {
28                // Remove the least recently used item from the cache
29                int lruKey = cacheList.back().first;
30                cacheMap.erase(lruKey);
31                cacheList.pop_back();
32            }
33            // Insert the new item at the front
34            cacheList.emplace_front(key, value);
35            cacheMap[key] = cacheList.begin();
36        }
37    }
38
39private:
40    int capacity;
41    std::list<std::pair<int, int>> cacheList;
42    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cacheMap;
43};
44
45int main() {
46    LRUCache cache(3);
47    cache.put(1, 1);
48    cache.put(2, 2);
49    cache.put(3, 3);
50    std::cout << "Get 1: " << cache.get(1) << std::endl; // Outputs 1
51    cache.put(4, 4); // Evicts key 2
52    std::cout << "Get 2: " << cache.get(2) << std::endl; // Outputs -1 (not found)
53    cache.put(5, 5); // Evicts key 3
54    std::cout << "Get 3: " << cache.get(3) << std::endl; // Outputs -1 (not found)
55    return 0;
56}

Explanation

• Constructor: Initializes the cache with a specified capacity.
• Get Method:
  • Checks if the item exists in the cache.
  • Moves accessed key to the head of the list, indicating recent use.
• Put Method:
  • Updates the cache if the item already exists.
  • If the cache is full, removes the least recently used item.
  • Inserts the new item at the head of the list.

Performance Considerations

An LRU cache implemented as above provides excellent time complexity characteristics:

• Both get and put operations work in $O(1)$ time.
• The eviction of the least-recently used item is efficiently handled by maintaining the order in a doubly-linked list.

Key Points Summary

Conclusion

The LRU cache is a fundamental concept in many applications where efficient memory management is required. By combining a hash map and a doubly-linked list, the LRU cache offers simplicity with excellent performance. This C++ implementation provides a practical example of how to build an efficient LRU caching mechanism capable of handling dynamic access patterns.