lru_cache/lru_cache.h at master · ilnarb/lru_cache · GitHub

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#ifndef __LRU_CACHE_H__
#define __LRU_CACHE_H__

#include <list>
#include <unordered_map>

template<
	typename Key,
	typename Value,
	// lets allow to change hasher and equal predicate
	typename Hash = std::hash<Key>,
	typename Pred = std::equal_to<Key>
>
class lru_cache_t
{
public:
	typedef Key key_type;
	typedef Value value_type;
	typedef Hash hasher_type;
	typedef Pred predicate_type;
	typedef typename std::pair<key_type, value_type> pair_type;
	typedef typename std::list<pair_type>::iterator iterator;
	typedef typename std::list<pair_type>::const_iterator const_iterator;
	//
	lru_cache_t(size_t max_size): _max_size(max_size)
	{
	}
	value_type& operator[](const key_type &key)
	{
		auto it = _mapper.find(key);
		if (it != _mapper.end())
		{
			const auto& lit = it->second;
			// move to the head
			_elements.splice(_elements.begin(), _elements, lit);
			//
			return lit->second;
		}
		else
		{
			if (_size >= _max_size)
			{
				const auto &pair = _elements.back();
				_mapper.erase(pair.first);
				_elements.pop_back();
				_size--;
			}
			//
			_elements.emplace_front(key, value_type());
			auto lit = _elements.begin();
			_mapper.emplace(key, lit);
			_size++;
			return lit->second;
		}
	}
	void set(const key_type &key, const value_type &value)
	{
		(*this)[key] = value;
	}
	bool get(const key_type &key, value_type &value)
	{
		auto it = _mapper.find(key);
		if (it != _mapper.end())
		{
			const auto& lit = it->second;
			// move to the head
			_elements.splice(_elements.begin(), _elements, lit);
			value = lit->second;
			return true;
		}
		return false;
	}
	bool get(const key_type &key, value_type &value) const
	{
		auto it = _mapper.find(key);
		if (it != _mapper.end())
		{
			const auto& lit = it->second;
			value = lit->second;
			return true;
		}
		return false;
	}
	const value_type& operator[](const key_type &key) const
	{
		auto it = _mapper.find(key);
		if (it != _mapper.end())
		{
			const auto& lit = it->second;
			return lit->second;
		}
		return dummy;
	}
	bool exists(const key_type &key) const
	{
		auto it = _mapper.find(key);
		return (it != _mapper.end());
	}
	bool erase(const key_type &key)
	{
		auto it = _mapper.find(key);
		if (it != _mapper.end())
		{
			const auto& lit = it->second;
			_elements.erase(lit);
			_mapper.erase(it);
			_size--;
			return true;
		}
		return false;
	}
	// iterators
	iterator begin()
	{
		return _elements.begin();
	}
	iterator end()
	{
		return _elements.end();
	}
	const_iterator begin() const
	{
		return _elements.begin();
	}
	const_iterator end() const
	{
		return _elements.end();
	}
	//
	size_t size() const
	{
		return _size;
	}
	size_t max_size() const
	{
		return _max_size;
	}
	bool empty() const
	{
		return _elements.empty();
	}
	void clear()
	{
		_elements.clear();
		_mapper.clear();
		_size = 0;
	}
private:
	size_t _size = 0, _max_size;
	std::list<pair_type> _elements;
	std::unordered_map<key_type, iterator, hasher_type, predicate_type> _mapper;
	value_type dummy;
};

#endif // __LRU_CACHE_H__