LRU Cache

LRU.cpp

#include <iostream>
#include <ext/hash_map>
using namespace std;
using namespace __gnu_cxx;

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


template <class K, class T>
class LRUCache
{
public:
    LRUCache(int size) {
        count = 0;
        this->size = size;
        head_ = new Node<K,T>;
        tail_ = new Node<K,T>;
        head_->prev = NULL;
        head_->next = tail_;
        tail_->prev = head_;
        tail_->next = NULL;
        return;
    }
    
    ~LRUCache() {
        delete head_;
        delete tail_;
    }
    
    void put(K key, T data) {
        Node<K,T> *node = map_[key];
        if (node) {
            // node already exists
            detach(node);
            node->data = data;
            attach(node);
        }
        else {
            if (count == this->size) {
                // cache is full
                node = tail_->prev;
                detach(node);
                map_.erase(node->key);
                cout << "Cache is full, erase <" << node->key << ", " << node->data << ">" << endl;
            }
            else {
                node = new Node<K,T>;
                count++;
            }
            node->key = key;
            node->data = data;
            map_[key] = node;
            attach(node);
        }
    }
    
    T get(K key) {
        Node<K,T> *node = map_[key];
        if (node) {
            detach(node);
            attach(node);
            return node->data;
        }
        else {
            return T();
        }
    }
    
private:
    void detach(Node<K,T>* node){
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    
    void attach(Node<K,T>* node) {
        node->next = head_->next;
        node->next->prev = node;
        head_->next = node;
        node->prev = head_;
    }
    
    
private:
    int size, count;
    Node<K,T> *head_, *tail_;
    hash_map<K, Node<K,T>* > map_;
};


int main(int argc, char const *argv[]) {
    LRUCache<int, string> lru_cache(10);
    lru_cache.put(1, "one");
    lru_cache.put(2, "two");
    lru_cache.put(3, "three");
    string a = lru_cache.get(1);
    lru_cache.put(4, "four");
    cout << lru_cache.get(2) << endl;
    cout << lru_cache.get(3) << endl;
    return 0;
}