LRU缓存算法 - C++版

LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法。实现思路： hashtable + 双向链表时间复杂度：插入，查找，删除：O（1）空间使用情况： O（N）：一个链表存储K个数据（stl的hash_map实际占的空间比较大）.运行环境：Linux：RedHat ， Fedora ，CentOS等（理论上Ubuntu ， debian，mac os等也可以运行）代码：#ifndef __LRUCACHE_H__
#define __LRUCACHE_H__#include <vector>
#include <ext/hash_map>
#include <pthread.h>
#include <assert.h>using namespace __gnu_cxx;template <class K, class D>
struct Node{
K key;
D data;
Node *prev, *next;
};template <class K, class D>
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<K,D>[size];
for（size_t i = 0; i < size; ++i）
cached_entries.push_back（entries + i）; head = new Node<K,D>;
tail = new Node<K,D>;
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<K,D>* node）{
node->prev->next = node->next;
node->next->prev = node->prev;
}
void attach（Node<K,D>* node）{
node->prev = head;
node->next = head->next;
head->next = node;
node->next->prev = node;
}private:
hash_map<K, Node<K,D>* > cached_map;
vector<Node<K,D>* > cached_entries;
Node<K,D> * head, *tail;
Node<K,D> * entries;
bool pthread_safe;
pthread_mutex_t cached_mutex;
};template<class K , class D>
void LRUCache<K,D>::Put（K key , D data）{
cached_lock（）;
Node<K,D> *node = cached_map[key];
if（node）{
detach（node）;
node->data = data;
attach（node）;
}
else{
if（cached_entries.empty（））{
node = tail->prev;
detach（node）;
cached_map.erase（node->key）;
}
else{
node = cached_entries.back（）;
cached_entries.pop_back（）;
}
node->key = key;
node->data = data;
cached_map[key] = node;
attach（node）;
}
cached_unlock（）;
}template<class K , class D>
D LRUCache<K,D>::Get（K key）{
cached_lock（）;
Node<K,D> *node = cached_map[key];
if（node）{
detach（node）;
attach（node）;
cached_unlock（）;
return node->data;
}
else{
cached_unlock（）;
return D（）;
}
}#endif测试用例：/*
Compile:
g++ -o app app.cpp LRUCache.cpp -lpthread
Run:
./app
*/
#include <iostream>
#include <string>#include "LRUCache.h"using namespace std;int
main（void）{
//int k = 10 ,
// max = 100;
int k = 100000 ,
max = 1000000;
LRUCache<int , int> * lru_cache = new LRUCache<int , int>（k , true）;

int tmp = 0;
for（int i = 0 ; i < 2*k ; ++i）{
tmp = rand（） % max;
lru_cache->Put（tmp, tmp + 1000000）;
cout<<tmp<<endl;
} for（int i = 0 ; i < k ; ++i）{
tmp = rand（） % max;
if（lru_cache->Get（tmp） == 0）
cout<<"miss : "<<tmp<<endl;
else
cout<<"hit : "<<tmp<<" value : "<<lru_cache->Get（tmp）<<endl;
} delete lru_cache;
return 0;
}其实，上面的代码，有一些毛病的。改天我会继续改进。例如：1：冗余操作。cached_entries完全可以用一个counter代替。2：过度抽象。3：Get、Put的interface不合理。如果真的去实现一个磁盘block的LRU cache，就会发现之前的接口需要重写了。不过对于大家理解LRU算法。应该有一定的帮助的。