-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathlru.hpp
More file actions
82 lines (71 loc) · 1.85 KB
/
lru.hpp
File metadata and controls
82 lines (71 loc) · 1.85 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <unordered_map>
#include <list>
#include <iostream>
namespace cppcode { namespace common {
template <class Key, class Value>
class LRUCache {
public:
FRIEND_TEST(LRUTest, test1);
typedef typename std::pair<Key, std::shared_ptr<Value>> CacheEntry;
typedef typename std::list<CacheEntry> Container;
typedef typename std::list<CacheEntry>::iterator Iterator;
LRUCache(size_t capacity)
: m_capacity(capacity)
{
}
std::shared_ptr<Value> get(const Key& key)
{
auto it = m_keys.find(key);
if (it != m_keys.end())
{
visit(it->second);
return m_values.back().second;
}
return std::shared_ptr<Value>{};
}
void put(const Key& key, std::shared_ptr<Value> value)
{
auto keyIt = m_keys.find(key);
if (keyIt != m_keys.end())
{
visit(keyIt->second);
}
else
{
if (m_values.size() >= m_capacity)
{
auto it = m_values.begin();
m_keys.erase(it->first);
m_keys[key] = it;
visit(it);
it->first = key;
it->second = std::move(value);
}
else
{
auto newIt = m_values.emplace(m_values.end(), key, std::move(value));
m_keys[key] = newIt;
}
}
}
private:
void visit(Iterator& it)
{
if (it != m_values.end())
{
m_values.splice(m_values.end(), m_values, it);
}
}
void printValues() const
{
for (const auto& entry : m_values)
{
std::cout << entry.second << " ";
}
std::cout << &std::endl;
}
std::unordered_map<Key, Iterator> m_keys;
Container m_values;
size_t m_capacity;
};
}}