cpp-lru-cache

C++Cache LibraryLRUHeader-onlyPerformanceHashMapLinked List

Cache Library

cpp-lru-cache

Overview

cpp-lru-cache is a simple and reliable LRU cache library for C++ based on hashmap and linked list.

Details

cpp-lru-cache is a header-only LRU (Least Recently Used) cache library for C++11 and later, developed by Alexander Ponomarev. Implemented using a combination of std::unordered_map and std::list, it provides O(1) time complexity for get, put, and exists operations. The library is fully templated, supporting any key-value type combination, and ensures reliability through minimal logic using standard containers. No installation is required - simply include the header file to start using it. It supports exception safety and move semantics. The LRU algorithm automatically removes the least recently accessed elements when the cache becomes full, enabling memory-efficient operation. Since the C++ standard library doesn't provide an LRU cache implementation, this library plays a crucial role in performance optimization for many applications.

Pros and Cons

Pros

O(1) Performance: get, put, and exists operations execute in constant time
Header-only: Easy integration without installation requirements
Template Support: Works with any key-value type combination
Standards Compliant: Safe implementation using std::unordered_map and std::list
Exception Safe: Maintains cache consistency even when exceptions occur
Move Semantics: Leverages C++11 move semantics for efficiency
Lightweight Design: High reliability with minimal logic

Cons

C++11 Requirement: Cannot be used with older C++ standards
Memory Overhead: Dual management of hashmap and linked list
Thread Safety: Requires external synchronization in multi-threaded environments
Limited Features: No advanced features like TTL or size-based eviction
Type Constraints: Key types must be hashable and equality comparable

Key Links

Usage Examples

Basic Usage

#include "lru_cache.h"
#include <iostream>
#include <string>

int main() {
    // Create LRU cache with maximum 3 elements
    cache::lru_cache<int, std::string> cache(3);
    
    // Insert elements
    cache.put(1, "one");
    cache.put(2, "two");
    cache.put(3, "three");
    
    // Retrieve elements
    std::string value;
    if (cache.get(1, value)) {
        std::cout << "Key 1: " << value << std::endl;
    }
    
    // Check element existence
    if (cache.exists(2)) {
        std::cout << "Key 2 exists" << std::endl;
    }
    
    // Check cache size
    std::cout << "Cache size: " << cache.size() << std::endl;
    
    return 0;
}

String Key-Value Example

#include "lru_cache.h"
#include <iostream>
#include <string>

class StringCache {
private:
    cache::lru_cache<std::string, std::string> cache_;
    
public:
    StringCache(size_t capacity) : cache_(capacity) {}
    
    void put(const std::string& key, const std::string& value) {
        cache_.put(key, value);
        std::cout << "Cached: " << key << " -> " << value << std::endl;
    }
    
    std::string get(const std::string& key) {
        std::string value;
        if (cache_.get(key, value)) {
            std::cout << "Cache hit: " << key << " -> " << value << std::endl;
            return value;
        } else {
            std::cout << "Cache miss: " << key << std::endl;
            return "";
        }
    }
    
    bool exists(const std::string& key) {
        return cache_.exists(key);
    }
    
    size_t size() const {
        return cache_.size();
    }
    
    void clear() {
        cache_.clear();
        std::cout << "Cache cleared" << std::endl;
    }
};

// Usage example
int main() {
    StringCache cache(5);
    
    cache.put("user:1", "Alice");
    cache.put("user:2", "Bob");
    cache.put("user:3", "Charlie");
    
    std::string user = cache.get("user:1");  // Cache hit
    std::string unknown = cache.get("user:4");  // Cache miss
    
    std::cout << "Cache size: " << cache.size() << std::endl;
    
    return 0;
}

Custom Object Caching

#include "lru_cache.h"
#include <iostream>
#include <string>
#include <memory>

struct User {
    int id;
    std::string name;
    std::string email;
    
    User(int id, const std::string& name, const std::string& email)
        : id(id), name(name), email(email) {}
};

class UserCache {
private:
    cache::lru_cache<int, std::shared_ptr<User>> cache_;
    
public:
    UserCache(size_t capacity) : cache_(capacity) {}
    
    void cacheUser(std::shared_ptr<User> user) {
        cache_.put(user->id, user);
        std::cout << "Cached user: " << user->name << std::endl;
    }
    
