Implementing a LRU cache is not so easy. Here is my solution with the use of a priority queue and a hash table.
hint: look at the LRU implemented in the source code of Linux :D

   
struct Node
{
	Node(int k, int v) : key(k), value(v), prev(NULL), next(NULL)
		{
			
		}
	int key;
	int value;
	Node * prev;
	Node * next;
};

struct DoubleLinkedList
{
	Node * head;
	Node * last;

	DoubleLinkedList(): head(NULL), last(NULL)
		{
			
		}

	~DoubleLinkedList()
		{
			for(Node * tmp = head; tmp != NULL; tmp = tmp->next)
				delete tmp;
		}

	Node * InsertNode(int key, int value)
		{
			// Insert the node at the head of the list
			Node * newnode = new Node(key, value);
			newnode->next = head;
			if(head)
			{
				head->prev = newnode;
				head = newnode;
			}
			else
			{
				head = newnode;
				last = newnode;
			}

			return newnode;
		}

	void RemoveLastNode()
		{
			assert(last != NULL);
			Node * prevLastNode = last->prev;
			delete last;
			last = prevLastNode;
			if(last)
				last->next = NULL;
			else
				head = NULL;
		}

	int GetNode(Node * node)
		{
			if(node == head)
			{
				return node->value;
			}
			else
			{
				if(node == last)
				{
					node->next = head;
					head->prev = node;
					node->prev->next = NULL;
					last = node->prev;
					node->prev = NULL;
					head = node;
				}
				else
				{
					node->prev->next = node->next;
					node->next->prev = node->prev;
					node->next = head;
					head->prev = node;
					node->prev = NULL;
					head = node;
				}
				return head->value;
			}
		}
};

class LRUCache{
public:
	LRUCache(int capacity): m_CurrentSize(0), m_Capacity(capacity)
		{		
		}

	int get(int key)
		{
			if(m_Container.find(key) == m_Container.end())
				return -1;
			else
			{
				Node * n = m_Container[key];
				return priorityList.GetNode(n);
			}
		}

	void set(int key, int value)
		{
			if(m_Container.find(key) == m_Container.end())
			{
				// When the cache reachs its capacity, it should invalidate
				// the least recently used item before inserting a new
				if(m_CurrentSize == m_Capacity)
				{
					// Remove the key from the map
					m_Container.erase(priorityList.last->key);
					priorityList.RemoveLastNode();
					// Remove the corresponding key from the map
					m_Container[key] = priorityList.InsertNode(key, value);
				}
				else
				{
					m_Container[key] = priorityList.InsertNode(key, value);
					m_CurrentSize++;
				}
			}
		}

	int m_CurrentSize;
	int m_Capacity;
	DoubleLinkedList priorityList;
	std::unordered_map<int, Node *> m_Container;
};