LeetCode——LRU Cache

set流程讲解：

1. 在map中查找key，如果找到，说明这个节点已经存在，那么将该节点的的位置排在链表头部；
2. 如果没找到，要进行第二个判断“是否已经达到了max_size”，如果已经达到了，将原来链表最后一个节点删除，然后将对应的map中的key-value删除，然后再加入新节点，并在map中加入对应的key-value，如果没有达到max-size，那么分配新地址给这个节点，同时加入到list和对应的map中。

class LRUCache {
public:
	LRUCache(int capacity) {
		_cache_map.clear();
		_cache_list.clear();
		_max_size = capacity;
	}

	int get(int key) {
		map<int, list<pair<int, int> >::iterator>::iterator p = _cache_map.find(
				key);
		if (p != _cache_map.end()) {
			_cache_list.splice(_cache_list.begin(), _cache_list, p->second);
			p->second = _cache_list.begin();
			return (p->second)->second;
		}
		return -1;
	}
	void set(int key, int value) {
		map<int, list<pair<int, int> >::iterator>::iterator p = _cache_map.find(
				key);
		//已经存在key
		if (p != _cache_map.end()) {
			((p->second))->second = value;
			_cache_list.splice(_cache_list.begin(), _cache_list, p->second);
			p->second = _cache_list.begin();
		} else {//key不存在
			if (_cache_map.size() >= _max_size) {//判断是否达到maxsize
				_cache_map.erase(_cache_list.rbegin()->first);
				_cache_list.pop_back();
			}
			_cache_list.push_front(pair<int, int>(key, value));
			_cache_map[key] = _cache_list.begin();
		}
	}
private:
	map<int, list<pair<int, int> >::iterator> _cache_map;
	list<pair<int, int> > _cache_list;
	int _max_size;
};

#include<iostream>
#include<list>
using namespace std;
int main() {
	list<int> mylist1, mylist2;
	list<int>::iterator it;
	// set some initial values:
	for (int i = 1; i <= 4; i++)
		mylist1.push_back(i);      // mylist1: 1 2 3 4
	for (int i = 1; i <= 3; i++)
		mylist2.push_back(i * 10);   // mylist2: 10 20 30
	it = mylist1.begin();
	++it;                         // points to 2
	mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4
								 // mylist2 (empty)
								 // "it" still points to 2 (the 5th element)

	mylist2.splice(mylist2.begin(), mylist1, it);
	// mylist1: 1 10 20 30 3 4
	// mylist2: 2
	// "it" is now invalid.
	it = mylist1.begin();
	advance(it, 3);                // "it" points now to 30
	mylist1.splice(mylist1.begin(), mylist1, it, mylist1.end());
	// mylist1: 30 3 4 1 10 20
	cout << "mylist1 contains:";
	for (it = mylist1.begin(); it != mylist1.end(); it++)
		cout << " " << *it;
	cout << "\nmylist2 contains:";
	for (it = mylist2.begin(); it != mylist2.end(); it++)
		cout << " " << *it;
	cout << endl;
	return 0;
}