A simple LRU cache.

LRU.hpp

#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;

template <typename K, typename V>
struct LRUNode {
	K key;
	V value;
	LRUNode *prev, *next;
};

template <typename K, typename V>
class LRUCache {
public:
	typedef LRUNode<K, V> node_t;
	LRUCache(size_t size) {
		entries.resize(size);
		for(auto& x:entries) {
			free_entries.push_back(&x);
		}

		head = new node_t();
		tail = new node_t();
		head->prev = nullptr;
		head->next = tail;
		tail->prev = head;
		tail->next = nullptr;
	}

	~LRUCache() {
		delete head;
		delete tail;
	}

	void Put(K key, V value) {
		auto nit = nodemap.find(key); 
		if( nit != nodemap.end() ) {
			// node exists
			node_t* node = nit->second;
			detach(node);
			node->value = value;
			attach(node);
		}
		else {
			node_t* node;
			if( free_entries.empty() ) {
				// cache is full
				node = tail->prev;
				detach(node);
				nodemap.erase(node->key);
			}
			else {
				node = free_entries.back();
				free_entries.pop_back();
			}

			node->key = key;
			node->value = value;
			nodemap[key] = node;
			attach(node);
		}
	}

	V Get(K key) {
		auto nit = nodemap.find(key);
		if( nit == nodemap.end() ) {
			return V();
		}
		else {
			node_t* node = nit->second;
			detach(node);
			attach(node);
			return node->value;
		}
	}

	template <typename KT, typename VT>
	friend ostream& operator<<(ostream& os, const LRUCache<KT, VT> &lru);
private:
	void detach(node_t* node) {
		node->prev->next = node->next;
		node->next->prev = node->prev;
	}

	void attach(node_t* node) {
		node->prev = head;
		node->next = head->next;

		head->next->prev = node;
		head->next = node;
	}
private:
	unordered_map<K, node_t*> nodemap;
	vector<node_t*> free_entries;
	vector<node_t> entries;
	node_t *head, *tail;
};

template <typename K, typename V>
ostream& operator<<(ostream& os, const LRUCache<K, V> &lru) {
	typename LRUCache<K,V>::node_t *n = lru.head->next;
	while( n != nullptr ) {
		os << n->value << ' ';
		n = n->next;
	}
	return os;
}