Последний недавно использовавшихся (ЛРУ) контейнер кэш класса


Я написал класс Cache, который реализует последний-недавно использованные (ЛРУ) кэш. Я хотел бы знать, что вы об этом думаете и стоит ли использовать его или нет (из-за проблем с производительностью, например).

#include <functional>
#include <iterator>
#include <list>
#include <utility>
#include <unordered_map>

#include <boost/functional/hash.hpp>


class nop
{
public:
    void operator()(...) const volatile { }
}; /* class nop */
/* ------------------------------------------------------------------------------------- */

template<typename T>
class scale
    : public std::unary_function<T, std::size_t>
{
public:
    std::size_t operator()(T const&) const {
            return 1;
        }
}; /* template class scale */
/* ------------------------------------------------------------------------------------- */


template<typename key_type, typename T>
struct cache_traits
{
    typedef key_type                                               key_type;
    typedef T                                                      cached_type;
    typedef std::pair<key_type const, T>                           value_type;
    typedef value_type&                                            reference;
    typedef value_type const&                                      const_reference;
    typedef typename allocator_traits<value_type>::difference_type difference_type;
    typedef typename allocator_traits<value_type>::size_type       size_type;
    typedef typename allocator_traits<value_type>::pointer         pointer;
    typedef typename allocator_traits<value_type>::const_pointer   const_pointer;
}; /* template struct cache_traits */
/* ------------------------------------------------------------------------------------- */


/*********************************************************************************************************
 template class cache;
 *********************************************************************************************************/

template<
    typename key_type,
    typename T,
    class    drop     = nop<T>,
    class    hash     = boost::hash<key_type>,
    class    pred     = std::equal_to<key_type>,
    class    scale    = scale<T>,
    class    alloc    = std::allocator<std::pair<key_type const, T>>
