学步园

class LRUCache{
	public:
		int cap;
		typedef pair<int,int> node;
		typedef list<node>::iterator It;
		list<node> cache;
		map<int,It> cursor;

		LRUCache(int capacity) {
			cap=capacity;
		} 

		int get(int key) {
			if(cursor.find(key)!=cursor.end()) {
				It it=cursor[key];//cut it to the tail
				cache.splice(cache.end(),cache,it);
				cursor[key]=--cache.end();  //list::iterator don't support +/- n operation,so ERROR if cache.end()-1
				return (--cache.end())->second;
			}
			return -1;
		}
		void set(int key, int value) {
			if(cursor.find(key)==cursor.end()){//append new element to the tail
				cache.push_back(node(key,value));
				cursor[key]=--cache.end();
				if(cache.size()>cap) {//invalidate the head element
					int key=cache.begin()->first;
					cache.pop_front();
					cursor.erase(key);
				}
			}else{
				It it=cursor[key];//cut it to the tail
				cache.splice(cache.end(),cache,it); 
				cursor[key]=--cache.end();
				(--cache.end())->second=value;//set its value
			} 
		}
};