LRU Cache in C++

A thread-safe, generic Least Recently Used (LRU) cache implementation in C++17 with an interactive CLI demo and benchmarking suite.

What is an LRU Cache?

An LRU Cache stores a fixed number of items and evicts the least recently used item when full. It's widely used in operating systems, databases, and web servers to speed up repeated data access.

Features

• Generic — works with any key/value types via C++ templates
• Thread-safe — uses std::mutex to handle concurrent access safely
• O(1) operations — get, put, and remove all run in constant time
• Hit/miss tracking — tracks cache hits, misses, and hit rate
• Interactive CLI — demo the cache with a menu-driven interface
• Benchmarking — measure performance across different cache sizes and workloads

Project Structure

lru-cache/ ├── LRUCache.h # Core cache implementation (header-only template class) ├── main.cpp # Interactive CLI demo ├── benchmark.cpp # Performance benchmarking suite └── README.md

How It Works

The cache combines two data structures:

• A doubly linked list — maintains LRU order. Most recently used items sit at the front, least recently used at the back
• A hash map — maps keys to list iterators for O(1) lookup

On a cache hit, the item is moved to the front of the list. On a miss, the item at the back (LRU) is evicted to make room for the new entry.

Build & Run

CLI Demo

g++ -std=c++17 -pthread -o lru_cache main.cpp
./lru_cache

Benchmark

g++ -std=c++17 -pthread -o benchmark benchmark.cpp
./benchmark

Benchmark Results

Cache Size	Key Range	Operations	Hit Rate	Time
10	1-100	10,000	10.28%	9.5ms
90	1-100	10,000	89.31%	3.3ms
100	1-100	10,000	99%	2.0ms

As cache size increases relative to the key range, hit rate improves and access time drops — demonstrating the core value of caching.

Example CLI Session

🗂 Welcome to LRU Cache Demo Enter cache capacity: 3 ✓ Cache created with capacity 3 Choice: 1 (Put) → [name] = Layi Choice: 1 (Put) → [school] = Michigan Choice: 1 (Put) → [lang] = C++ Choice: 1 (Put) → [job] = Uber ← evicts [name] (LRU) Choice: 2 (Get) → Hit! [school] = Michigan Choice: 2 (Get) → Miss — key not found: name 📊 Cache Stats: Hits : 1 Misses : 1 Hit Rate : 50%

Time Complexity

Operation	Time Complexity
get()	O(1)
put()	O(1)
remove()	O(1)
contains()	O(1)