roboptim::LRUCache< K, V, H > Class Template Reference

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

#include <roboptim/core/cache.hh>

List of all members.

Public Types

typedef K key_t
 Type of keys.
typedef detail::const_ref
< key_t >::type 
const_key_ref
 Type of const reference to key.
typedef V value_t
 Type of values.
typedef detail::const_ref
< value_t >::type 
const_value_ref
 Type of const reference to key.
typedef H hasher_t
 Hasher type.
typedef std::size_t hash_t
 Hash type used by the Boost map.
typedef std::vector< value_tvaluePool_t
typedef std::list< hash_tkeyTracker_t
 List used to track key usage.
typedef hash_t mapKey_t
 Key type for the underlying map.
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.
typedef map_t::const_iterator const_iterator
typedef map_t::iterator iterator

Public Member Functions

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

Protected Member Functions

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

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 std::vector<value_t> roboptim::LRUCache< K, V, H >::valuePool_t

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.

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.

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines