キャッシュライブラリ

cpp-lru-cache

概要

cpp-lru-cacheは、ハッシュマップと連結リストを基盤とした、シンプルで信頼性の高いC++向けLRUキャッシュライブラリです。

詳細

cpp-lru-cache（シープラスプラス・エルアールユー・キャッシュ）は、Alexander Ponomarevによって開発された、C++11以降で使用可能なヘッダーオンリーのLRU（Least Recently Used）キャッシュライブラリです。std::unordered_mapとstd::listの組み合わせによる実装で、O(1)の時間計算量でget、put、existsの各操作を実行できます。ライブラリはテンプレート化されており、任意のキー・バリュー型の組み合わせで使用でき、標準コンテナを使用した最小限のロジックで信頼性を保証しています。インストール不要でヘッダーファイルをインクルードするだけで使用でき、例外安全性とmove semanticsをサポートしています。LRUアルゴリズムにより、キャッシュが満杯になると最も長時間アクセスされていない要素が自動的に削除されるため、メモリ効率的な運用が可能です。C++標準ライブラリにはLRUキャッシュの実装が提供されていないため、このライブラリは性能最適化において重要な役割を果たします。

メリット・デメリット

メリット

• O(1)パフォーマンス: get、put、exists操作が定数時間で実行
• ヘッダーオンリー: インストール不要で簡単導入
• テンプレート対応: 任意のキー・バリュー型をサポート
• 標準準拠: std::unordered_mapとstd::listを使用した安全な実装
• 例外安全: 例外が発生してもキャッシュの整合性を保証
• Move Semantics: C++11の移動セマンティクスを活用
• 軽量設計: 最小限のロジックで高い信頼性

デメリット

• C++11要件: 古いC++標準では使用不可
• メモリオーバーヘッド: ハッシュマップと連結リストの二重管理
• スレッドセーフティ: マルチスレッド環境では外部同期が必要
• 機能限定: TTLやサイズベース削除などの高度な機能なし
• 型制約: キー型はハッシュ可能で等価比較可能である必要

主要リンク

• GitHub - lamerman/cpp-lru-cache
• C++ LRU Cache Implementation
• LeetCode - LRU Cache Problem

書き方の例

基本的な使用方法

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

int main() {
    // 最大3要素のLRUキャッシュを作成
    cache::lru_cache<int, std::string> cache(3);
    
    // 要素の挿入
    cache.put(1, "one");
    cache.put(2, "two");
    cache.put(3, "three");
    
    // 要素の取得
    std::string value;
    if (cache.get(1, value)) {
        std::cout << "Key 1: " << value << std::endl;
    }
    
    // 要素の存在確認
    if (cache.exists(2)) {
        std::cout << "Key 2 exists" << std::endl;
    }
    
    // キャッシュサイズの確認
    std::cout << "Cache size: " << cache.size() << std::endl;
    
    return 0;
}

文字列キー・値の例

#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;
    }
};

// 使用例
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;
}

カスタムオブジェクトのキャッシュ

#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;
    }
};

// 使用例
int main() {
    UserCache userCache(3);
    
    // ユーザーを作成してキャッシュ
    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);
    
    // キャッシュからユーザーを取得
    auto cachedUser = userCache.getUser(1);
    if (cachedUser) {
        std::cout << "Retrieved: " << cachedUser->email << std::endl;
    }
    
    userCache.printCacheInfo();
    
    return 0;
}

ファイルキャッシュの実装例

#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;
        
        // キャッシュから検索
        if (cache_.get(filename, content)) {
            std::cout << "File served from cache: " << filename << std::endl;
            return content;
        }
        
        // ファイルを読み込み
        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;
    }
};

// 使用例
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");  // キャッシュヒット
    
    fileCache.printStats();
    
    return 0;
}

計算結果キャッシュの例

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

class ComputationCache {
private:
    cache::lru_cache<double, double> cache_;
    
    double expensiveComputation(double x) {
        // 重い計算をシミュレート
        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;
    }
};

// 使用例
int main() {
    ComputationCache compCache(3);
    compCache.benchmarkCache();
    
    return 0;
}