C++实现LRU缓存算法

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算法。应该有一定的帮助的。