LRU Cache Demo In C++

lru.cc

#include <iostream>
#include <string>
#include <map>
using namespace std;

struct entry {
    entry(string k, int v, entry *n, entry *p):
        key(k), value(v), next(n), prev(p){}
    string key;
    int value;
    entry *next;
    entry *prev;
};

struct hash_item {
    hash_item(string k, entry *p):
        key(k), ptr(p){}
    string key;
    entry *ptr;
};

class lru {
public:
    lru(int size):size_(size)
    {
    }

    entry *lookkup(string key)
    {
        map<string, hash_item>::iterator i = ht_.find(key);
        if (i != ht_.end()) {
            cerr << "Hited, item value: " << i->second.ptr->value << endl;
            // move it to the front of list
            entry *hit_entry =  i->second.ptr;
            entry *prev = hit_entry->prev;
            prev->next = hit_entry->next;
            prev->next->prev = prev;
            hit_entry->next = cache_;
            hit_entry->prev = NULL;
            cache_ = hit_entry;
        } else {
            // missed, update cache
            if ((int)ht_.size() == size_) {
                cerr << "Missed, cache full, repalce last item: " << last_->value << endl;
                entry *last_second = last_->prev;
                // delete old in hash table
                ht_.erase(last_->key);

                // delete old in list
                delete last_second->next;
                last_second->next = NULL;
                last_ = last_second;

                // add new in list
                entry *new_entry = new entry(key, rand(), NULL, NULL);
                cache_->prev = new_entry;
                new_entry->next = cache_;
                cache_ = new_entry;

                // add to hash table
                hash_item new_item(key, new_entry);
                ht_.insert(make_pair(key, new_item));
                return new_entry;

            } else {
                // insert new value
                entry *new_entry = new entry(key, rand(), NULL, NULL);
                cerr << "Missed, cache not full, insert new item: " << new_entry->value << endl;
                if (cache_ == NULL) {
                    last_ = new_entry;
                    cache_ = new_entry;
                } else {
                    cache_->prev = new_entry;
                    new_entry->next = cache_;
                    cache_ = new_entry;
                }

                hash_item new_item(key, new_entry);
                ht_.insert(make_pair(key, new_item));
                return new_entry;
            }
        }
    }
private:
    map<string, hash_item> ht_;
    entry *cache_;
    entry *last_;
    int size_;
};

int main( int argc, char **argv)
{
    lru ll(3);
    ll.lookkup("abcd");
    ll.lookkup("bcde");
    ll.lookkup("abcdef");
    /////// HIT
    ll.lookkup("abcd");

    /////// MISS
    ll.lookkup("abcdefdsr");
    ////// HIT
    ll.lookkup("abcdefdsr");

    return 0;
}