Implementation of LRU cache What do you think of this implementation of an LRU cache? I'm trying to migrate to modern C++, so it would be fantastic if you could give me any tips here. I've heard it's not desired to use raw pointers, right? What about only internally, as in the example? 

Also, since I can't return a nullptr value in the get() method, what is the best alternative for this? Default value as in the example?

#ifndef __LRU_HPP__
#define __LRU_HPP__
#include &lt;map&gt;
#include&lt;iostream&gt;
#include&lt;assert.h&gt;

template&lt;class T&gt;
struct Default {
  T value;
  Default():value(){}
};

template&lt;class K, class V&gt;
struct node {
  K key;
  V value;
  node&lt;K,V&gt;* next;
  node&lt;K,V&gt;* prev;
  explicit node(K key, V value);
};

template&lt;class K, class V&gt;
class lru {
private:
  node&lt;K,V&gt;* head;
  node&lt;K,V&gt;* tail;
  std::map&lt;K,node&lt;K,V&gt;*&gt; map;
  std::size_t capacity;
  void replace(node&lt;K,V&gt;*);
public:
  explicit lru(std::size_t);
  void put(K key, V value);
  V get(K key);
};

template&lt;class K, class V&gt;
inline node&lt;K,V&gt;::node(K key, V value) {
  this-&gt;key = key;
  this-&gt;value = value;
}

template&lt;class K, class V&gt;
inline lru&lt;K,V&gt;::lru(std::size_t capacity) {
  assert(capacity &gt; 1);
  this-&gt;capacity = capacity;
  this-&gt;head = tail = nullptr;
}

template&lt;class K, class V&gt;
void lru&lt;K,V&gt;::put(K key, V value) {
  auto it = map.find(key);
  if (it != map.end()) {
    node&lt;K,V&gt;* temp = it-&gt;second;
    temp-&gt;value = value;
    replace(temp);
    return;
  }
  if(capacity == map.size()) {
    tail-&gt;prev-&gt;next = tail-&gt;next;
    node&lt;K,V&gt;* target = tail;
    map.erase(target-&gt;key);
    tail = tail-&gt;prev;
    delete tail;
  }
  node&lt;K,V&gt;* temp = new node&lt;K,V&gt;(key, value);
  temp-&gt;prev = nullptr;
  temp-&gt;next = head;
  if(head != nullptr)
    head-&gt;prev = temp;
  else
    tail = temp;
  head = temp;
  map.insert(std::pair&lt;K,node&lt;K,V&gt;*&gt; {key, temp});
}

template&lt;class K, class V&gt;
V lru&lt;K,V&gt;::get(K key) {
  auto it = map.find(key);
  if(it != map.end()) {
    replace(it-&gt;second);
    return it-&gt;second-&gt;value;
  }
  return Default&lt;V&gt;().value;
}

template&lt;class K, class V&gt;
void lru&lt;K,V&gt;::replace(node&lt;K,V&gt;* temp) {
  if (temp-&gt;prev != nullptr)
    temp-&gt;prev-&gt;next = temp-&gt;next;
  if (temp-&gt;next != nullptr)
    temp-&gt;next-&gt;prev = temp-&gt;prev;
  if (tail == temp)
    tail = temp-&gt;prev != nullptr ? temp-&gt;prev : temp;
  if (head != temp) {
    head-&gt;prev = temp;
    temp-&gt;next = head;
    head = temp;
  }
}
#endif
Namespace Usage

I'd put all of this into some namespace, so it won't accidentally collide with other usage of the names it defines.

I'd probably also work even a little harder to do something to hide your node and Default templates. For example, node doesn't need to be visible to the outside world, so it would probably be better off defined inside of lru.

Prefer Initialization to Assignment

A constructor like this:

template&lt;class K, class V&gt;
inline node&lt;K, V&gt;::node(K key, V value) {
    this-&gt;key = key;
    this-&gt;value = value;
}


...is typically better written something like this instead:

template &lt;class K, class V&gt;
inline node&lt;K, V&gt;::node(K key, V value)
    : key(key)
    , value(value)
{}


In some cases, you must us initialization (like this) instead of assignment. In this case, it's not mandatory, but I still consider it preferable.

Consider passing by reference

Passing your keys and values by value generally requires copying. You might want to consider whether it's worth passing by reference instead. This generally accomplishes little (or nothing) if the type being passed is "small", but can improve speed substantially if the type is large.

Encapsulate knowledge of a type's internals in that type

Right now, your lru class "knows" (depends upon) the internals of the node class. I'd generally prefer if only node knew about its internals. For one possibility, you might pass a next and prev to the ctor, and let it put those values into the node itself:

template &lt;class K, class V&gt;
inline node&lt;K, V&gt;::node(K key, V value, node *prev = nullptr, node *next = nullptr)
    : key(key)
    , value(value)
    , prev(prev)
    , next(next)
{}


In this case, your code like this:

node&lt;K, V&gt;* temp = new node&lt;K, V&gt;(key, value);
temp-&gt;prev = nullptr;
temp-&gt;next = head;


...would become something like:

node&lt;K, V&gt; *temp = new node&lt;K, V&gt;(key, value, nullptr, head);


Consider other Data Structures

Although a doubly-linked list does work for the task at hand, it's often fairly wasteful, using a couple of pointers per node in addition to the data you actually care about storing.

I'd consider using a singly linked list instead. Although it may not immediately be obviously how you can do this, I'm reasonably certain you can.

Consider pre-allocating your storage

Given that the total maximum number of objects is fixed when you create the cache, I'd also consider pre-allocating storage for both the objects and the linked-list nodes when you create the cache. An allocator for a fixed-size set of fixed-size blocks can be really trivial, which can improve speed considerably over using a couple of allocations on the free store for every item you insert in the cache.