QueueCache.hpp

A simple implementation of a Least-Recently Used Cache. It orders elements by access time and removes the stalest ones in case maximum capacity is reached.

template<class Key, class Value, size_t DefaultCapacity = std::numeric_limits<size_t>::max(), class Hash = std::hash<Key>, class Pred = std::equal_to<Key>>
class QueueCache

#include <QueueCache.hpp>

Public Types

using const_iterator = typename cache_list_t::const_iterator

using iterator = typename cache_list_t::const_iterator

Public Functions

inline QueueCache(const size_t _capacity = DefaultCapacity)

~QueueCache() = default

inline size_t Size() const

Return number of elements in cache.

Returns:

number of elements in the cache

inline bool Empty() const

Test if cache has any elements.

Returns:

true if cache is empty

inline size_t Capacity() const

Return maximum number of elements that will fit in cache.

Returns:

maximum number of elements that the cache can contain

inline void Clear()

Clear the cache.

inline void Delete(const Key &key)

Delete element from cache.

Parameters:

key – Key to delete from cache

inline bool Contains(const Key &key) const

Does cache contain key?

Parameters:

key – Key to check presence of

Returns:

whether cache contains key

inline cache_list_t::iterator Put(const Key &key, const Value &val)

Store element in front of cache.

Parameters:

• key – Key of element to store

• val – Value of element to store

Returns:

Iterator to newly-added element in cache queue

inline Value &Get(const Key &key, const std::function<Value(const Key &k)> &fun = DefaultFun)

Get an element from cache. By default, this method throws an exception if the element is not in cache. This behaviour can be changed by specifying a callable as a second parameter, which must return a Value.

Parameters:

• key – Key of element to get

• fun – Optional function to be executed in case the key is not in cache

inline void SetCapacity(const size_t _capacity)

Resize the cache.

Parameters:

_capacity – New capacity of the cache.

inline const cache_list_t::const_iterator cbegin() const

Return a constant iterator to the beginning of the cache queue.

Returns:

Constant const_iterator to the beginning of cache queue

inline const cache_list_t::const_iterator cend() const

Return a constant iterator to one past the end of the cache queue.

Returns:

Constant const_iterator to one past the end of cache queue

inline const cache_list_t::const_iterator begin() const

Return a constant iterator to the beginning of the cache queue. Alias of cbegin()

Returns:

Constant const_iterator to the beginning of cache queue

inline const cache_list_t::const_iterator end() const

Return a constant iterator to one past the end of the cache queue. Alias of cend()

Returns:

Constant const_iterator to one past the end of cache queue

inline Value &operator[](const Key &index)

Get an element from cache if found, and creates it otherwise. Value type must have a default constructor and an assignment operator.

Parameters:

index – Key of element to add/retrieve

Returns:

Reference to value of element of given key

Private Types

using cache_list_t = typename std::list<std::pair<Key, Value>>

using cache_map_t = std::unordered_map<Key, typename cache_list_t::iterator, Hash, Pred>

Private Functions

inline void Shrink()

inline void Delete(const typename cache_map_t::iterator it)

Private Members

cache_list_t cache_list

cache_map_t cache_map

size_t capacity

Private Static Functions

static inline Value DefaultFun(const Key&)