3#ifndef STEP20_LEAST_FREQUENTLY_USED_HPP
4#define STEP20_LEAST_FREQUENTLY_USED_HPP
8#include <unordered_map>
15 class Hash = std::hash<Key>,
16 class KeyEqual = std::equal_to<Key>>
19 using item_list = std::list<item_type>;
20 using item_iterator =
typename item_list::iterator;
22 using freq_list = std::list<freq_type>;
23 using freq_iterator =
typename freq_list::iterator;
37 std::unordered_map<Key, item_iterator, Hash, KeyEqual> map_;
38 std::size_t capacity_;
40 bool equal(freq_iterator it, std::size_t n)
const
42 return it != list_.end() && it->n == n;
46 explicit cache(std::size_t capacity) : capacity_(capacity) {}
54 const T*
find(
const Key& key)
56 auto it = map_.find(key);
59 auto item = it->second;
60 auto freq = item->parent;
61 auto next = std::next(freq);
62 if (!equal(next, freq->n + 1)) {
63 if (freq->items.size() == 1) {
65 return std::addressof(item->val);
67 next = list_.emplace(next, freq->n + 1);
70 next->items.splice(next->items.end(), freq->items, item);
73 if (next->items.empty())
78 if (freq->items.empty())
80 return std::addressof(item->val);
87 if (
auto ptr =
find(key)) {
88 *
const_cast<T*
>(ptr) = val;
91 if (map_.size() >= std::max<std::size_t>(1, capacity_)) {
92 auto freq = list_.begin();
93 auto item = freq->items.begin();
94 map_.erase(item->key);
95 freq->items.erase(item);
96 if (freq->items.empty())
99 auto freq = list_.begin();
100 auto exists = equal(freq, 1);
101 freq = exists ? freq : list_.emplace(freq, 1);
102 auto item = freq->items.end();
104 item = freq->items.emplace(item, freq, key, val);
105 map_.emplace(key, item);
110 else if (item != freq->items.end())
111 freq->items.erase(item);
An O(1) algorithm for implementing the LFU cache eviction scheme.
Definition least_frequently_used.hpp:17
cache & operator=(const cache &)=delete
const T * find(const Key &key)
Definition least_frequently_used.hpp:54
cache & operator=(cache &&)=default
cache(const cache &)=delete
void insert_or_assign(const Key &key, const T &val)
Definition least_frequently_used.hpp:85
cache(std::size_t capacity)
Definition least_frequently_used.hpp:46
Definition least_frequently_used.hpp:10