Last-recently-used (LRU) cache container class

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
#include
#include
#include
#include

#include

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

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

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

/*
template class cache;
*/

template,
class hash = boost::hash,
class pred = std::equal_to,
class scale = scale,
class alloc = std::allocator>
>
class cache
: public cache_traits
{
public:
typedef drop drop_func;

-
For one thing, this is not gonna work if m_idx contains iterators into 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) {

-
you cannot shuffle keys of unordered_maps like that:

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(xpos->second->first),
                    const_cast(ypos->second->first));

-
this may cause UB when overflow() unfortunately removes pos.

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

        size_type size = m_scale(pos->second);
        if (size first] = pos;
            adjust();
            return pos;
        }

-
I'd be happier if accessor functions hadn't thrown exceptions on missing data, since you can't really control what is and what isn't in the cache. A return of eg. boost::optional would be appropriate.

// 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");
    }

StackExchange Code Review Q#5324, answer score: 4