I've written a cache class which implements a last-recently-used (LRU) cache. I would like to know what you think about it and whether it's worth using it or not (due to performance issues for instance).
#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 */
/* ------------------------------------------------------------------------------------- */
