LeetCode Q:146 LRU Cache (hard)

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

	class LRUCache {
	public:
	LRUCache(int capacity) : _capacity(capacity) {}
	int get(int key) {
	auto it = cache.find(key);
	if (it == cache.end()) return -1;
	touch(it);
	return it->second.first;
	}
	void set(int key, int value) {
	auto it = cache.find(key);
	if (it != cache.end()) touch(it);
	else {
	if (cache.size() == _capacity) {
	cache.erase(used.back());
	used.pop_back();
	}
	used.push_front(key);
	}
	cache[key] = { value, used.begin() };
	}
	private:
	typedef list<int> LI;
	typedef pair<int, LI::iterator> PII;
	typedef unordered_map<int, PII> HIPII;
	void touch(HIPII::iterator it) {
	int key = it->first;
	used.erase(it->second.second);
	used.push_front(key);
	it->second.second = used.begin();
	}
	HIPII cache; // < key, <value, list<key>::iterator> >
	LI used; // list<key>
	int _capacity;
	};

view raw Q146LRU.cpp hosted with ❤ by GitHub

Round 2 solution:
The key here is to keep a list iterator in hash map. We save a pair in list because we need know what key it is when we remove a value from list. So we can remove this key from hash map.

	class LRUCache {
	public:
	list<pair<int, int> > myList;
	unordered_map<int, list<pair<int, int> >::iterator> myMap;
	int capacity;
	LRUCache(int _capacity) : capacity(_capacity) {}
	void touch(list<pair<int, int> >::iterator& it){
	pair<int, int> p = *(it);
	myList.erase(it);
	myList.push_front(p);
	it = myList.begin();
	}
	int get(int key) {
	auto it = myMap.find(key);
	if(it==myMap.end())
	return -1;
	touch(it->second);
	return (*(it->second)).first;
	}
	void set(int key, int value) {
	auto it = myMap.find(key);
	if(it!=myMap.end()){
	(*(it->second)).first=value;
	touch(it->second);
	}else{
	if(myList.size()==capacity){
	pair<int, int> back = myList.back();
	myList.pop_back();
	myMap.erase(back.second);
	}
	pair<int, int> newPair(value, key);
	myList.push_front(newPair);
	list<pair<int, int> >:: iterator newit = myList.begin();
	myMap[key] = newit;
	}
	}
	};

view raw Q146Rnd2.cpp hosted with ❤ by GitHub