[iOS] LRU cache

SFLRUCache.hpp

#ifndef __sf_iOS_SFRLUCache_hpp_
#define __sf_iOS_SFRLUCache_hpp_

#include <unordered_map>
#include <utility>

namespace sf {

    // http://twitter.github.io/commons/apidocs/com/twitter/common/util/caching/LRUCache.html
    template<typename KeyT, typename ValT
        , class hash0 = std::hash<KeyT>
        , class pred0 = std::equal_to<KeyT>> class LRUCache
    {
        struct Link
        {
            Link *next = 0;
            Link *prev = 0;
            void unlink()
            {
                next->prev = prev;
                prev->next = next;
            }
            void insert(Link *link)
            {
                next = link->next;
                prev = link;
                next->prev = this;
                prev->next = this;
            }
        } head {&last, 0}, last {0, &head};
        struct Node: public Link
        {
            template<typename ...Args> Node(const KeyT &key, Args &&...args)
            :key(key)
            ,raw(std::forward<Args>(args)...)
            {
            }
            KeyT key;
            ValT raw;
        };
        struct Hash: public std::unary_function<const KeyT*, size_t>
        {
            inline size_t operator()(const KeyT *key) const { return hash0()(*key); }
        };
        struct Pred: public std::binary_function<const KeyT*, const KeyT*, bool>
        {
            inline bool operator()(const KeyT *a, const KeyT *b) const
            {
                return pred0()(*a, *b);
            }
        };
        using MapTy = std::unordered_map<const KeyT*, std::unique_ptr<Node>, Hash, Pred>;
    public:
        template<typename ...Args> void put(const KeyT &key, Args &&...args)
        {
            auto &e = nodes[&key];
            if (e) {
                e->raw = ValT(std::forward<Args>(args)...);
                e->unlink();
            }
            else {
                e.reset(new Node(key, std::forward<Args>(args)...));
            }
            e->insert(&head);
        }
        
        ValT *get(const KeyT &key, bool hit=true)
        {
            auto i = nodes.find(&key);
            if (i == nodes.end()) {
                return nullptr;
            }
            auto &e = i->second;
            if (hit) {
                e->unlink();
                e->insert(&head);
            }
            return &e->raw;
        }
        
        size_t size() const { return nodes.size(); }
        
        void pop_back()
        {
            if (nodes.empty()) {
                throw std::logic_error("No entry. (x_x)q");
            }
            auto e = static_cast<Node*>(last.prev);
            e->unlink();
            nodes.erase(&e->key);
        }
        
    private:
        MapTy nodes;
    };
    
} // namespace
#endif