cxxtools::Cache< Key, Value > Class Template Reference

Implements a container for caching elements. More...

#include <cxxtools/cache.h>

Classes

struct  Data

Public Types

typedef DataType::size_type size_type
typedef Value value_type

Public Member Functions

 Cache (size_type maxElements_)
size_type size () const
 returns the number of elements currently in the cache
size_type getMaxElements () const
 returns the maximum number of elements in the cache
void setMaxElements (size_type maxElements_)
bool erase (const Key &key)
 removes a element from the cache and returns true, if found
void clear (bool stats=false)
 clears the cache.
Value & put (const Key &key, const Value &value)
 puts a new element in the cache.
void put_top (const Key &key, const Value &value)
 puts a new element on the top of the cache.
Value * getptr (const Key &key)
std::pair< bool, Value > getx (const Key &key, Value def=Value())
 returns a pair of values - a flag, if the value was found and the value if found or the passed default otherwise.
Value get (const Key &key, Value def=Value())
 returns the value to a key or the passed default value if not found.
unsigned getHits () const
 returns the number of hits.
unsigned getMisses () const
 returns the number of misses.
double hitRatio () const
 returns the cache hit ratio between 0 and 1.
double fillfactor () const
 returns the ratio, between held elements and maximum elements.
unsigned winners () const
unsigned loosers () const

Detailed Description

template<typename Key, typename Value>
class cxxtools::Cache< Key, Value >

Implements a container for caching elements.

The cache holds a list of key-value-pairs. There are 2 main operations for accessing the cache: put and get. Put takes a key and a value and puts the element into the list. Get takes a key and optional a value. If the value for the key is found, it is returned. The passed value otherwise. By default the value is constructed with the empty ctor of the value-type.

The cache has a maximum size, after which key-value-pairs are dropped, when a new item is put into the cache.

The algorithm for this cache is as follows:

  • when the cache is not full, new elements are appended
  • new elements are put into the middle of the list otherwise
  • the last element of the list is then dropped
  • when getting a value and the value is found, it is put to the beginning of the list

When elements are searched, a linear search is done using the ==-operator of the key type.

The caching algorithm keeps elements, which are fetched more than once in the first half of the list. In the second half the elements are either new or the elements are pushed from the first half to the second half by other elements, which are found in the cache.

You should be aware, that the key type should be simple. Comparing keys must be cheap. Copying elements (both key and value) must be possible and should be cheap, since they are moved in the underlying container.

Member Typedef Documentation

template<typename Key , typename Value >
typedef DataType::size_type cxxtools::Cache< Key, Value >::size_type
template<typename Key , typename Value >
typedef Value cxxtools::Cache< Key, Value >::value_type

Constructor & Destructor Documentation

template<typename Key , typename Value >
cxxtools::Cache< Key, Value >::Cache ( size_type  maxElements_)
inlineexplicit

Member Function Documentation

template<typename Key , typename Value >
void cxxtools::Cache< Key, Value >::clear ( bool  stats = false)
inline

clears the cache.

template<typename Key , typename Value >
bool cxxtools::Cache< Key, Value >::erase ( const Key &  key)
inline

removes a element from the cache and returns true, if found

template<typename Key , typename Value >
double cxxtools::Cache< Key, Value >::fillfactor ( ) const
inline

returns the ratio, between held elements and maximum elements.

template<typename Key , typename Value >
Value cxxtools::Cache< Key, Value >::get ( const Key &  key,
Value  def = Value() 
)
inline

returns the value to a key or the passed default value if not found.

If the value is found it is a cahce hit and pushed to the top of the list.

template<typename Key , typename Value >
unsigned cxxtools::Cache< Key, Value >::getHits ( ) const
inline

returns the number of hits.

template<typename Key , typename Value >
size_type cxxtools::Cache< Key, Value >::getMaxElements ( ) const
inline

returns the maximum number of elements in the cache

template<typename Key , typename Value >
unsigned cxxtools::Cache< Key, Value >::getMisses ( ) const
inline

returns the number of misses.

template<typename Key , typename Value >
Value* cxxtools::Cache< Key, Value >::getptr ( const Key &  key)
inline
template<typename Key , typename Value >
std::pair<bool, Value> cxxtools::Cache< Key, Value >::getx ( const Key &  key,
Value  def = Value() 
)
inline

returns a pair of values - a flag, if the value was found and the value if found or the passed default otherwise.

If the value is found it is a cache hit and pushed to the top of the list.

template<typename Key , typename Value >
double cxxtools::Cache< Key, Value >::hitRatio ( ) const
inline

returns the cache hit ratio between 0 and 1.

template<typename Key , typename Value >
unsigned cxxtools::Cache< Key, Value >::loosers ( ) const
inline
template<typename Key , typename Value >
Value& cxxtools::Cache< Key, Value >::put ( const Key &  key,
const Value &  value 
)
inline

puts a new element in the cache.

If the element is already found in the cache, it is considered a cache hit and pushed to the top of the list.

template<typename Key , typename Value >
void cxxtools::Cache< Key, Value >::put_top ( const Key &  key,
const Value &  value 
)
inline

puts a new element on the top of the cache.

If the element is already found in the cache, it is considered a cache hit and pushed to the top of the list. This method actually overrides the need, that a element needs a hit to get to the top of the cache.

template<typename Key , typename Value >
void cxxtools::Cache< Key, Value >::setMaxElements ( size_type  maxElements_)
inline
template<typename Key , typename Value >
size_type cxxtools::Cache< Key, Value >::size ( ) const
inline

returns the number of elements currently in the cache

template<typename Key , typename Value >
unsigned cxxtools::Cache< Key, Value >::winners ( ) const
inline

The documentation for this class was generated from the following file: