Skip to main content

The Cache Class Template Reference

Declaration​

template <typename K, typename V> class Cache<K, V> { ... }

Included Headers​

#include <src/cache.h>

Public Member Typedefs Index​

template <typename K, typename V>
usingkv_pair = std::pair< K, V >
template <typename K, typename V>
usingiterator = typename std::list< kv_pair >::iterator
template <typename K, typename V>
usingconst_iterator = typename std::list< kv_pair >::const_iterator

Public Constructors Index​

template <typename K, typename V>
Cache (size_t capacity)

creates a cache that can hold capacity elements More...

Public Member Functions Index​

template <typename K, typename V>
V *insert (const K &key, V &&value)

Inserts value under key in the cache. More...

template <typename K, typename V>
V *insert (const K &key, const V &value)

Inserts value under key in the cache. More...

template <typename K, typename V>
voidremove (const K &key)
template <typename K, typename V>
V *find (const K &key)
template <typename K, typename V>
size_tsize () const

Returns the number of values stored in the cache. More...

template <typename K, typename V>
size_tcapacity () const

Returns the maximum number of values that can be stored in the cache. More...

template <typename K, typename V>
uint64_thits () const

Returns how many of the find() calls did find a value in the cache. More...

template <typename K, typename V>
uint64_tmisses () const

Returns how many of the find() calls did not found a value in the cache. More...

template <typename K, typename V>
voidclear ()

Clears all values in the cache. More...

template <typename K, typename V>
iteratorbegin ()
template <typename K, typename V>
iteratorend ()
template <typename K, typename V>
const_iteratorbegin () const
template <typename K, typename V>
const_iteratorend () const

Private Member Functions Index​

template <typename K, typename V>
voidresize ()

Private Member Attributes Index​

template <typename K, typename V>
size_tm_capacity
template <typename K, typename V>
std::list< kv_pair >m_cacheItemList
template <typename K, typename V>
std::unordered_map< K, iterator >m_cacheItemMap
template <typename K, typename V>
uint64_tm_hits =0
template <typename K, typename V>
uint64_tm_misses =0

Description​

Fixed size cache for value type V using keys of type K.

When the maximum capacity has reached, the least recently used value is removed from the cache (LRU strategy).

Definition at line 31 of file cache.h.

Public Member Typedefs​

const_iterator​

template <typename K, typename V>
using Cache< K, V >::const_iterator = typename std::list<kv_pair>::const_iterator

Definition at line 36 of file cache.h.

36 using const_iterator = typename std::list<kv_pair>::const_iterator;

iterator​

template <typename K, typename V>
using Cache< K, V >::iterator = typename std::list<kv_pair>::iterator

Definition at line 35 of file cache.h.

35 using iterator = typename std::list<kv_pair>::iterator;

kv_pair​

template <typename K, typename V>
using Cache< K, V >::kv_pair = std::pair<K,V>

Definition at line 34 of file cache.h.

34 using kv_pair = std::pair<K,V>;

Public Constructors​

Cache()​

template <typename K, typename V>
Cache< K, V >::Cache (size_t capacity)
 inline

creates a cache that can hold capacity elements

Definition at line 39 of file cache.h.

39 Cache(size_t capacity) : m_capacity(capacity)
40 {
41 }

References Cache< K, V >::capacity and Cache< K, V >::m_capacity.

Public Member Functions​

begin()​

template <typename K, typename V>
iterator Cache< K, V >::begin ()
 inline

Definition at line 156 of file cache.h.

156 iterator begin() { return m_cacheItemList.begin(); }

Reference Cache< K, V >::m_cacheItemList.

begin()​

template <typename K, typename V>
const_iterator Cache< K, V >::begin ()
 inline

Definition at line 158 of file cache.h.

158 const_iterator begin() const { return m_cacheItemList.cbegin(); }

Reference Cache< K, V >::m_cacheItemList.

capacity()​

template <typename K, typename V>
size_t Cache< K, V >::capacity ()
 inline

Returns the maximum number of values that can be stored in the cache.

Definition at line 132 of file cache.h.

