生产代码中的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缓存实现

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

它很容易使用和理解它是如何工作的。代码的总大小约为50行。

为了简单起见,也许您应该考虑使用Boost的多索引映射。如果我们将键与数据分开,我们就支持同一数据上的多组键。

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

“…使用两个索引:1)按键散列搜索值2)按顺序跟踪最近使用的项(get函数put item as last item in sequence)。如果我们需要从缓存中删除某些项,我们可以从序列开始删除它们。“

请注意,“项目”操作符允许程序员有效地在同一个多索引容器的不同索引之间移动。

这个 article 描述使用一对STL容器(键值映射加上键访问历史记录列表)或单个 boost::bimap .

在我们的生产环境中,我们使用一个类似于 Linux kernel linked list . 它的好处在于,您可以根据需要将对象添加到任意多个链接列表中,并且列表操作既快速又简单。