cppadvanced60 minutes

Design and Implement a Thread-Safe LRU Cache in C++

Create a high-performance, thread-safe Least Recently Used (LRU) cache class in C++. The cache should support concurrent access from multiple threads and provide O(1) time complexity for insertions, lookups, and deletions.

Challenge prompt

Implement a generic thread-safe LRU cache class template in C++ with the following requirements: - The cache should store key-value pairs and have a fixed maximum capacity provided at initialization. - When the cache max capacity is reached, it should evict the least recently used item before inserting a new one. - Provide methods: get(key), put(key, value), and size(). The get should return std::optional<ValueType> to handle missing keys. - Ensure that the cache supports safe concurrent access by multiple threads with minimal locking to allow maximum performance. - Internally, achieve O(1) average complexity for the get and put operations. Your solution should leverage appropriate C++11 (or later) concurrency primitives and containers such as mutexes, unordered_map, and doubly-linked lists or equivalents.

Guidance

• Use an unordered_map for fast key lookups and a linked data structure (e.g., std::list) to track usage order.
• Synchronize access with mutexes to protect shared data, ensuring deadlock-free design.
• Update the position of keys on every successful get or put to mark them as recently used.

Hints

• std::list iterators remain valid upon insertions and removals of other elements, useful for O(1) updates.
• Use a single mutex or consider a shared_mutex with shared locking for readers and exclusive for writers to improve concurrency.
• Return std::optional to handle cache misses cleanly and idiomatically.

Starter code

#include <unordered_map>
#include <list>
#include <mutex>
#include <optional>

template <typename KeyType, typename ValueType>
class ThreadSafeLRUCache {
public:
    explicit ThreadSafeLRUCache(size_t capacity) : capacity_(capacity) {}

    std::optional<ValueType> get(const KeyType& key) {
        // TODO: Implement get with thread safety and LRU update
        return std::nullopt;
    }

    void put(const KeyType& key, const ValueType& value) {
        // TODO: Implement put with thread safety and eviction
    }

    size_t size() const {
        std::lock_guard<std::mutex> lock(mtx_);
        return cache_map_.size();
    }

private:
    size_t capacity_;
    mutable std::mutex mtx_;
    std::list<KeyType> usage_order_;
    std::unordered_map<KeyType, std::pair<ValueType, typename std::list<KeyType>::iterator>> cache_map_;
};

Expected output

A thread-safe LRU cache class that passes usage examples such as: ThreadSafeLRUCache<int, std::string> cache(2); cache.put(1, "one"); cache.put(2, "two"); assert(cache.get(1).value() == "one"); cache.put(3, "three"); assert(!cache.get(2).has_value()); // 2 was evicted assert(cache.get(3).value() == "three");

Core concepts

Concurrency and thread safetyData structures (unordered_map and linked list)Cache eviction policies (LRU)C++11 standard library features (mutex, optional, templates)

Challenge a Friend

Send this duel to someone else and see if they can solve it.