All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
roboptim::LRUCache< K, V, H > Class Template Reference

LRU (Least Recently Used) cache. More...

#include <roboptim/core/fwd.hh>

Public Types

typedef K key_t
 Type of keys. More...
 
typedef detail::const_ref
< key_t >::type 
const_key_ref
 Type of const reference to key. More...
 
typedef V value_t
 Type of values. More...
 
typedef detail::const_ref
< value_t >::type 
const_value_ref
 Type of const reference to key. More...
 
typedef H hasher_t
 Hasher type. More...
 
typedef std::size_t hash_t
 Hash type used by the Boost map. More...
 
typedef
detail::aligned_vector_type
< value_t >::type 
valuePool_t
 Pool of values stored as std::vector. More...
 
typedef std::list< hash_tkeyTracker_t
 List used to track key usage. More...
 
typedef hash_t mapKey_t
 Key type for the underlying map. More...
 
typedef detail::const_ref
< mapKey_t >::type 
const_mapKey_ref
 
typedef boost::unordered_map
< mapKey_t, typename
valuePool_t::iterator > 
map_t
 Map from map's key to iterator in the value pool. More...
 
typedef map_t::const_iterator const_iterator
 
typedef map_t::iterator iterator
 

Public Member Functions

 LRUCache (size_t size=10)
 Constructor. More...
 
virtual ~LRUCache ()
 Destructor. More...
 
size_t size () const
 Size of the cache. More...
 
void resize (size_t size)
 Change the size of the cache. More...
 
const_iterator find (const_key_ref key) const
 Find an element in the cache. More...
 
iterator begin ()
 Iterator to the beginning of the cache. More...
 
iterator end ()
 Iterator to the end of the cache. More...
 
const_iterator cbegin () const
 Iterator to the beginning of the cache. More...
 
const_iterator cend () const
 Iterator to the end of the cache. More...
 
V & operator[] (const_key_ref key)
 Access a cached element. More...
 
void insert (const_key_ref key, const_value_ref value)
 Insert a value into the cache. More...
 
void clear ()
 Clear the cache. More...
 
virtual std::ostream & print (std::ostream &) const
 Display the cache on the specified output stream. More...
 

Protected Member Functions

hash_t hash_function (const_key_ref key) const
 Hash function used in the cache. More...
 

Detailed Description

template<typename K, typename V, typename H = boost::hash<K>>
class roboptim::LRUCache< K, V, H >

LRU (Least Recently Used) cache.

Note that the cache is unidirectional, i.e. the map does not store the actual keys, since this was designed with large vectors in mind.

Template Parameters
Ktype for keys.
Vtype for values.

Some of the ideas used here come from Tim Day's "LRU cache implementation in C++" (http://timday.bitbucket.org/lru.html)

Member Typedef Documentation

template<typename K, typename V, typename H = boost::hash<K>>
typedef map_t::const_iterator roboptim::LRUCache< K, V, H >::const_iterator
template<typename K, typename V, typename H = boost::hash<K>>
typedef detail::const_ref<key_t>::type roboptim::LRUCache< K, V, H >::const_key_ref

Type of const reference to key.

template<typename K, typename V, typename H = boost::hash<K>>
typedef detail::const_ref<mapKey_t>::type roboptim::LRUCache< K, V, H >::const_mapKey_ref
template<typename K, typename V, typename H = boost::hash<K>>
typedef detail::const_ref<value_t>::type roboptim::LRUCache< K, V, H >::const_value_ref

Type of const reference to key.

template<typename K, typename V, typename H = boost::hash<K>>
typedef std::size_t roboptim::LRUCache< K, V, H >::hash_t

Hash type used by the Boost map.

template<typename K, typename V, typename H = boost::hash<K>>
typedef H roboptim::LRUCache< K, V, H >::hasher_t

Hasher type.

