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.

采用单链表，并通过STL库的map来提高搜索速度。

class LRUCache

{

public:

  LRUCache(int capacity)

  {

    capacity_ = capacity;

	length_ = 0;

	list_ = NULL;

  }

  ~LRUCache(){ Destroy();}

  int get(int key);

  void set(int key, int value);

  void Print();

private:

  struct ListNode

  {

    int key;

    int value;

    struct ListNode *next;

	struct ListNode *pre;

    ListNode(int k=-1,int val=-1, struct ListNode *p=NULL)

      : key(k), value(val), next(p), pre(p){}

  };

  typedef struct ListNode ListNode;

  void Destroy();

  void Delete(ListNode *node);

  void DeleteRear();

  ListNode* Find(int key);

  ListNode* InsertFront(int key, int value);

  int length_;

  int capacity_;

  ListNode *list_;

  map<int, ListNode*> map_;

};

//value is positive

//if not found, return -1

int LRUCache::get(int key)

{

  int x;

  ListNode *node(NULL);

  if(map_.count(key))

  {

	node = map_.find(key)->second;

	Delete(node);//do not free space

	node->next = list_;

	list_ = node;

    return node->value;

  }

  else return -1;

}

//if full, delete the least used, and insert into the head

void LRUCache::set(int key, int value)

{

  ListNode *node(NULL);

  if(map_.count(key))

  { //already in the list

    node = map_.find(key)->second;

    Delete(node);

	node->value = value;

	node->next = list_;

	list_ = node;

  }

  else

  { //not found

    node = InsertFront(key, value);

	map_[key] = node;

	if(length_ >= capacity_)

	  DeleteRear();

	else

	  length_++;

  }

}

//return pointer to the node containing key

//if not found, return NULL

typename LRUCache::ListNode* LRUCache::Find(int key)

{

  ListNode *list(list_);

  while(list && list->key != key)

    list = list->next;

  return (list!=NULL) ? list:NULL;

}

//destroy singlely-linked list

void LRUCache::Destroy()

{

  ListNode *pre(NULL);

  while(list_)

  {

    pre = list_;

	list_ = list_->next;

	delete pre;

  }

  map_.clear();

}

void LRUCache::Delete(ListNode *node)

{ // do not free space

  assert(node != NULL);

  ListNode *pre(NULL), *cur(list_);

  while(cur != node)

  {

    pre = cur;

	cur = cur->next;

  }

  assert(cur == node);

  if(pre == NULL)

    list_ = node->next;

  else

    pre->next = cur->next;

}

void LRUCache::DeleteRear()

{

  if(list_ == NULL) return;

  ListNode *cur(list_), *pre(NULL);

  while(cur->next)

  {

    pre = cur;

	cur = cur->next;

  }

  if(pre == NULL)

    list_ = cur->next;

  else

    pre->next = cur->next;

  map<int, ListNode*>::iterator it = map_.find(cur->key);

  map_.erase(it);

  delete cur;

}

LRUCache::ListNode* LRUCache::InsertFront(int key, int val)

{

  ListNode *node = new ListNode(key, val, list_);

  list_ = node;

  return node;

}