Implementation of LRU cache

Question

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 <map>
#include<iostream>
#include<assert.h>

template<class T>
struct Default {
  T value;
  Default():value(){}
};

template<class K, class V>
struct node {
  K key;
  V value;
  node<K,V>* next;
  node<K,V>* prev;
  explicit node(K key, V value);
};

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

template<class K, class V>
inline node<K,V>::node(K key, V value) {
  this->key = key;
  this->value = value;
}

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

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

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

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

Answer 1

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<class K, class V>
inline node<K, V>::node(K key, V value) {
    this->key = key;
    this->value = value;
}

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

template <class K, class V>
inline node<K, V>::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 <class K, class V>
inline node<K, V>::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<K, V>* temp = new node<K, V>(key, value);
temp->prev = nullptr;
temp->next = head;

...would become something like:

node<K, V> *temp = new node<K, V>(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.

Answer 2

Header guards

Your code contains undefined behaviour since the underscores are reserved for the implementation:

17.6.4.3 Reserved names [reserved.names]

The C++ standard library reserves the following kinds of names:

• macros
• global names
• names with external linkage

If a program declares or defines a name in a context where it is reserved, other than as explicitly allowed by this Clause, its behavior is undefined.

[…]

17.6.4.3.2 Global names [global.names]

Certain sets of names and function signatures are always reserved to the implementation:

• Each name that contains a double underscore __ or begins with an underscore followed by an uppercase letter (2.12) is reserved to the implementation for any use.

• Each name that begins with an underscore is reserved to the implementation for use as a name in the global namespace.

So rename __LRU_HPP__ to LEAST_RECENTLY_USED_HPP or similar.

Default

Instead of

return Default<V>().value;

use

return V{};

Unless you want to use Default<V> to provide specializations.

Possible bug

I'm rather sure you meant delete target, not delete tail.

  if(capacity == map.size()) {
    tail->prev->next = tail->next;
    node<K,V>* target = tail;
    map.erase(target->key);
    tail = tail->prev;
    delete tail;                     // << ?
  }

Otherwise you end up with a deleted, but not nulled tail.

Call-by-reference

Use const & for arguments if you're not going to change them afterwards.

Answer 3

• There is no reason for node to know the key.

• The node constructor shall make a completely created node, that is prev and next fields should be initialized as well (to nullptr).

• Member initializer lists are preferred to constructor bodies. For example,

      lru<K,V>::lru(std::size_t capacity)
          : capacity(capacity)
          , prev(nullptr)
          , next(nullptr) {
              assert(capacity > 1);
      }
  

• Returning a Default<V>.value() does not fit the purpose. At least it means that the client cannot put such a value. An idiomatic (i.e. STL) way is to make get to return an iterator, with failure being signaled by returning end iterator.

• The sequence in put:

  tail->prev->next = tail->next;
  ....
  tail = tail->prev;
  delete tail;
  

  is a definite bug, and has many grave consequences.

  Consider a rewrite:

  ....
  tail = tail->prev;
  delete tail->next;
  tail->next = nullptr;
  

• The reviewer immediately notices another "bug" in put - namely that the head is not updated - and it takes time and mental concentration to recall the capacity > 1 assertion, which makes the bug immaterial. I strongly recommend to factor the tail removal into a function with the name which reflects this fact. I suggest pop_back_unguarded or something along those lines.

• I don't think replace reflects what the function actually does. bump_up perhaps?