生产代码中的LRU实现

Question

我有一些C++代码,我需要使用LRU技术实现缓存替换.
到目前为止,我知道实现LRU缓存替换的两种方法:

1. 每次访问缓存数据时使用timeStamp,最后在更换时比较timeStamps.
2. 使用一堆缓存的项目并在最近访问它们时将它们移动到顶部,因此最后底部将包含LRU Candidate.

那么,哪些更适合在生产代码中使用？
他们还有其他更好的方法吗？

Answer 1

最近,我使用遍布哈希映射的链表实现了LRU缓存.

    /// Typedef for URL/Entry pair
    typedef std::pair< std::string, Entry > EntryPair;

    /// Typedef for Cache list
    typedef std::list< EntryPair > CacheList;

    /// Typedef for URL-indexed map into the CacheList
    typedef boost::unordered_map< std::string, CacheList::iterator > CacheMap;

    /// Cache LRU list
    CacheList mCacheList;

    /// Cache map into the list
    CacheMap mCacheMap;

它具有对所有重要操作都是O(1)的优点.

插入算法:

// create new entry
Entry iEntry( ... );

// push it to the front;
mCacheList.push_front( std::make_pair( aURL, iEntry ) );

// add it to the cache map
mCacheMap[ aURL ] = mCacheList.begin();

// increase count of entries
mEntries++;

// check if it's time to remove the last element
if ( mEntries > mMaxEntries )
{
    // erease from the map the last cache list element
    mCacheMap.erase( mCacheList.back().first );

    // erase it from the list
    mCacheList.pop_back();

    // decrease count
    mEntries--;
}

Answer 2

这是一个非常简单的LRU缓存实现

https://github.com/lamerman/cpp-lru-cache.

它易于使用并了解其工作原理.代码的总大小约为50行.

Answer 3

为简单起见,您可以考虑使用Boost的MultiIndex贴图.如果我们将密钥与数据分开,我们在同一数据上支持多组密钥.

来自[ http://old.nabble.com/realization-of-Last-Recently-Used-cache-with-boost%3A%3Amulti_index-td22326432.html ]:

"...使用两个索引:1)哈希用于按键搜索值2)顺序跟踪最近使用过的项目(获取函数把项目作为最后一项查询.如果我们需要从缓存中删除一些项目,我们可能会删除它们从序列开始.)"

请注意,"项目"运算符"允许程序员有效地在同一个multi_index_container的不同索引之间移动".