生产代码中的LRU实现

问题内容：

我有一些C ++代码，需要在其中使用LRU技术实现缓存替换。
到目前为止，我知道两种实现LRU缓存替换的方法：

每次访问缓存的数据时都使用timeStamp，最后在替换时比较timeStamps。
如果最近访问过它们，则使用一堆缓存项并将它们移到顶部，因此最后底部将包含LRU候选对象。

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

问题答案：

最近，我使用散列在哈希图中的链表实现了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--;
}

生产代码中的LRU实现

微信关注