LRU是Least Recently Used的缩写，即最近最少使用（最近一段时间最少使用），是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。
最近不是空间的概念，是时间概念，即最近一段时间。
1、最开始时，内存空间是空的，因此依次进入A、B、C是没有问题的
2、当加入D时，就出现了问题，内存空间不够了，因此根据LRU算法，内存空间中A待的时间最为久远，选择A,将其淘汰
3、当再次引用B时，内存空间中的B又处于活跃状态，而C则变成了内存空间中，近段时间最久未使用的
4、当再次向内存空间加入E时，这时内存空间又不足了，选择在内存空间中待的最久的C将其淘汰出内存，这时的内存空间存放的对象就是E->B->D
算法实现：
LRUCache通过一个list列表和一个map表实现读写功能，list表存放key，map表存放key、value、list表对应的位置信息，list表负责构造最近最少使用列表，新增加或新使用的元素放在列表最后，map表负责快速查找。
/**
* Least-recently-used cache class.
* K = key type, T = value type
*
* usage:
* LRUCache<K,T> cache;
* cache.put( key, value );
* LRUCache.Record rec = cache.get( key );
* if ( rec.valid() )
* const T& value = rec.value();
*/
template<typename K, typename T, typename COMPARE=std::less<K> >
class LRUCache
{
public:
struct Record {
Record() : _valid(false) { }
Record(const T& value) : _value(value), _valid(true) { }
bool valid() const { return _valid; }
const T& value() const { return _value; }
private:
bool _valid;
T _value;
friend class LRUCache;
};
struct Functor {
virtual void operator()(const K& key, const T& value) =0;
};
protected:
typedef typename std::list<K>::iterator lru_iter;
typedef typename std::list<K> lru_type;
typedef typename std::pair<T, lru_iter> map_value_type;
typedef typename std::map<K, map_value_type> map_type;
typedef typename map_type::iterator map_iter;
typedef typename map_type::const_iterator map_const_iter;
map_type _map;
lru_type _lru;
unsigned _max;
unsigned _buf;
unsigned _queries;
unsigned _hits;
bool _threadsafe;
mutable Threading::Mutex _mutex;
public:
LRUCache( unsigned max =100 ) : _max(max), _threadsafe(false) {
_queries = 0;
_hits = 0;
setMaxSize_impl(max);
}
LRUCache( bool threadsafe, unsigned max =100 ) : _max(max), _threadsafe(threadsafe) {
_queries = 0;
_hits = 0;
setMaxSize_impl(max);
}
/** dtor */
virtual ~LRUCache() { }
void insert( const K& key, const T& value ) {
if ( _threadsafe ) {
Threading::ScopedMutexLock lock(_mutex);
insert_impl( key, value );
}
else {
insert_impl( key, value );
}
}
bool get( const K& key, Record& out ) {
if ( _threadsafe ) {
Threading::ScopedMutexLock lock(_mutex);
get_impl( key, out );
}
else {
get_impl( key, out );
}
return out.valid();
}
bool has( const K& key ) {
if ( _threadsafe ) {
Threading::ScopedMutexLock lock(_mutex);
return has_impl( key );
}
else {
return has_impl( key );
}
}
void erase( const K& key ) {
if ( _threadsafe ) {
Threading::ScopedMutexLock lock(_mutex);
erase_impl( key );
}
else {
erase_impl( key );
}
}
void clear() {
if ( _threadsafe ) {
Threading::ScopedMutexLock lock(_mutex);
clear_impl();
}
else {
clear_impl();
}
}
void setMaxSize( unsigned max ) {
if ( _threadsafe ) {
Threading::ScopedMutexLock lock(_mutex);
setMaxSize_impl( max );
}
else {
setMaxSize_impl( max );
}
}
unsigned getMaxSize() const {
return _max;
}
CacheStats getStats() const {
return CacheStats(
_map.size(), _max, _queries, _queries > 0 ? (float)_hits/(float)_queries : 0.0f );
}
void iterate(Functor& functor) const {
if (_threadsafe) {
Threading::ScopedMutexLock lock(_mutex);
iterate_impl(functor);
}
else {
iterate_impl(functor);
}
}
private:
void insert_impl( const K& key, const T& value ) {
map_iter mi = _map.find( key );
if ( mi != _map.end() ) {
_lru.erase( mi->second.second );
mi->second.first = value;
_lru.push_back( key );
mi->second.second = _lru.end();
mi->second.second--;
}
else {
_lru.push_back( key );
lru_iter last = _lru.end(); last--;
_map[key] = std::make_pair(value, last);
}
if ( _map.size() > _max ) {
for( unsigned i=0; i < _buf; ++i ) {
const K& key = _lru.front();
_map.erase( key );
_lru.pop_front();
}
}
}
void get_impl( const K& key, Record& result ) {
_queries++;
map_iter mi = _map.find( key );
if ( mi != _map.end() ) {
_lru.erase( mi->second.second );
_lru.push_back( key );
lru_iter new_iter = _lru.end(); new_iter--;
mi->second.second = new_iter;
_hits++;
result._value = mi->second.first;
result._valid = true;
}
}
bool has_impl( const K& key ) {
return _map.find( key ) != _map.end();
}
void erase_impl( const K& key ) {
map_iter mi = _map.find( key );
if ( mi != _map.end() ) {
_lru.erase( mi->second.second );
_map.erase( mi );
}
}
void clear_impl() {
_lru.clear();
_map.clear();
_queries = 0;
_hits = 0;
}
void setMaxSize_impl( unsigned max ) {
_max = std::max(max,10u);
_buf = _max/10u;
while( _map.size() > _max ) {
const K& key = _lru.front();
_map.erase( key );
_lru.pop_front();
}
}
void iterate_impl(Functor& f) const {
for (map_const_iter i = _map.begin(); i != _map.end(); ++i) {
f(i->first, i->second.first);
}
}
};