29

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

  1. 每次访问缓存数据时使用timeStamp，最后比较替换时的timeStamps。
  2. 使用一堆缓存项，如果最近访问它们，则将它们移动到顶部，因此最后底部将包含 LRU Candidate。

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

4

5 回答 5

39

最近，我使用散列映射上的链表实现了 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--;
}
于 2010-01-13T14:50:47.700 回答
11

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

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

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

于 2013-06-21T06:45:42.357 回答
6

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

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

"...使用两个索引：1) 散列用于按键搜索值 2) 顺序用于跟踪最近使用的项目（获取函数将项目作为最后一个项目在 sequesnce 中。如果我们需要从缓存中删除一些项目，我们可以删除它们从序列开始）。”

请注意，“项目”运算符“允许程序员有效地在同一 multi_index_container 的不同索引之间移动”。

于 2010-07-20T02:36:39.210 回答
4

本文描述了使用一对 STL 容器（键值映射加上键访问历史列表）或单个boost::bimap.

于 2010-11-26T14:27:55.120 回答
2

在我们的生产环境中，我们使用类似于Linux 内核链表的 C++ 双链表。它的美妙之处在于您可以根据需要将对象添加到任意数量的链表中，并且列表操作快速而简单。

于 2010-01-13T17:49:02.977 回答