>
class cache
    : public cache_traits<key_type, T>
{
public:
    typedef drop  drop_func;
    typedef hash  hasher;
    typedef pred  key_equal;
    typedef scale scale_func;
    typedef alloc allocator_type;
    /* --------------------------------------------------------------------------------- */

private:
    typedef std::list<value_type, alloc>                          storage_type;
    typedef typename storage_type::iterator                       storage_iterator;
    typedef typename storage_type::const_iterator                 const_storage_iterator;
    typedef std::pair<key_type const, storage_iterator>           index_pair;
    typedef std::unordered_map<key_type, storage_iterator, hash,
        pred, typename alloc::template rebind<index_pair>::other> index_type;
    typedef typename index_type::iterator                         index_iterator;
    typedef typename index_type::const_iterator                   const_index_iterator;
    /* --------------------------------------------------------------------------------- */

public:
    typedef storage_iterator                      iterator;
    typedef const_storage_iterator                const_iterator;
    typedef std::reverse_iterator<iterator>       reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    /* --------------------------------------------------------------------------------- */

    cache(cache const& other)
            : m_cur_size(other.m_cur_size), m_max_size(other.m_max_size),
              m_drop(other.m_drop), m_scale(other.m_scale),
              m_stg(other.m_stg), m_idx(other.m_idx) {
        }
    cache(cache const& other, alloc const& alloc)
            : m_cur_size(other.m_cur_size), m_max_size(other.m_max_size),
              m_drop(other.m_drop), m_scale(other.m_scale),
              m_stg(other.m_stg, alloc), m_idx(other.m_idx, alloc) {
        }
    cache(size_type n, alloc const& alloc)
            : m_cur_size(0), m_max_size(n),
              m_stg(alloc), m_idx(n, alloc) {
        }
    cache(size_type n = 0, drop const& df = drop(), hash const& hf = hash(), pred const& eq = pred(),
        scale const& sf = scale(), alloc const& alloc = alloc())
            : m_cur_size(0), m_max_size(n),
              m_drop(df), m_scale(sf),
              m_stg(alloc), m_idx(n, hf, eq, alloc) {
        }
    template<class input_iterator>
    cache(size_type n, input_iterator first, input_iterator last, drop const& df = drop(),
        hash const& hf = hash(), pred const& eq = pred(), scale const& sf = scale(),
        alloc const& alloc = alloc())
            : m_cur_size(0), m_max_size(n),
              m_drop(df), m_scale(sf),
              m_stg(alloc), m_idx(n, hf, eq, alloc)
        {
            insert(first, last);
        }
    virtual ~cache() {
        }
    cache& operator=(cache other)
        {
            swap(other);
            return *this;
        }
    alloc get_allocator() const {
            return this->m_stg.get_allocator();
        }
    /* --------------------------------------------------------------------------------- */


    // iterators:
    iterator begin() {
            return m_stg.begin();
        }
    const_iterator begin() const {
            return m_stg.begin();
        }
    iterator end() {
            return m_stg.end();
        }
    const_iterator end() const {
            return m_stg.end();
        }
    /* --------------------------------------------------------------------------------- */

    reverse_iterator rbegin() {
            return m_stg.rbegin();
        }
    const_reverse_iterator rbegin() const {
            return m_stg.rbegin();
        }
    reverse_iterator rend() {
            return m_stg.rend();
        }
    const_reverse_iterator rend() const {
            return m_stg.rend();
        }
    /* --------------------------------------------------------------------------------- */

    const_iterator cbegin() const {
            return m_stg.cbegin();
        }
    const_iterator cend() const {
            return m_stg.cend();
        }
    const_reverse_iterator crbegin() const {
            return m_stg.crbegin();
        }
    const_reverse_iterator crend() const {
            return m_stg.crend();
        }
    /* --------------------------------------------------------------------------------- */

    // capacity:
    bool empty() const {
            return size() == 0;
        }
    size_type max_size() const {
            return m_max_size;
        }
    void resize(size_type n)
        {
            m_max_size = n;
            adjust();
        }
    size_type size() const {
            return m_cur_size;
        }
    /* --------------------------------------------------------------------------------- */

    // element access:
    T& at(key_type const& key)
        {
            const_index_iterator pos = m_idx.find(key);
            if (pos != m_idx.end())
                return pos->second->second;
            throw std::out_of_range("cache::at() : no such element is present");
        }
    T const& at(key_type const& key) const {
            return const_cast<cache*>(this)->at(key);
        }
    iterator fetch(key_type const& key)
        {
            const_index_iterator pos = m_idx.find(key);
            if (pos != m_idx.end())
            {
                touch(pos->second);
                return pos->second;                
            }
            return end();
        }
    bool touch(key_type const& key)
        {
            const_index_iterator pos = m_idx.find(key);
            if (pos != m_idx.end())
            {
                touch(pos->second);
                return true;
            }
            return false;
        }
    /* --------------------------------------------------------------------------------- */

    // modifiers:
    std::pair<iterator, bool> insert(const_reference x)
        {
            if (m_idx.find(x.first) == m_idx.end())
            {
                iterator pos = add(x);
                return std::make_pair(pos, pos == end());
            }
            return std::make_pair(m_stg.end(), false);
        }
    template<class input_iterator> void insert(input_iterator first, input_iterator last)
        {
            for (; first != last; ++first) 
                store(*first);
        }
    size_type erase(key_type const& key)
        {
            const_index_iterator pos = m_idx.find(key);
            if (pos != m_idx.end())
            {
                remove(pos);   
                return 1;
            }
            return 0;
        }
    iterator erase(const_iterator pos)
        {
            const_index_iterator index_pos = m_idx.find(pos->first);
            if (index_pos != m_idx.end())
                return remove(index_pos);   
            return end();
        }
    iterator erase(const_iterator first, const_iterator last)
        {
            for (const_iterator i = first; i != last; ++i)
            {
                m_drop(i->second);
                m_cur_size -= m_scale(i->second);
                m_idx.erase(i->first);
            }
            return m_stg.erase(first, last);
        }
    void clear()
        {
            m_idx.clear();
            m_stg.clear();
            m_cur_size = 0;
        }
    void swap(cache& other)
        {
            using std::swap;

            swap(m_idx, other.m_idx);
            swap(m_stg, other.m_stg);
            swap(m_cur_size, other.m_cur_size);
            swap(m_max_size, other.m_max_size);
        }
    iterator store(const_reference x)
        {
            const_index_iterator pos = m_idx.find(x.first);
            if (pos != m_idx.end())
            {
                pos->second->second = x.second;
                touch(pos->second);
                return pos->second;
            }
            return add(x);
        }
    size_type exchange_key(key_type const& x, key_type const& y)
        {
            const_index_iterator xpos = m_idx.find(x);
            if (xpos != m_idx.end())
            {
                const_index_iterator ypos = m_idx.find(y);
                if (ypos != m_idx.end())
                {
                    swap(const_cast<key_type&>(xpos->second->first),
                        const_cast<key_type&>(ypos->second->first));

                    touch(xpos->second);
                    touch(ypos->second);
                    return 1;
                }
            }
            return 0;
        }
    size_type replace_key(key_type const& old_key, key_type const& new_key)
        {
            const_index_iterator pos = m_idx.find(old_key);
            if (pos != m_idx.end())
            {
                if (m_idx.insert(std::make_pair(new_key, pos->second)).second)
                {
                    const_cast<key_type&>(pos->second->first) = new_key;
                    touch(pos->second);
                    m_idx.erase(pos);
                    return 1;
                }
            }
            return 0;
        }
    /* --------------------------------------------------------------------------------- */

    // observers:
    drop drop_function() const {
            return m_drop;
        }
    hash hash_function() const {
            return m_idx.hash_function();
        }
    pred key_eq() const {
            return m_idx.key_eq();
        }
    scale scale_function() const {
            return m_scale;
        }
    /* --------------------------------------------------------------------------------- */

    // map operations:
    size_type count(key_type const& key) const {
            return m_idx.find(key) != this->m_idx.end() ? 1 : 0;
        }
    iterator find(key_type const& key)
        {
            const_index_iterator pos = m_idx.find(key);
            if (pos != m_idx.end())
                return pos->second;
            return end();
        }
    const_iterator find(key_type const& key) const {
            return const_cast<cache*>(this)->find(key);
        }
    /* --------------------------------------------------------------------------------- */

    iterator lower_bound(key_type const& key)
        {
            const_index_iterator lower_bound = m_idx.lower_bound(key);
            if (lower_bound != m_idx.end())
                return lower_bound->second;
            return end();
        }
    const_iterator lower_bound(key_type const& key) const {
            return const_cast<cache*>(this)->lower_bound(key);
        }
    iterator upper_bound(key_type const& key)
        {
            const_index_iterator upper_bound = m_idx.upper_bound(key);
            if (upper_bound != m_idx.end())
                return upper_bound->second;
            return end();
        }
    const_iterator upper_bound(key_type const& key) const {
            return const_cast<cache*>(this)->upper_bound(key);
        }
    /* --------------------------------------------------------------------------------- */

    std::pair<iterator, iterator> equal_range(key_type const& key)
        {
            const_index_iterator equal_range = m_idx.find(key);
            if (equal_range != m_idx.end())
                return std::make_pair(equal_range->second, equal_range->second);

            iterator end = end();
            return std::make_pair(end, end);
        }
    std::pair<const_iterator, const_iterator> equal_range(key_type const& key) const {
            return const_cast<cache*>(this)->equal_range(key);
        }
    /* --------------------------------------------------------------------------------- */

private:
    iterator add(const_reference x)
        {
            m_stg.push_front(x);
            iterator pos = m_stg.begin();

            size_type size = m_scale(pos->second);
            if (size <= m_max_size)
            {
                m_cur_size += size;
                m_idx[pos->first] = pos;
                adjust();
                return pos;
            }

            m_stg.erase(pos);
            return end();
        }
    void adjust()
        {
            while (m_cur_size > m_max_size)
                overflow();
        }
    void overflow() {
            erase(boost::prior(m_stg.end())->first);
        }
    iterator remove(const_index_iterator const& pos)
        {
            T const& x = pos->second->second;
            m_drop(x);
            m_cur_size -= m_scale(x);

            iterator next = m_stg.erase(pos->second);
            m_idx.erase(pos);
            return next;
        }
    void touch(const_storage_iterator const& pos) {
            m_stg.splice(m_stg.begin(), m_stg, pos);
        }
    /* --------------------------------------------------------------------------------- */

    drop  m_drop;
    scale m_scale;
    /* --------------------------------------------------------------------------------- */

    index_type   m_idx;
    storage_type m_stg;
    size_type    m_cur_size,
                 m_max_size;
    /* --------------------------------------------------------------------------------- */

    friend void swap(cache& x, cache& y) {
            x.swap(y);
        }
}; /* template class cache */
/* ------------------------------------------------------------------------------------- */


