Thrill  0.1
Public Types | Public Member Functions | Protected Types | Private Attributes | List of all members
LruCacheMap< Key, Value, Alloc > Class Template Reference
Thrill Layers » tlx - C++ Extensions and Utilities » Containers and Data Structures

Detailed Description

template<typename Key, typename Value, typename Alloc = std::allocator<std::pair<Key, Value> >>
class tlx::LruCacheMap< Key, Value, Alloc >

This is an expected O(1) LRU cache which contains a map of (key -> value) elements.

Elements can be put() by key into LRU cache, and later retrieved with get() using the same key. Insertion and retrieval will remark the elements as most recently used, pushing all other back in priority. The LRU cache itself does not limit the number of items, because it has no eviction mechanism. Instead, the user program must check size() before or after an insert and may extract the least recently used element.

Definition at line 163 of file lru_cache.hpp.

#include <lru_cache.hpp>

Public Types

using KeyValuePair = typename std::pair< Key, Value >
 

Public Member Functions

 LruCacheMap (const Alloc &alloc=Alloc())
 
void clear ()
 clear LRU More...
 
void erase (const Key &key)
 remove key from LRU cache More...
 
bool erase_if_exists (const Key &key) noexcept
 remove key from LRU cache More...
 
bool exists (const Key &key) const
 test if key exists in LRU cache More...
 
const Value & get (const Key &key)
 get and touch value from LRU cache for key. More...
 
const Value & get_touch (const Key &key)
 get and touch value from LRU cache for key. More...
 
KeyValuePair pop ()
 return the least recently used key value pair More...
 
void put (const Key &key, const Value &value)
 put or replace/touch item in LRU cache More...
 
size_t size () const noexcept
 return number of items in LRU cache More...
 
void touch (const Key &key)
 touch pair in LRU cache for key. Throws if it is not in the map. More...
 
bool touch_if_exists (const Key &key) noexcept
 touch pair in LRU cache for key. Returns true if it exists. More...
 

Protected Types

using List = typename std::list< KeyValuePair, Alloc >
 
using ListIterator = typename List::iterator
 
using Map = typename std::unordered_map< Key, ListIterator, std::hash< Key >, std::equal_to< Key >, typename Alloc::template rebind< std::pair< const Key, ListIterator > >::other >
 

Private Attributes

List list_
 list of entries in least-recently used order. More...
 
Map map_
 map for accelerated access to keys More...
 

Member Typedef Documentation

◆ KeyValuePair

using KeyValuePair = typename std::pair<Key, Value>

Definition at line 166 of file lru_cache.hpp.

◆ List

using List = typename std::list<KeyValuePair, Alloc>
protected

Definition at line 169 of file lru_cache.hpp.

◆ ListIterator

using ListIterator = typename List::iterator
protected

Definition at line 170 of file lru_cache.hpp.

◆ Map

using Map = typename std::unordered_map< Key, ListIterator, std::hash<Key>, std::equal_to<Key>, typename Alloc::template rebind< std::pair<const Key, ListIterator> >::other>
protected

Definition at line 175 of file lru_cache.hpp.

Constructor & Destructor Documentation

◆ LruCacheMap()

LruCacheMap ( const Alloc &  alloc = Alloc())
inlineexplicit

Definition at line 178 of file lru_cache.hpp.

Member Function Documentation

◆ clear()

void clear ( )
inline

clear LRU

Definition at line 183 of file lru_cache.hpp.

References LruCacheSet< Key, Alloc >::list_, and LruCacheSet< Key, Alloc >::map_.

◆ erase()

void erase ( const Key &  key)
inline

remove key from LRU cache

Definition at line 225 of file lru_cache.hpp.

References LruCacheSet< Key, Alloc >::list_, and LruCacheSet< Key, Alloc >::map_.

◆ erase_if_exists()

bool erase_if_exists ( const Key &  key)
inlinenoexcept

remove key from LRU cache

Definition at line 237 of file lru_cache.hpp.

References LruCacheSet< Key, Alloc >::list_, and LruCacheSet< Key, Alloc >::map_.

◆ exists()

bool exists ( const Key &  key) const
inline

test if key exists in LRU cache

Definition at line 271 of file lru_cache.hpp.

References LruCacheSet< Key, Alloc >::map_.

◆ get()

const Value& get ( const Key &  key)
inline

get and touch value from LRU cache for key.

Definition at line 248 of file lru_cache.hpp.

References LruCacheSet< Key, Alloc >::map_.

◆ get_touch()

const Value& get_touch ( const Key &  key)
inline

get and touch value from LRU cache for key.

Definition at line 259 of file lru_cache.hpp.

References LruCacheSet< Key, Alloc >::list_, and LruCacheSet< Key, Alloc >::map_.

◆ pop()

KeyValuePair pop ( )
inline

return the least recently used key value pair

Definition at line 281 of file lru_cache.hpp.

References LruCacheSet< Key, Alloc >::list_, LruCacheSet< Key, Alloc >::map_, and LruCacheSet< Key, Alloc >::size().

◆ put()

void put ( const Key &  key,
const Value &  value 
)
inline

put or replace/touch item in LRU cache

Definition at line 189 of file lru_cache.hpp.

References LruCacheSet< Key, Alloc >::list_, and LruCacheSet< Key, Alloc >::map_.

◆ size()

size_t size ( ) const
inlinenoexcept

return number of items in LRU cache

Definition at line 276 of file lru_cache.hpp.

References LruCacheSet< Key, Alloc >::map_.

◆ touch()

void touch ( const Key &  key)
inline

touch pair in LRU cache for key. Throws if it is not in the map.

Definition at line 204 of file lru_cache.hpp.

References LruCacheSet< Key, Alloc >::list_, and LruCacheSet< Key, Alloc >::map_.

◆ touch_if_exists()

bool touch_if_exists ( const Key &  key)
inlinenoexcept

touch pair in LRU cache for key. Returns true if it exists.

Definition at line 215 of file lru_cache.hpp.

References LruCacheSet< Key, Alloc >::list_, and LruCacheSet< Key, Alloc >::map_.

Member Data Documentation

◆ list_

List list_
private

list of entries in least-recently used order.

Definition at line 293 of file lru_cache.hpp.

◆ map_

Map map_
private

map for accelerated access to keys

Definition at line 295 of file lru_cache.hpp.

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