Data Structures & STL

C++ LRU Cache (std::list & std::unordered_map)

Implement a high-performance LRU Cache in C++ using std::list for double-linked list ordering and std::unordered_map for O(1) key lookups.

C++ Source Code

Editable code sample with line numbers

C++

#include <iostream>
#include <list>
#include <unordered_map>
#include <string>

class LRUCache {
private:
    int capacity;
    std::list<std::pair<int, std::string>> items; // {key, value}
    std::unordered_map<int, std::list<std::pair<int, std::string>>::iterator> cache;

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

std::string get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) return "NOT_FOUND";

// Move the accessed item to the front of list
        items.splice(items.begin(), items, it->second);
        return it->second->second;
    }

void put(int key, const std::string& value) {
        auto it = cache.find(key);
        if (it != cache.end()) {
            it->second->second = value;
            items.splice(items.begin(), items, it->second);
            return;
        }

if (items.size() >= capacity) {
            // Evict least recently used (back of list)
            int lastKey = items.back().first;
            cache.erase(lastKey);
            items.pop_back();
        }

items.emplace_front(key, value);
        cache[key] = items.begin();
    }
};

int main() {
    LRUCache lru(2);
    lru.put(1, "Alpha");
    lru.put(2, "Beta");

std::cout << "Get Key 1: " << lru.get(1) << std::endl; // Access Key 1
    lru.put(3, "Gamma");                                    // Evicts Key 2

std::cout << "Get Key 2 (Evicted): " << lru.get(2) << std::endl;
    std::cout << "Get Key 3:           " << lru.get(3) << std::endl;
    return 0;
}

Expected Output

When this program is compiled and executed, the terminal outputs:

Get Key 1: Alpha
Get Key 2 (Evicted): NOT_FOUND
Get Key 3:           Gamma

How the Code Works

std::list::splice allows relinking nodes within the doubly-linked list in O(1) time without copying memory. Combining it with std::unordered_map provides O(1) element lookup and O(1) recency renewal.

Time Complexity

O(1) for both get and put

Space Complexity

O(Capacity)

Key Takeaways & Best Practices

std::list::splice moves elements between list positions in O(1) constant time.
Storing list iterators in unordered_map avoids list traversal.

Master C++ with ZenCompiler

Practice in our high-performance cloud container IDE with multi-file support, interactive terminal STDIN, real-time memory visualizer, and structured lessons.

Related C++ Examples

Trees & Strings

O(L) for Insert, Search, and StartsWith

C++ Trie (Prefix Tree) Implementation

Build an efficient Prefix Tree (Trie) in C++ supporting fast word insertion, full match search, and prefix matching.

C++ Binary Search (Custom Implementation & std::binary_search)

Implement a template-based binary search algorithm in C++ and compare it with the Standard Template Library (STL) algorithms std::binary_search and std::lower_bound.

Runnable Code

View Code

Algorithms & STL

O(N log N) average, O(N²) worst-case

C++ QuickSort Algorithm (Lomuto & Hoare Partitioning)

Implement the high-performance QuickSort divide-and-conquer sorting algorithm in C++ using in-place median/pivot partitioning.

Runnable Code

View Code

How the Code Works

std::list::splice allows relinking nodes within the doubly-linked list in O(1) time without copying memory. Combining it with std::unordered_map provides O(1) element lookup and O(1) recency renewal.

Time Complexity

O(1) for both get and put

Space Complexity

O(Capacity)

Key Takeaways & Best Practices

std::list::splice moves elements between list positions in O(1) constant time.
Storing list iterators in unordered_map avoids list traversal.

C++ LRU Cache (std::list & std::unordered_map)

C++ Source Code

Expected Output

How the Code Works

Key Takeaways & Best Practices

Master C++ with ZenCompiler

Related C++ Examples

C++ Trie (Prefix Tree) Implementation

C++ Binary Search (Custom Implementation & std::binary_search)

C++ QuickSort Algorithm (Lomuto & Hoare Partitioning)

Platform & Tools

Account

Company & Help

Legal & Policies

C++ LRU Cache (std::list & std::unordered_map)

C++ Source Code

Expected Output

How the Code Works

Key Takeaways & Best Practices

Master C++ with ZenCompiler

Related C++ Examples

C++ Trie (Prefix Tree) Implementation

C++ Binary Search (Custom Implementation & std::binary_search)

C++ QuickSort Algorithm (Lomuto & Hoare Partitioning)