template<typename K, typename V, typename H = boost::hash<K>>
typedef map_t::iterator roboptim::LRUCache< K, V, H >::iterator
template<typename K, typename V, typename H = boost::hash<K>>
typedef K roboptim::LRUCache< K, V, H >::key_t

Type of keys.

template<typename K, typename V, typename H = boost::hash<K>>
typedef std::list<hash_t> roboptim::LRUCache< K, V, H >::keyTracker_t

List used to track key usage.

Note: we use hashes rather than vectors to prevent costly allocations.

template<typename K, typename V, typename H = boost::hash<K>>
typedef boost::unordered_map<mapKey_t, typename valuePool_t::iterator> roboptim::LRUCache< K, V, H >::map_t

Map from map's key to iterator in the value pool.

template<typename K, typename V, typename H = boost::hash<K>>
typedef hash_t roboptim::LRUCache< K, V, H >::mapKey_t

Key type for the underlying map.

template<typename K, typename V, typename H = boost::hash<K>>
typedef V roboptim::LRUCache< K, V, H >::value_t

Type of values.

template<typename K, typename V, typename H = boost::hash<K>>
typedef detail::aligned_vector_type<value_t>::type roboptim::LRUCache< K, V, H >::valuePool_t

Pool of values stored as std::vector.

The container is properly aligned if an Eigen type is used.

Constructor & Destructor Documentation

template<typename K , typename V , typename H >
roboptim::LRUCache< K, V, H >::LRUCache ( size_t  size = 10)

Constructor.

Note: all the memory is allocated in the constructor.

Parameters
sizemaximum size of the cache.
template<typename K , typename V , typename H >
roboptim::LRUCache< K, V, H >::~LRUCache ( )
virtual

Destructor.

Member Function Documentation

template<typename K , typename V , typename H >
LRUCache< K, V, H >::iterator roboptim::LRUCache< K, V, H >::begin ( )

Iterator to the beginning of the cache.

template<typename K , typename V , typename H >
LRUCache< K, V, H >::const_iterator roboptim::LRUCache< K, V, H >::cbegin ( ) const

Iterator to the beginning of the cache.

template<typename K , typename V , typename H >
LRUCache< K, V, H >::const_iterator roboptim::LRUCache< K, V, H >::cend ( ) const

Iterator to the end of the cache.

template<typename K , typename V , typename H >
void roboptim::LRUCache< K, V, H >::clear ( )

Clear the cache.

template<typename K , typename V , typename H >
LRUCache< K, V, H >::iterator roboptim::LRUCache< K, V, H >::end ( )

Iterator to the end of the cache.

Referenced by roboptim::CachedFunction< T >::cachedFunctionJacobian().

template<typename K , typename V , typename H >
LRUCache< K, V, H >::const_iterator roboptim::LRUCache< K, V, H >::find ( const_key_ref  key) const
template<typename K , typename V , typename H >
LRUCache< K, V, H >::hash_t roboptim::LRUCache< K, V, H >::hash_function ( const_key_ref  key) const
protected

Hash function used in the cache.

Parameters
keykey to hash.
Returns
hashed key.
template<typename K , typename V , typename H >
void roboptim::LRUCache< K, V, H >::insert ( const_key_ref  key,
const_value_ref  value 
)

Insert a value into the cache.

Parameters
keykey of the element.
valuevalue of the element.
template<typename K , typename V , typename H >
V & roboptim::LRUCache< K, V, H >::operator[] ( const_key_ref  key)

Access a cached element.

Parameters
keykey to the element.
Returns
reference to the element.
template<typename K , typename V , typename H >
std::ostream & roboptim::LRUCache< K, V, H >::print ( std::ostream &  o) const
virtual

Display the cache on the specified output stream.

template<typename K , typename V , typename H >
void roboptim::LRUCache< K, V, H >::resize ( size_t  size)

Change the size of the cache.

template<typename K , typename V , typename H >
size_t roboptim::LRUCache< K, V, H >::size ( ) const

Size of the cache.