LRU Cache @Leetcode

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.

Analysis: The major difference lies between this problem and the rest leetcode problems is this is all about OO design. It provides interface functions while we have to design the data structure and implement the functions to realize the LRU Cache. 

Basic Idea: Queue + Hashtable. In this place, Queue can be supported by double linked list. Hashtable enables O(1) iterating complexity. We can use list<> container in C++ as it works as double linked list and has defined API functions. We just need to define element struct type. 

PS:

1. Ways to open new nodes. malloc/free/C, new/delete/C++, cacheEntry tmp(key, value). 

http://stackoverflow.com/questions/240212/what-is-the-difference-between-new-delete-and-malloc-free

2. Ways to use unordered_map<type, type>. Pay attention we just need to give variable type but not variable names. #iterator#