interview cache (mail.ru)

#ifndef LIBUTIL_LRU_CACHE_HPP__
#define LIBUTIL_LRU_CACHE_HPP__

#include <unordered_map>

namespace libutil
{

    template< class Tkey, class TItem >
    class LastUsedCache
    {
        struct record_t
        {
            TItem data;
            uint64_t gen;
        };



        typedef std::unordered_map< Tkey, record_t > cache_t;
        std::map<uint64_t, const Tkey* const> gen_to_key_;
        cache_t cache_;
        size_t max_size_;
        uint64_t generation_;

    public:
        LastUsedCache( size_t nelems )
        :   max_size_(nelems),
            generation_( 0 )
        {}


        bool find( Tkey key, TItem *item = NULL ) const
        {
            typename cache_t::const_iterator it = cache_.find( key );

            if (it == cache_.end())
                return false;
            else
            {
                if (item)
                    *item = it->second.data;
                return true;
            }
        }











        void insert( Tkey key, const TItem &data )
        {
            if (max_size_ != 0U)
            {
                record_t rec{ data, ++ generation_ };

                std::pair< typename cache_t::iterator, bool > result =
                    cache_.insert( typename cache_t::value_type( key, rec ) );

                if (result.second)
                {
                    if (cache_.size() > max_size_)
                    {
                        auto it = gen_to_key_.begin();
                        cache_.erase(*it->second);
                        gen_to_key_.erase(it);
                    }
                }
                else
                {
                    gen_to_key.erase(result.first->second.gen);
                    result.first->second = rec;
                    gen_to_key.emplace(result.first->second.gen, &result.first->first);
                }
            }
        }

        size_t size() const
        {
            return cache_.size();
        }

        bool empty() const
        {
            return (size() == 0);
        }

        void clear()
        {
            cache_.clear();
            gen_to_key_.clear();
            generation_ = 0;
        }
    };

} // namespace libutil

#endif LIBUTIL_LRU_CACHE_HPP__