缓存的数据结构采用哈希表，key到value的映射。

网上有些资料采用记录数据的使用时刻 实现LRU策略，此处采用双向链表 实现LRU策略。LRU Least Recently Used，MRUMost Recently Used

双向链表，lruPtr头指向最近最少使用的元素，mruPtr头指向最近最多使用的元素。

LRUCache tc(3); //最大三个元素
tc.insert(1, 101);
tc.insert(2, 102);
tc.insert(3, 103);

最终存储结构如下图：

哈希表中的元素：

lru.hpp

/*
* Implementation of an LRU cache with a maximum size.
*
* See http://code.google.com/p/lru-cache-cpp/ for usage and limitations.
*
* Licensed under the GNU LGPL: http://www.gnu.org/copyleft/lesser.html
*
* Pierre-Luc Brunelle, 2011
* pierre-luc.brunelle@polytml.ca
*
* 使用stl中的map替换hash_table
* Peteryfren China, 2012
*/

#include

namespace lru{

//-------------------------------------------------------------
// Bucket
//-------------------------------------------------------------

template
struct LRUCacheH4Value
{
typedef std::pair > Val;

LRUCacheH4Value()
: _v(), _older(NULL), _newer(NULL) { }

LRUCacheH4Value(const V & v, Val * older, Val * newer)
: _v(v), _older(older), _newer(newer) { }

V _v;
Val * _older;
Val * _newer;
};

//-------------------------------------------------------------
// Const Iterator
//-------------------------------------------------------------

template
class LRUCacheH4ConstIterator
{
public:
typedef std::pair > Val;
typedef LRUCacheH4ConstIterator const_iterator;
typedef Val & reference;
typedef Val * pointer;

enum DIRECTION {
MRU_TO_LRU = 0,
LRU_TO_MRU
};

LRUCacheH4ConstIterator(const Val * ptr = NULL, DIRECTION dir = MRU_TO_LRU);

const_iterator & operator++();
const_iterator operator++(int);

bool operator==(const const_iterator & other);
bool operator!=(const const_iterator & other);

const K & key() const;
const V & value() const;

private:
const Val * _ptr;
DIRECTION _dir;
};

template
LRUCacheH4ConstIterator::LRUCacheH4ConstIterator(
const typename LRUCacheH4ConstIterator::Val * ptr,
typename LRUCacheH4ConstIterator::DIRECTION dir)
: _ptr(ptr), _dir(dir)
{
}

template
LRUCacheH4ConstIterator & LRUCacheH4ConstIterator::operator++()
{
assert(_ptr);
_ptr = (_dir == LRUCacheH4ConstIterator::MRU_TO_LRU _ptr->second._older : _ptr->second._newer);
return *this;
}

template
LRUCacheH4ConstIterator LRUCacheH4ConstIterator::operator++(int)
{
const_iterator ret = *this;
++*this;
return ret;
}

template
bool LRUCacheH4ConstIterator::operator==(const const_iterator & other)
{
return _ptr == other._ptr;
}

template
bool LRUCacheH4ConstIterator::operator!=(const const_iterator & other)
{
return _ptr != other._ptr;
}

template
const K & LRUCacheH4ConstIterator::key() const
{
assert(_ptr);
return _ptr->first;
}

template
const V & LRUCacheH4ConstIterator::value() const
{
assert(_ptr);
return _ptr->second._v;
}

} // file scope

namespace lru {

//-------------------------------------------------------------
// LRU Cache
//-------------------------------------------------------------

template
class LRUCacheH4
{
public:
typedef LRUCacheH4ConstIterator const_iterator;

public:
LRUCacheH4(int maxsize); // Pre-condition: maxsize >= 1
LRUCacheH4(const LRUCacheH4 & other);
~LRUCacheH4() { _map.clear(); }

V & operator[](const K & key);
void insert(const K & key, const V & value);

int size() const;
int maxsize() const;
bool empty() const;