1.算法概述

LRU算法（Leaset Recently used），或者说缓存调度算法。对于软件层面实现的缓存来说，其主要针对的是对磁盘上具有结构性组织的大型文件数据的随机读取。如果程序需要从磁盘上某个存放了一亿条数据的文件中读取id=xxx的某条数据，并且这条数据会被多次访问到（很好的满足局部性原理），如果每次都是从磁盘上查询并读取，那么程序的性能将会非常的低。试想，如果我们在内存中维护一段能存储N条需要访问的数据段的缓存，并且以其id作为每个数据节点的键值。那么对于反复需要从磁盘文件中读取的某条数据就可以暂时存放在缓存中，当程序访问磁盘文件数据时就可以先在缓存中查找对应数据段的id（这种查询是可以达到o(1)的），如果找到那么直接从缓存读取这段数据，否则再从磁盘读取（另外一点需要的常识是对内存的访问要比磁盘快大约百万个数量级）。上面就是缓存的必要性，但是更细节的内容就涉及到缓存结构该如何设计。LRU算法正式这样的一种结构设计思想（最近访问的数据插入或置换到缓存队列越靠前的位置，优先淘汰队列最末尾的数据段）。

2.代码实现

#include<list>
#include<string>
#include<unordered_map>

template<class KeyType, class ValueType>
class LRUCache
{
public:
	LRUCache(int capacity) : m_capacity(capacity){}

	int get(KeyType key, ValueType &value)
	{
		if (m_map.count(key) <= 0)
		{
			return -1;
		}

		Iter iter = m_map[key];
		value = iter->second;

		m_list.splice(m_list.begin(), m_list, iter);

		return 0;
	}

	void put(KeyType key, ValueType value)
	{
		if (m_map.count(key) >= 1)
		{
			Iter iter = m_map[key];
			iter->second = value;
			m_list.splice(m_list.begin(), m_list, iter);
		}
		else
		{
			Node node(key, value);
			if (m_list.size() == m_capacity)
			{
				m_map.erase(m_list.back().first);
				m_list.pop_back();
			}

			m_list.push_front(node);
			m_map[key] = m_list.begin();
		}
	}

	void show(void(*p)(ValueType *))
	{
		typename std::list<Node>::iterator it;
		for (it = m_list.begin(); it != m_list.end(); it++)
		{
			p(&it->second);
		}
	}

private:
	typedef std::pair<KeyType, ValueType> Node;
	typedef typename std::list<Node>::iterator Iter;
	std::list<Node> m_list;
	std::unordered_map<KeyType, Iter> m_map;
	int m_capacity;
};


void show_func(int *a)
{
	printf("%dn", *a);
}

int main()
{
	int value;
	LRUCache<std::string, int> cache(5);
	cache.put("aaa", 1);
	cache.put("bbb", 2);
	cache.put("ccc", 3);
	cache.put("ddd", 4);
	cache.put("eee", 5);

	cache.show(show_func);

	cache.get("ccc", value);

	cache.show(show_func);

	cache.put("fff", 6);

	cache.show(show_func);

    return 0;
}