    std::shared_ptr<User> getUser(int userId) {
        std::shared_ptr<User> user;
        if (cache_.get(userId, user)) {
            std::cout << "User found in cache: " << user->name << std::endl;
            return user;
        } else {
            std::cout << "User not in cache: " << userId << std::endl;
            return nullptr;
        }
    }
    
    bool hasUser(int userId) {
        return cache_.exists(userId);
    }
    
    void printCacheInfo() {
        std::cout << "Cache size: " << cache_.size() << std::endl;
    }
};

// Usage example
int main() {
    UserCache userCache(3);
    
    // Create and cache users
    auto alice = std::make_shared<User>(1, "Alice", "[email protected]");
    auto bob = std::make_shared<User>(2, "Bob", "[email protected]");
    auto charlie = std::make_shared<User>(3, "Charlie", "[email protected]");
    
    userCache.cacheUser(alice);
    userCache.cacheUser(bob);
    userCache.cacheUser(charlie);
    
    // Retrieve user from cache
    auto cachedUser = userCache.getUser(1);
    if (cachedUser) {
        std::cout << "Retrieved: " << cachedUser->email << std::endl;
    }
    
    userCache.printCacheInfo();
    
    return 0;
}

File Cache Implementation

#include "lru_cache.h"
#include <iostream>
#include <string>
#include <fstream>
#include <sstream>

class FileCache {
private:
    cache::lru_cache<std::string, std::string> cache_;
    
    std::string loadFileContent(const std::string& filename) {
        std::ifstream file(filename);
        if (!file.is_open()) {
            throw std::runtime_error("Cannot open file: " + filename);
        }
        
        std::stringstream buffer;
        buffer << file.rdbuf();
        return buffer.str();
    }
    
public:
    FileCache(size_t capacity) : cache_(capacity) {}
    
    std::string getFileContent(const std::string& filename) {
        std::string content;
        
        // Search in cache
        if (cache_.get(filename, content)) {
            std::cout << "File served from cache: " << filename << std::endl;
            return content;
        }
        
        // Load file
        try {
            content = loadFileContent(filename);
            cache_.put(filename, content);
            std::cout << "File loaded and cached: " << filename << std::endl;
            return content;
        } catch (const std::exception& e) {
            std::cerr << "Error loading file: " << e.what() << std::endl;
            return "";
        }
    }
    
    bool isFileCached(const std::string& filename) {
        return cache_.exists(filename);
    }
    
    void evictFile(const std::string& filename) {
        // Note: cpp-lru-cache doesn't have direct removal method
        // This would require cache modification or workaround
        std::cout << "File eviction requested: " << filename << std::endl;
    }
    
    void printStats() {
        std::cout << "Cached files: " << cache_.size() << std::endl;
    }
};

// Usage example
int main() {
    FileCache fileCache(5);
    
    std::string content1 = fileCache.getFileContent("config.txt");
    std::string content2 = fileCache.getFileContent("data.json");
    std::string content3 = fileCache.getFileContent("config.txt");  // Cache hit
    
    fileCache.printStats();
    
    return 0;
}

Computation Result Caching

#include "lru_cache.h"
#include <iostream>
#include <chrono>
#include <cmath>

class ComputationCache {
private:
    cache::lru_cache<double, double> cache_;
    
    double expensiveComputation(double x) {
        // Simulate expensive computation
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
        return std::sin(x) * std::cos(x) + std::sqrt(std::abs(x));
    }
    
public:
    ComputationCache(size_t capacity) : cache_(capacity) {}
    
    double compute(double x) {
        double result;
        
        if (cache_.get(x, result)) {
            std::cout << "Computation result from cache: f(" << x << ") = " << result << std::endl;
            return result;
        }
        
        auto start = std::chrono::high_resolution_clock::now();
        result = expensiveComputation(x);
        auto end = std::chrono::high_resolution_clock::now();
        
        auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
        std::cout << "Computed f(" << x << ") = " << result 
                  << " in " << duration.count() << "ms" << std::endl;
        
        cache_.put(x, result);
        return result;
    }
    
    void benchmarkCache() {
        std::vector<double> inputs = {1.0, 2.0, 3.0, 1.0, 2.0, 4.0, 1.0};
        
        std::cout << "\n=== Cache Benchmark ===" << std::endl;
        for (double input : inputs) {
            compute(input);
        }
        
        std::cout << "Final cache size: " << cache_.size() << std::endl;
    }
};

// Usage example
int main() {
    ComputationCache compCache(3);
    compCache.benchmarkCache();
    
    return 0;
}