132 size_t capacity() const
133 {
134 return m_capacity;
135 }

Reference Cache< K, V >::m_capacity.

Referenced by Cache< K, V >::Cache.

clear()​

template <typename K, typename V>
void Cache< K, V >::clear ()
 inline

Clears all values in the cache.

Definition at line 150 of file cache.h.

150 void clear()
151 {
152 m_cacheItemMap.clear();
153 m_cacheItemList.clear();
154 }

References Cache< K, V >::m_cacheItemList and Cache< K, V >::m_cacheItemMap.

end()​

template <typename K, typename V>
iterator Cache< K, V >::end ()
 inline

Definition at line 157 of file cache.h.

157 iterator end() { return m_cacheItemList.end(); }

Reference Cache< K, V >::m_cacheItemList.

end()​

template <typename K, typename V>
const_iterator Cache< K, V >::end ()
 inline

Definition at line 159 of file cache.h.

159 const_iterator end() const { return m_cacheItemList.cend(); }

Reference Cache< K, V >::m_cacheItemList.

find()​

template <typename K, typename V>
V * Cache< K, V >::find (const K & key)
 inline

Finds a value in the cache given the corresponding key.

Returns

a pointer to the value or nullptr if the key is not found in the cache

info

The hit and miss counters are updated, see hits() and misses().

Definition at line 105 of file cache.h.

105 V *find(const K &key)
106 {
107 auto it = m_cacheItemMap.find(key);
108 if (it != m_cacheItemMap.end())
109 {
110 // move the item to the front of the list
111 m_cacheItemList.splice(m_cacheItemList.begin(),
112 m_cacheItemList,
113 it->second);
114 m_hits++;
115 // return the value
116 return &it->second->second;
117 }
118 else
119 {
120 m_misses++;
121 }
122 return nullptr;
123 }

References Cache< K, V >::m_cacheItemList, Cache< K, V >::m_cacheItemMap, Cache< K, V >::m_hits and Cache< K, V >::m_misses.

hits()​

template <typename K, typename V>
uint64_t Cache< K, V >::hits ()
 inline

Returns how many of the find() calls did find a value in the cache.

Definition at line 138 of file cache.h.

138 uint64_t hits() const
139 {
140 return m_hits;
141 }

Reference Cache< K, V >::m_hits.

insert()​

template <typename K, typename V>
V * Cache< K, V >::insert (const K & key, V && value)
 inline

Inserts value under key in the cache.

Definition at line 44 of file cache.h.

44 [[maybe_unused]] V *insert(const K &key,V &&value)
45 {
46 // reuse item if it already exists
47 auto it = m_cacheItemMap.find(key);
48 if (it != m_cacheItemMap.end())
49 {
50 // move the item to the front of the list
51 m_cacheItemList.splice(m_cacheItemList.begin(),
52 m_cacheItemList,
53 it->second);
54 std::exchange(it->second->second,value);
55 return &it->second->second;
56 }
57 // create new item
58 m_cacheItemList.push_front(kv_pair(key,std::move(value)));
59 V *result = &m_cacheItemList.front().second;
60 m_cacheItemMap[key] = m_cacheItemList.begin();
61 // remove least recently used item if cache is full
62 resize();
63 return result;
64 }

References Cache< K, V >::m_cacheItemList, Cache< K, V >::m_cacheItemMap and Cache< K, V >::resize.

insert()​

template <typename K, typename V>
V * Cache< K, V >::insert (const K & key, const V & value)
 inline

Inserts value under key in the cache.

Definition at line 67 of file cache.h.

67 [[maybe_unused]] V *insert(const K &key,const V &value)
68 {
69 // reuse item if it already exists
70 auto it = m_cacheItemMap.find(key);
71 if (it != m_cacheItemMap.end())
72 {
73 // move the item to the front of the list
74 m_cacheItemList.splice(m_cacheItemList.begin(),
75 m_cacheItemList,
76 it->second);
77 it->second->second = value;
78 return &it->second->second;
79 }
80 // store new item
81 m_cacheItemList.push_front(kv_pair(key,value));
82 V *result = &m_cacheItemList.front().second;
83 m_cacheItemMap[key] = m_cacheItemList.begin();
84 // remove least recently used item if cache is full
85 resize();
86 return result;
87 }

