学步园

设计一个LRU cache, 如果想时间复杂度O(1), 则必须用到hash.

这里有一个使用STL实现的lru cache 模板类源码
LRU cache implementation in C++

http://timday.bitbucket.org/lru.html?1364610172

下面是自己随便写的一个lru测试程序, 逻辑验证正确.

#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <arpa/inet.h>
#include <sstream>
#include <vector>
#include <list>
#include <map>
#include <ext/hash_map>
#include <list>
#include <unistd.h> // for usleep

using namespace std;
using namespace __gnu_cxx;


#ifndef foreach
#define foreach(container,it) \
            for(typeof((container).begin()) it = (container).begin();it!=(container).end();++it)
#endif

struct DataValue
{
    string ss;
    int appid;
    string Info()
    {
        char buf[128];
        snprintf(buf, sizeof(buf), "[ss:%s, appid:%d]", ss.c_str(), appid);
        return buf;
    }
};

int MakeValue(int appid, DataValue& v)
{
    v.ss = "hello";
    v.appid = appid;
    return 0;
}

typedef int (*make_value_pt)(int, DataValue&);

class CLRU
{
public:
    CLRU(make_value_pt fn, int cache_size):
        _fn_make_value(fn),
        CACHE_SIZE(cache_size)
    {}

public:
    void get(int appid, DataValue& dv)
    {
        // 如果key已经存在, 把key移动到队tail
        if (key_map.find(appid) != key_map.end())
        {
            key_lru_list.splice(key_lru_list.end(), key_lru_list, key_map[appid].second);
            dv = key_map[appid].first;
        }
        // if not exiest
        else
        {
            // if cash size is full, evict
            if (key_lru_list.size() >= (unsigned int)CACHE_SIZE)
            {
                key_map.erase(key_lru_list.front());
                key_lru_list.erase(key_lru_list.begin());

            }

            // make a value for key
            _fn_make_value(appid, dv);

            // insert
            key_lru_list.push_back(appid);
            key_map[appid] = pair<DataValue, list<int>::iterator>(dv, --key_lru_list.end());
        }
    }

    // just for debug
    void output()
    {
        foreach(key_lru_list, it)
        {
            int appid = *it;
            printf("appid:%u, dv:%s\n", 
                    appid, key_map[appid].first.Info().c_str());
        }
    }

public:
    list<int>           key_lru_list;
    hash_map<int, pair<DataValue, list<int>::iterator> > key_map;

    make_value_pt       _fn_make_value;
    int                 CACHE_SIZE;
};

int main()
{
    CLRU lru(MakeValue, 3);
    DataValue dv;
    lru.get(1, dv);
    printf("dv:%s\n", dv.Info().c_str());
    lru.output();
    printf("----------\n");

    lru.get(2, dv);
    printf("dv:%s\n", dv.Info().c_str());
    lru.output();
    printf("----------\n");
   
    lru.get(3, dv);
    printf("dv:%s\n", dv.Info().c_str());
    lru.output();
    printf("----------\n");

    lru.get(4, dv);
    printf("dv:%s\n", dv.Info().c_str());
    lru.output();
    printf("----------\n");

    lru.get(3, dv);
    printf("dv:%s\n", dv.Info().c_str());
    lru.output();
    printf("----------\n");


    return 0;
}

输出如下:

dv:[ss:hello, appid:1]
appid:1, dv:[ss:hello, appid:1]
----------
dv:[ss:hello, appid:2]
appid:1, dv:[ss:hello, appid:1]
appid:2, dv:[ss:hello, appid:2]
----------
dv:[ss:hello, appid:3]
appid:1, dv:[ss:hello, appid:1]
appid:2, dv:[ss:hello, appid:2]
appid:3, dv:[ss:hello, appid:3]
----------
dv:[ss:hello, appid:4]
appid:2, dv:[ss:hello, appid:2]
appid:3, dv:[ss:hello, appid:3]
appid:4, dv:[ss:hello, appid:4]
----------
dv:[ss:hello, appid:3]
appid:2, dv:[ss:hello, appid:2]
appid:4, dv:[ss:hello, appid:4]
appid:3, dv:[ss:hello, appid:3]
----------