開發互聯網的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;
}