LRU缓存 : 最近最少使用的缓存机制。规则：从容器get(key)：如果存在key，拿出之后这个键值对表示最常用；如果没有返回-1.
put(key,value)：如果容器未满，插入值后这对键值对是最常用；如果之前存在key则覆盖掉原来的值。如果容器已满，去掉最不常用的键值对再添加。

这里使用一个链表（list）和哈希表(unordered_map)实现，链表表示常用的顺序。因为我们首先要根据key从map中看是否已经存在，然后再调节该键值对在list中的常用顺序。所以map中必须存储list中对应键值对的地址：iterator。

 class LRUCache {
 public:
	 LRUCache(int capacity) {
		 cap = capacity;
	 }

	 int get(int key) {
		 auto it = m.find(key);
		 if (it == m.end()) return -1;
		 keys.splice(keys.begin(), keys, it->second);
		 return it->second->second;
	 }

	 void put(int key, int value) {
		 auto it = m.find(key);
		 if (it != m.end()) keys.erase(it->second);
		 keys.push_front(make_pair(key, value));
		 m[key] = keys.begin();
		 if (m.size() > cap)
		 {
			 int k = (keys.back()).first;
			 keys.pop_back();
			 m.erase(k);
		 }
	 }
 private:
	 int cap;
	 list<pair<int,int>> keys;
	 unordered_map<int, list<pair<int, int>>::iterator> m;
 };