1075
8
задан 12 октября 2011 в 04:10 Источник Поделиться
Комментарии
2 ответа


  • Для один вещь, это не сработает, если m_idx содержит итераторы в m_stg:

    cache(cache const& other)
    : m_cur_size(other.m_cur_size), m_max_size(other.m_max_size),
    m_drop(other.m_drop), m_scale(other.m_scale),
    m_stg(other.m_stg), m_idx(other.m_idx) {

  • вы не можете перетасовать ключи unordered_mapтак:

    size_type exchange_key(key_type const& x, key_type const& y)
    {
    const_index_iterator xpos = m_idx.find(x);
    if (xpos != m_idx.end())
    {
    const_index_iterator ypos = m_idx.find(y);
    if (ypos != m_idx.end())
    {
    swap(const_cast<key_type&>(xpos->second->first),
    const_cast<key_type&>(ypos->second->first));

  • это может привести к УБ, когда переполнение() , к сожалению, удаляет поз.

    iterator add(const_reference x)
    {
    m_stg.push_front(x);
    iterator pos = m_stg.begin();

    size_type size = m_scale(pos->second);
    if (size <= m_max_size)
    {
    m_cur_size += size;
    m_idx[pos->first] = pos;
    adjust();
    return pos;
    }


  • Я был бы счастливее, если функции доступа не бросают исключений на недостающие данные, поскольку вы не можете реально контролировать, что есть, А чего нет в кэше. Возвращение ЭГ. импульс::опционально было бы уместно.

     // element access:
    T& at(key_type const& key)
    {
    const_index_iterator pos = m_idx.find(key);
    if (pos != m_idx.end())
    return pos->second->second;
    throw std::out_of_range("cache::at() : no such element is present");
    }

4
ответ дан 12 октября 2011 в 05:10 Источник Поделиться

На кэше пропустите вопрос конкретно: по моим наблюдениям, для большинства приложений из кэшей LRU, вместо того, кэш кидать или возврата пустой наддува::дополнительно на кэш Мисс, это более удобно для использования, если кэш знает, как вычислить недостающее значение (например.г путем предоставления ему объект функции, чтобы делать такие). Затем пользователь может просто использовать кэш, как будто он был более эффективным (при условии разумной доли попаданий в кэш) версии функции. Как memoisation функции, но с ограниченным размером.

Примеры такого типа кэш-интерфейс здесь (хотя значительно менее гибок чем твой).

Такой интерфейс может быть реализован как тонкая обертка вокруг класса конечно.

1
ответ дан 4 ноября 2011 в 09:11 Источник Поделиться