LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法。
实现思路： hashtable + 双向链表
时间复杂度： 插入，查找，删除：O（1）
空间使用情况： O（N） :一个链表存储K个数据（stl的hash_map实际占的空间比较大）。
运行环境：
linux:redhat , fedora ,centos等（理论上ubuntu , debian,mac os等也可以运行）
代码：
[cpp] view plaincopy
#ifndef __LRUCACHE_H__
#define __LRUCACHE_H__
#include
#include
#include
#include
using namespace __gnu_cxx;
template
struct Node{
K key;
D data;
Node *prev, *next;
};
template
class LRUCache{
public:
LRUCache（size_t size , bool is_pthread_safe = false）{
if（size <= 0）
size = 1024;
pthread_safe = is_pthread_safe;
if（pthread_safe）
pthread_mutex_init（&cached_mutex , NULL）；
entries = new Node[size];
for（size_t i = 0; i < size; ++i）
cached_entries.push_back（entries + i）；
head = new Node;
tail = new Node;
head->prev = NULL;
head->next = tail;
tail->prev = head;
tail->next = NULL;
}
~LRUCache（）{
if（pthread_safe）
pthread_mutex_destroy（&cached_mutex）；
delete head;
delete tail;
delete[] entries;
}
void Put（K key, D data）；
D Get（K key）；
private:
void cached_lock（void）{
if（pthread_safe）
pthread_mutex_lock（&cached_mutex）；
}
void cached_unlock（void）{
if（pthread_safe）
pthread_mutex_unlock（&cached_mutex）；
}
void detach（Node* node）{
node->prev->next = node->next;
node->next->prev = node->prev;
}
void attach（Node* node）{
node->prev = head;
node->next = head->next;
head->next = node;
node->next->prev = node;
}
private: