An LRU cache template

I recently implemented a cache for a pet project of mine. The main objectives behind this implementation were:

1. Support move-only types for values: C++11 is here, and some of the objects that will be used with this template are movable but not copyable. Keys are fine with a copyable requirement because move-only keys make little sense in my opinion.

2. Fast key lookup.

3. Lazy evaluation: if the creation of the cached value type is an expensive operation, unnecessary creation is undesirable. Instead of creating the value directly and passing it along, I can simply pass a lambda or an existing factory function or function object, like this:

lru_cache<int,int> c;

4. Simple syntax when lazy evaluation is not needed: sometimes if an instance is available, or its creation is "free", using a lambda can be cumbersome. I'd rather just pass it directly:

c.get_or_add(17, 42); // int literals are "free", no need for laziness

Points 1 and 2 are achieved with a hash map of nodes in a linked list. The hash map gives fast lookup, and the linked list tracks the order of use. I tried to use Boost.Intrusive for the internal linked list, but its hooks don't have move semantics, so I had to roll my own :)

Points 3 and 4 are achieved through the meta::lazy<T>::eval function. It alone decides whether the argument is a function that is to be called or just a value to be returned.

Here is the code:

// for wheels::meta::lazy
#include "../meta/traits.hpp"

#include <functional>
#include <cstddef>
#include <type_traits>
#include <unordered_map>
#include <utility>

namespace wheels {
//! A cache that evicts the least recently used item.
template <typename Key,
typename T,
typename Hash = std::hash<Key>,
typename Pred = std::equal_to<Key>>
class lru_cache {
public:
//! Initializes an LRU cache with the given capacity.
lru_cache(std::size_t capacity) : front(), back(), map(), capacity(capacity) {}

//! Fetches an item from the cache, or adds one if it doesn't exist.
/*! The value parameter can be passed directly, or lazily (i.e. as a factory function). */
template <typename Lazy>
T& get_or_add(Key const& key, Lazy value) {
auto it = map.find(key);
if(it != map.end()) {
touch(it);
return it->second.value;
} else {
}
}

//! Flushes the cache evicting all entries.
void flush() {
front = back = nullptr;
map.clear();
}

private:
//! Moves a recently used entry to the front.
template <typename Iterator>
void touch(Iterator it) noexcept {
auto& entry = it->second;
unplug(entry);
push_front(entry);
}
template <typename Tf>
T& add(Key const& key, Tf&& value) {
cache_entry entry(key, std::forward<Tf>(value));
auto item = std::make_pair(key, std::move(entry));
auto it = map.insert(std::move(item)).first;
push_front(it->second);
if(map.size() > capacity) evict();
return it->second.value;
}
//! Evicts the least recently used entry.
void evict() {
map.erase(back->key);
unplug(*back);
}

//! An entry in the cache. Maintains a linked list to track the LRU.
struct cache_entry {
template <typename Tf>
cache_entry(Key const& key, Tf&& value)
: key(key), value(std::forward<Tf>(value)), next(), prev() {}

cache_entry(cache_entry&& that)
: key(std::move(that.key)), value(std::move(that.value)) {}

Key key;
T value;
cache_entry* next;
cache_entry* prev;
};

//! Unplugs an entry from the linked list.
void unplug(cache_entry& entry) {
if(entry.prev) {
entry.prev->next = entry.next;
} else {
front = entry.next;
}
if(entry.next) {
entry.next->prev = entry.prev;
} else {
back = entry.prev;
}
}
//! Pushes an entry to the front of the linked list.
void push_front(cache_entry& entry) {
entry.prev = nullptr;
entry.next = front;
if(front) {
front->prev = &entry;
} else {
back = &entry;
}
front = &entry;
}

cache_entry* front; //! Front of the internal linked list.
cache_entry* back; //! Back of the internal linked list.

//! Hash table for quick lookup by key.
std::unordered_map<Key,cache_entry, Hash> map;
//! Maximum capacity.
std::size_t capacity;
};
}

I'm particularly concerned about exception safety (which I've been a bit lax about, and it's something I'm still assimilating), but any criticism is welcome.

• Here's a nice article comparing two data structures: a) std::list and std::unordered_map and b) boost::bimap. Boost.MultiIndex also has an MRU example that should be easy to transform to LRU. Jan 26, 2014 at 16:22

I think you can make the maintenance of the list a lot easier if the list is circular.
With a circular list there are no test for NULL when inserting or removing an element (you just need a fake head node so that an empty list points back at itself).

Also you are not using encapsulation enough, this makes your methods a little more complex than they need to be. For example the cache_entry should be able to add and move itself around in the list.

Here is a simplified example of what I mean to try and show what I mean. Unfortunately there is no way I can implement the full template thing you have (way beyond me skill level).

The only worry I have for this technique is exception safety. There are no problems with this simplified version but I can quite convince myself this is true for your more complex cache. I would need to write the unit tests to make myself convinced.

#include <map>

class simple_cache
{
// The node(s) used to maintain the circular list.
{
// Links are created into a list.
: next(n)
, prev(p)
{}

// Remove a this from the list.
{
// Unlink this from the chain
prev->next      = next;
next->prev      = prev;
}

// Move a link to head of the list.
// But we do need to pass the head of the list.
{

// Put this node back into the chain at the head node

}

};
// A cache_entry is a link
// So we can add it to the circular list.
{
, key(key)
, value(value)
{
}

int         key;
int         value;
};
typedef std::map<int, cache_entry>      Data;
// If there are zero elements it points at itself
Data    data;
public:
simple_cache()
{}

{
Data::iterator  find    = data.find(key);
if (find != data.end())
{
find->second.value  = value;
}
else
{
if (data.size() > 5)
{
evict();
}
}
}
private:
void evict()
{
/* This function will explode if called when the list is empty
* i.e. if the only link in the chain is the fake node.
* Thus it is important to make sure that you only call this
* when their is a real node in the list.
*
* Maybe a check and exception may be worth it (though if done
* correctly it should be possible to make sure it does not happen)
*/

// Get and remove the last element from the list