注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Code@Pig Home

喜欢背着一袋Code傻笑的Pig .. 忧美.欢笑.记忆.忘却 .之. 角落

 
 
 

日志

 
 

[C++] 简单的 LRU  

2009-06-26 18:39:55|  分类: lang_c/c++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
呵呵,用 C++ 也把 lru 写了一遍。据某位同学说,非常 java-style,我也觉得~~ - -#

--------------------- lru.hpp ------------------
#ifndef MY_LRU_H
#define MY_LRU_H

#include <map>
#include <list>
#include <string>

class MyLruVal {
public:
        virtual ~MyLruVal() {}
        virtual void on_remove() = 0;   // called when removed from lru queue
};

class MyLru {
public:
        MyLru(size_t max_size) : _max_size(max_size) {}

        MyLruVal *get(std::string key);
        void put(std::string key, MyLruVal *val);

private:
        typedef std::map<std::string, MyLruVal *> KEY2IDX_MAP;
        typedef std::list<MyLruVal *> QUEUE_LIST;

        KEY2IDX_MAP _key2idx_map;
        QUEUE_LIST _queue;
        size_t _max_size;
};
#endif

----------------------- lru.cpp ----------------------
#include "lru.hpp"

MyLruVal *MyLru::get(std::string key)
{
        KEY2IDX_MAP::iterator itr;
        MyLruVal *val;

        itr = _key2idx_map.find(key);
        if ( itr == _key2idx_map.end() )
                return NULL;

        // make it to the first
        val = itr->second;
        _queue.remove(val);
        _queue.push_front(val);

        return val;
}

void MyLru::put(std::string key, MyLruVal *val)
{
        if ( _key2idx_map.find(key) != _key2idx_map.end() )
                return;

        if ( _queue.size() >= _max_size )
        {
                // remove last one
                MyLruVal *lastone = _queue.back();
                _queue.pop_back();

                lastone->on_remove();
        }

        _queue.push_front(val);
        _key2idx_map[key] = val;
}

-------------------- test.cpp ---------------------
#include <stdio.h>
#include "lru.hpp"

class TestVal : public MyLruVal {
public:
        TestVal(int n) : _val(n) {}
        virtual ~TestVal() {}
        virtual void on_remove() {
                printf("#%d, removed\n", _val);
        }

        int val() { return _val; }

private:
        int _val;
};

int main()
{
        MyLru lru(10);

        for ( int i = 0; i < 10; i++ )
        {
                char buf[80];
                sprintf(buf, "%d", i);

                printf("key = %s, val = %d\n", buf, i);
                lru.append(buf, new TestVal(i));
        }

        TestVal *v = dynamic_cast<TestVal*>(lru.get("0"));
        printf("#0 = %d\n", v->val());

        lru.append("11", new TestVal(11));

        return 0;
}
  评论这张
 
阅读(989)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017