References Cache< K, V >::m_cacheItemList, Cache< K, V >::m_cacheItemMap and Cache< K, V >::resize.

misses()​

template <typename K, typename V>
uint64_t Cache< K, V >::misses ()
 inline

Returns how many of the find() calls did not found a value in the cache.

Definition at line 144 of file cache.h.

144 uint64_t misses() const
145 {
146 return m_misses;
147 }

Reference Cache< K, V >::m_misses.

remove()​

template <typename K, typename V>
void Cache< K, V >::remove (const K & key)
 inline

Removes entry key from the cache.

info

this invalidates any iterators

Definition at line 91 of file cache.h.

91 void remove(const K &key)
92 {
93 // remove item if it already exists
94 auto it = m_cacheItemMap.find(key);
95 if (it != m_cacheItemMap.end())
96 {
97 m_cacheItemList.erase(it->second);
98 m_cacheItemMap.erase(it);
99 }
100 }

References Cache< K, V >::m_cacheItemList and Cache< K, V >::m_cacheItemMap.

size()​

template <typename K, typename V>
size_t Cache< K, V >::size ()
 inline

Returns the number of values stored in the cache.

Definition at line 126 of file cache.h.

126 size_t size() const
127 {
128 return m_cacheItemMap.size();
129 }

Reference Cache< K, V >::m_cacheItemMap.

Private Member Functions​

resize()​

template <typename K, typename V>
void Cache< K, V >::resize ()
 inline

Definition at line 163 of file cache.h.

163 void resize()
164 {
165 if (m_cacheItemMap.size() > m_capacity)
166 {
167 auto last_it = m_cacheItemList.end();
168 --last_it;
169 m_cacheItemMap.erase(last_it->first);
170 m_cacheItemList.pop_back();
171 }
172 }

References Cache< K, V >::m_cacheItemList, Cache< K, V >::m_cacheItemMap and Cache< K, V >::m_capacity.

Referenced by Cache< K, V >::insert and Cache< K, V >::insert.

Private Member Attributes​

m_cacheItemList​

template <typename K, typename V>
std::list<kv_pair> Cache< K, V >::m_cacheItemList

Definition at line 176 of file cache.h.

176 std::list<kv_pair> m_cacheItemList;

Referenced by Cache< K, V >::begin, Cache< K, V >::begin, Cache< K, V >::clear, Cache< K, V >::end, Cache< K, V >::end, Cache< K, V >::find, Cache< K, V >::insert, Cache< K, V >::insert, Cache< K, V >::remove and Cache< K, V >::resize.

m_cacheItemMap​

template <typename K, typename V>
std::unordered_map<K,iterator> Cache< K, V >::m_cacheItemMap

Definition at line 178 of file cache.h.

178 std::unordered_map<K,iterator> m_cacheItemMap;

Referenced by Cache< K, V >::clear, Cache< K, V >::find, Cache< K, V >::insert, Cache< K, V >::insert, Cache< K, V >::remove, Cache< K, V >::resize and Cache< K, V >::size.

m_capacity​

template <typename K, typename V>
size_t Cache< K, V >::m_capacity

Definition at line 174 of file cache.h.

174 size_t m_capacity;

Referenced by Cache< K, V >::Cache, Cache< K, V >::capacity and Cache< K, V >::resize.

m_hits​

template <typename K, typename V>
uint64_t Cache< K, V >::m_hits =0

Definition at line 179 of file cache.h.

179 uint64_t m_hits=0;

Referenced by Cache< K, V >::find and Cache< K, V >::hits.

m_misses​

template <typename K, typename V>
uint64_t Cache< K, V >::m_misses =0

Definition at line 180 of file cache.h.

180 uint64_t m_misses=0;

Referenced by Cache< K, V >::find and Cache< K, V >::misses.

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

Generated via doxygen2docusaurus by Doxygen 1.14.0.