An LRU cache template

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

-
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.

-
Fast key lookup.

-
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 c;
c.get_or_add(17, [&blah]{ return long_calculation(blah); });

-
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::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
#include
#include
#include
#include

namespace wheels {
//! A cache that evicts the least recently used item.
template ,
typename Pred = std::equal_to>
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.
/*!

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 

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

            // Remove a `this` from the list.
            void unlink()
            {
                // 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.
            void move(Link& head)
            {
                unlink();

                // Put this node back into the chain at the head node
                this->next      = &head;
                this->prev      = head.prev;

                head.prev->next = this;
                head.prev       = this;
            }

            Link*    next;
            Link*    prev;
        };
        // A cache_entry is a link
        // So we can add it to the circular list.
        struct cache_entry: public Link
        {
            // Create a link AND add it to the head of the list.
            cache_entry(int key, int value, Link& head)
                : Link(&head, head.prev)
                , key(key)
                , value(value)
            {
                head.prev->next = this;
                head.prev       = this;
            }

            int         key;
            int         value;
        };
        typedef std::map      Data;
        Link    head;   // Circular linked list
                        // If there are zero elements it points at itself
        Data    data;
    public:
        simple_cache() 
          : head(&head, &head)
        {}

        void add(int key, int value)
        {
            Data::iterator  find    = data.find(key);
            if (find != data.end())
            {
                find->second.value  = value;
                find->second.move(head);
            }
            else
            {
                data.insert(std::make_pair(key,cache_entry(key, value,head)));
                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
            Link*   lastElement = head.prev;
            lastElement->unlink();

            // Now remove it from the map.
            data.erase(static_cast(lastElement)->key);
        }

};

StackExchange Code Review Q#4806, answer score: 5