C++ template: Last Recently Used Cache

A last-recently-used cache implemented as a C++ template. Define the cache with the desired data and key type, then instantiate with the size. Items added or gotten are pushed towards the front (most recent) while those which have not been used in a while fall off the back as new items are added.

The cache is implemented via 2 STL structures, the first being a std::list of a std::pair of Data and Key, and the second structure being a std::map of Key and std::list iterator where the data is stored. The fact that the std::list contains a copy of the key may not be necessary, but makes dumping the cache for debug purposes convenient. A rather involved hierarchy of typedefs help ease the pain of using the data structures in the code.

/// @brief Typedef the cache item pair of 'data' and 'key' types.
typedef std::pair< Key, Data > Item;
/// @brief Typedef a list of Item(s).
typedef std::list< Item > Items;
/// @brief Typedef an iterator of the list of items.
typedef typename Items::iterator Items_iterator;
/// @brief Declare our cache to be a list of the Item(s).
Items m_Cache;
/// @brief Typedef an index of keys, and iterators to cache items.
typedef std::map< Key, Items_iterator > Index;
/// @brief Typedef an iterator to the index is helpful.
typedef typename Index::iterator Index_iterator;
/// @brief Typedef the insert to index result (iterator / bool pair).
typedef typename std::pair< Index_iterator, bool > Index_insert;
/// @brief An index instance.
Index m_Index;

Calling put(data,key) will add items to the cache.

/// @brief Put an item in the cache.
/// @note It is assumed that the key was searched for previously, and could
/// not be found, so the search is not done here.
/// @param[in] item The item that should be placed in the cache.
/// @param[in] key A key associated with the item.
/// @param True is returned if the item is added.
bool put( const Data &in, const Key &key ) {
    bool result = false;
    Items_iterator ix = m_Cache.insert( m_Cache.begin(), Item( key, in ) );
    Index_insert ii = m_Index.insert( 

        std::pair< Key, Items_iterator >( key, ix ) 

    );
    if ( !(result = ii.second) ) {
        m_Cache.erase( ix );
    } else {
        result = true;
        if ( m_Cache.size() > m_Size ) {
            Items_iterator ee = --m_Cache.end();
            if ( ee != m_Cache.end() ) {
                Index_iterator ii = m_Index.find( ee->first );
                m_Cache.erase( ee );
                if ( ii != m_Index.end() ) {
                    m_Index.erase( ii );
                }
            }
        }
    }
    return result;
}

And calling get(data,key) will return a copy if the cache has one.

/// @brief Get an item from the cache, if it exists.
/// @param[out] out Where the found item is copied to.
/// @param[in] key The key representing the item.
/// @return A true is returned if the item was in the cache.
bool get( Data &out, const Key &key ) {
    bool result = false;
    Index::iterator ii = m_Index.find( key );
    if ( ii != m_Index.end() ) {
        Items_iterator ix = ii->second;
        out = ix->second;
        m_Cache.splice( m_Cache.begin(), m_Cache, ix );
        result = true;
    }
    return result;
}

A link to the working (and tested) code can be found here: lru_cache.h Since I didn't give credit in the code for where I scrounged the idea, you don't either.