LRU缓存模板

Question

我最近为我的一个宠物项目实现了一个缓存。这项执行的主要目标是：

1. 支持仅移动类型的值: C++11在这里，与此模板一起使用的一些对象是可移动的，但不可复制。键与一个可复制的要求是好的，因为只移动键在我看来没有什么意义。
2. 快速查找键。
3. 惰性评估:如果缓存值类型的创建是一项昂贵的操作，则不必要的创建是不可取的。与直接创建值和传递值不同，我只需传递一个lambda或现有的工厂函数或函数对象，如: lru_cache c；c.get_or_add(17，&诸如此类{返回long_calculation(blah)；})；
4. 当不需要惰性计算时，使用简单的语法:有时，如果一个实例可用，或者它的创建是“免费的”，那么使用lambda可能会很麻烦。我宁愿直接传递它: c.get_or_add(17，42)；// int字是“免费”的，不需要懒惰

点1和2是通过链表中节点的散列映射来实现的。哈希映射提供快速查找，链接列表跟踪使用顺序。我试图对内部链接列表使用Boost.Intrusive，但是它的钩子没有移动语义，所以我不得不自己滚:)

第3和第4点是通过meta::lazy<T>::eval函数实现的。它单独决定参数是要调用的函数还是要返回的值。

以下是代码：

// 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 {
                return add(key, meta::lazy<T>::eval(value));
            }
        }

        //! 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);
        }
        //! Adds a new 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;
    };
}

我特别关心异常安全(我一直对此有些松懈，而且我还在吸收)，但任何批评都是受欢迎的。

Answer 1

如果列表是循环的，我认为您可以使列表的维护变得更容易。

对于循环列表，在插入或删除元素时没有对NULL的测试(您只需要一个假的head节点，这样空列表就会指向它自己)。

此外，您还没有足够地使用封装，这使得您的方法比它们所需要的要复杂一些。例如，cache_entry应该能够在列表中添加和移动自己。

这里是一个简单的例子，说明了我的意思，并试图展示我的意思。不幸的是，我无法实现您拥有的完整模板(远远超出了我的技能水平)。

我对这一技术唯一的担心是异常安全。这个简化版本没有问题，但我可以说服自己，这对于您更复杂的缓存是正确的。我需要写单元测试才能让自己信服。

#include <map>

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<int, cache_entry>      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<cache_entry*>(lastElement)->key);
        }

};