14 #include <unordered_map>
21 template <
class Tkey,
class Tdata>
24 typedef std::pair<Tkey, Tdata *> Tpair;
25 typedef typename std::list<Tpair>::iterator Titer;
28 std::unordered_map<Tkey, Titer>
lookup;
46 return this->lookup.find(key) != this->lookup.end();
55 Tdata *
Insert(
const Tkey key, Tdata *item)
61 old = this->lookup[key]->second;
62 this->lookup[key]->second = item;
65 if (this->data.size() >= this->capacity) {
66 Tpair last =
data.back();
67 this->lookup.erase(last.first);
68 this->data.pop_back();
74 this->data.emplace_front(key, item);
75 this->lookup.emplace(key, this->data.begin());
87 if (this->data.empty())
return nullptr;
89 Tdata *value = this->data.back().second;
90 this->lookup.erase(this->data.back().first);
91 this->data.pop_back();
101 inline Tdata *
Get(
const Tkey key)
103 if (this->lookup.find(key) == this->lookup.end())
throw std::out_of_range(
"item not found");
105 this->data.splice(this->data.begin(), this->data, this->lookup[key]);
107 return this->data.front().second;
Size limited cache with a least recently used eviction strategy.
LRUCache(size_t max_items)
Construct new LRU cache map.
bool Contains(const Tkey key)
Test if a key is already contained in the cache.
std::list< Tpair > data
Ordered list of all items.
Tdata * Get(const Tkey key)
Get an item from the cache.
const size_t capacity
Number of items to cache.
Tdata * Insert(const Tkey key, Tdata *item)
Insert a new data item with a specified key.
std::unordered_map< Tkey, Titer > lookup
Map of keys to items.
Tdata * Pop()
Pop the least recently used item.