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 
  
   
#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: hash_map
             
              * > cached_map; vector
              
               * > cached_entries; Node
               
                 * head, *tail; Node
                
                  * entries; bool pthread_safe; pthread_mutex_t cached_mutex; }; template
                 
                   void LRUCache
                  
                   ::Put(K key , D data){ cached_lock(); Node
                   
                     *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
                    
                      D LRUCache
                     
                      ::Get(K key){ cached_lock(); Node
                      
                        *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 
  
   
#include 
   
     #include "LRUCache.h" using namespace std; int main(void){ //int k = 10 , // max = 100; int k = 100000 , max = 1000000; LRUCache
    
      * lru_cache = new LRUCache
     
      (k , true); int tmp = 0; for(int i = 0 ; i < 2*k ; ++i){ tmp = rand() % max; lru_cache->Put(tmp, tmp + 1000000); cout<
      
       Get(tmp) == 0) cout<<"miss : "<
       
        Get(tmp)<
         
         





 
         

 
 
         
其实，上面的代码，有一些毛病的。改天我会继续改进。
 
         
例如：
 
         
1：冗余操作。cached_entries完全可以用一个counter代替。
 
         
2：过度抽象。
 
         
3：Get、Put的interface不合理。如果真的去实现一个磁盘block的LRU cache，就会发现之前的接口需要重写了。
 
         

 
 
         
不过对于大家理解LRU算法。应该有一定的帮助的。