开发互联网的server系统，难免会用一些cache机制，通常在Linux下多使用共享内存机制，把分配的内存组织成一个特定的数据结构，用来缓存后端DB的数据，加速读写。但是对一些新手而言，共享内存的使用还是有一些门槛，与此同时STL的使用却是相对容易上手，所以可以通过STL的容器组合出一个cache来。
上网搜了一下，看到已经有人做了一些类似的事情，具体可以参看http://bytes.com/forum/thread640146.html，作者采用STL::map（当然也可以是hash_map做数据缓存cache），采用一个list做lru链，每当读写cache中的数据时，都要在lru链中删除该key值对应的项，并把该数据的key值重新放到头部，这里面有个相对较慢的地方就是从lru链中删除key值对应的项的操作，因为删除操作表面看也仅是erase，但是其中也是顺序查找出来再删，相对耗时。可以针对此对之进行改进。
采用STL::map做lru链，map::first是一个“虚时间”，表示访问某一个key的虚时间，map::second就是key值，同样另外一个map做cache缓存数据，first为key，second为（value，virtual_time)对，这样当读写一个key的数据时，可以快速定位到该数据，并且可以查找到它的上次访问时间，从而在lru链里面快速定位（树上的查找终究要快）并删除，再更新key的访问时间并插入到lru链中就可以了。
当cache过大了，比如缓存最多100，那么就可以从lru链的头部开始淘汰了，（因为lru链first值越小，表示访问越久了）。代码贴在下面，欢迎批评指证。与上面文章里的相比，代码简化了给多，这样比较方便阅读，另外考虑到数据多是blob，所以cache中的value就采用stl::string了。
STL做cache的几个缺点：
1 由于cache的数据在堆栈中，所以server一旦core掉就丢了；
2 鉴于上述原因，所以这种cache适合“读多写少”的业务，一旦有“写入”操作，就和数据库同步更新，这样的话淘汰的时候也比较简单，直接丢掉就好了，不存在“脏数据”的概念。
当然，对于海量用户访问的业务，还是建议用共享内存做cache机制，这样读写的效率都会提高，并且程序出问题数据仍然在，但是坏处就是会带来复杂性和好多其它的问题，就不在这里说了。
#ifndef _MAP_LRU_CACHE_H_
#define _MAP_LRU_CACHE_H_
#include <string.h>
#include <iostream>
#include <list>
#include <map>
using namespace std;
namespace lru_cache {
static const int DEF_CAPACITY = 100000;
typedef unsigned long long virtual_time;
typedef struct _HashKey
{// key的类型自定义，重要的是要overload <和==
｝HashKey;
typedef struct _HashValue
{
string value_;
virtual_time access_;
}HashValue;
class CLRUCache
{
public:
CLRUCache() : _lru_list(), _hash_table(), _now(0){}
virtual ~CLRUCache(){}
int set( const HashKey& key, const string &value );
HashValue* get( const HashKey& key );
unsigned get_lru_list_size(){ return (unsigned)_lru_list.size(); }
unsigned get_hash_table_size() { return (unsigned)_hash_table.size(); }
virtual_time get_now() { return _now; }
private:
virtual_time get_virtual_time()
{
return ++_now;
}
map<virtual_time, HashKey> _lru_list;
map<HashKey, HashValue> _hash_table;
virtual_time _now;
};
}
#endif
#include "map_lru_cache.h"
using namespace lru_cache;
int CLRUCache::set( const HashKey& key, const string &value )
{
HashValue hash_value;
hash_value.value_ = value;
hash_value.access_ = get_virtual_time();
pair< map<HashKey, HashValue>::iterator, bool > ret = _hash_table.insert(make_pair(key, hash_value));
if ( !ret.second )
{
// key already exist
virtual_time old_access = _hash_table[key].access_;
map<virtual_time, HashKey>::iterator iter = _lru_list.find(old_access);
if(iter != _lru_list.end())
{
_lru_list.erase(iter);
}
_lru_list.insert(make_pair(hash_value.access_, key));
_hash_table[key] = hash_value;
}
else
{
_lru_list.insert(make_pair(hash_value.access_, key));
if ( _hash_table.size() > DEF_CAPACITY ) //ÌÔÌ
{
// get the least recently used key
map<virtual_time, HashKey>::iterator iter = _lru_list.begin();
_hash_table.erase( iter->second );
// remove last key from list
_lru_list.erase(iter);
}
}
return 0;
}
HashValue* CLRUCache::get( const HashKey& key )
{
map<HashKey, HashValue>::iterator iter = _hash_table.find(key);
if ( iter != _hash_table.end() )
{
virtual_time old_access = iter->second.access_;
iter->second.access_ = get_virtual_time();
map<virtual_time, HashKey>::iterator it = _lru_list.find(old_access);
if(it != _lru_list.end())
{
_lru_list.erase(it);
}
_lru_list.insert(make_pair(iter->second.access_, key));
return &(iter->second);
}
else
return NULL;
}