使用 C++ STL 的 MRU 缓存

• 下载源代码 - 1.47 KB

引言

我想你已经知道什么是 MRU 缓存了；否则，你不会阅读这篇文章。这是使用 STL 实现的一个非常简单的版本。

要实现一个缓存，请从此模板类派生一个子类。作为实现者，你需要实现两种方法：

• HandleNonExistingKeyFetch - 用于处理缓存未命中。 在此方法中，你访问缓存背后的真实数据源并返回该值。
• HandleItemRelease - （可选）在从缓存中移除项目时调用。

缓存类是两种类型的模板，一个键和一个值（就像哈希表一样）。值类型是资源的类型，键类型是资源地址的类型（这是你获取资源的方式）。

源代码

#include <list>
#include <map>

/**
 * MRU Cache
 *
 * contains up to a fixed size of "Most Recently Used" items,
 * where items are assiciated with keys.
 * when asked to fetch a value that is not
 * in the cache, HandleNonExistingKeyFetch is called.
 * when an item is removed from the cache, HandleItemRelease is called.
 * implementor of this cache must provide those methods.
 *
 */
template <typename key_type, typename value_type>
class MruCache
{
public:
    
    const int maxLength;

    MruCache(int iMaxLength) : maxLength(iMaxLength) { }

    inline value_type FetchItem(key_type key) { return __fetch_item(key); }

    virtual ~MruCache() { Clear(); }

    /**
     * clear the cache.
     * for every item contained, HandleItemRelease is called.
     */
    virtual void Clear() { __clear(); }


protected:

    virtual void HandleItemRelease(key_type key, value_type value) { };

    virtual value_type HandleNonExistingKeyFetch(key_type key) = 0;

private:

    typedef struct _Entry
    {
        key_type key;
        value_type value;
    } Entry;

    typedef std::list<Entry> EntryList;
    EntryList listOfEntries;

    /**
     * for fast search in the cache.
     * this map contains pointers to iterators in EntryList.
     */
    typedef std::map<key_type, void*> ItrPtrMap;
    ItrPtrMap mapOfListIteratorPtr;

    value_type __fetch_item(key_type key)
    {
        Entry entry;
        EntryList::iterator* ptrItr = 
           (EntryList::iterator*) mapOfListIteratorPtr[key];
        if (!ptrItr)
        {
            if ( (int)listOfEntries.size() >= maxLength)
            {
                Entry lruEntry = listOfEntries.back();
                HandleItemRelease(lruEntry.key, lruEntry.value);
                listOfEntries.pop_back();
                delete mapOfListIteratorPtr[lruEntry.key];
                mapOfListIteratorPtr.erase(lruEntry.key);
            }

            entry.value = HandleNonExistingKeyFetch(key);
            entry.key = key;
            listOfEntries.push_front(entry);

            EntryList::iterator* ptrItr = new EntryList::iterator();
            *ptrItr = listOfEntries.begin();
            mapOfListIteratorPtr[key] = ptrItr;
        }
        else
        {
            entry = *(*ptrItr);
            listOfEntries.erase(*ptrItr);
            listOfEntries.push_front(entry);
            *ptrItr = listOfEntries.begin();
        }
        return entry.value;
    }

    virtual void __clear()
    {
        for (ItrPtrMap::iterator i=mapOfListIteratorPtr.begin(); 
             i!=mapOfListIteratorPtr.end(); i++)
        {
            void* ptrItr = i->second;
            EntryList::iterator* pItr = (EntryList::iterator*) ptrItr;
            HandleItemRelease( (*pItr)->key, (*pItr)->value );
            delete ptrItr;
        }
        listOfEntries.clear();
        mapOfListIteratorPtr.clear();
    }
};

缓存本身是一个链表。最新的元素位于列表的开头。最近最少使用的元素位于列表的末尾。使用哈希表以“随机访问”时间访问元素。

使用示例

char* HARD_DISK[] =
{
    "zero", "one", "two", "three", "four", 
    "five", "six", "seven", "eight", "nine", "ten"
};
class TestCache : public MruCache<int, char*>
{
public:
    TestCache(int iMaxLength) : MruCache<int, char*>(iMaxLength) { }
protected:
    virtual void HandleItemRelease(int key, char* value)
    {
        cout << "[DEBUG] key \"" << key 
             << "\" removed" << endl;
    }
    virtual char* HandleNonExistingKeyFetch(int key)
    {
        cout << "[DEBUG] key \"" 
             << key << "\" fetched" << endl;
        return HARD_DISK[key];
    }
};
int main()
{
    TestCache cache(4);
    cout << cache.FetchItem(1) << endl;
    cout << cache.FetchItem(2) << endl;
    cout << cache.FetchItem(3) << endl;
    cout << cache.FetchItem(4) << endl;
    cout << cache.FetchItem(5) << endl;
    // 1 is removed from the cache

    return 0;
}