leveldb--2[LRUCache C++実装]

leveldbの実装を見ていると、小僧の蔵経閣にLRUCacheが言及され、本をめくってみると、メモリの普遍的な実装であることが分かった.
Cacheには、hitが一度にカウンタを+1にすることで、カバーする必要があり、countが最も少ないものを探すことができます.毎回ポーリングが必要で、効率が悪い.だからLRUCacheが出てきた
C++実装ここでは、C++でLRUCacheを実装する方法がよく実装されています.
私の下は一度写しただけです.はい、一度写しました.肝心なのは覚えておいてください.

//A simple LRUCache demo
//double linked list + hashmap
#include 
#include 
#include 
#include 

using namespace std;
using namespace __gnu_cxx;

template< class K, class T>
struct Node{
    K key;
    T value;
    Node *prev,*next;
};

template< class K, class T>
class LRUCache {
public:
    LRUCache(size_t size){
        entries_ = new Node[size];
        for(int i=0;i;
        tail_ = new Node;
        head_->prev = NULL;
        head_->next = tail_;
        tail_->prev = head_;
        tail_->next = NULL;
    }
    ~LRUCache(){
       delete head_;
       delete tail_;
       delete[] entries_;
    }
     T Get(K key){
        Node* node = hashmap_[key];
        if(node){
            detach(node);
            attach(node);
            return node->value;
        }
        else{
            return T();
        }
    }
    void Put(K key, T value){
        Node *node = hashmap_[key];
        if(node){//node exist
            detach(node);
            node->value = value;
            attach(node);
        }else{
            if(free_entries_.empty()){//cache full
                node = tail_->prev;
                detach(tail_->prev);
                hashmap_.erase(node->key);
            }else{
                //cache available
                node = free_entries_.back();
                free_entries_.pop_back();
            }
            node->key =  key;
            node->value = value;
            hashmap_[key] = node;
            attach(node);
        }
    }

private:
        Node *head_,*tail_;
        Node *entries_;
        hash_map* > hashmap_;
        vector* > free_entries_;

        void detach(Node* node){
            node->next->prev = node->prev;
            node->prev->next = node->next;
        }
        void attach(Node* node){
            node->prev = head_;
            node->next = head_->next;
            head_->next = node;
            head_->next->prev = node;
        }

};


int main(int argc, char* argv[]){
    hash_map map;
    map[9]= 999;
    cout<