18 #include <unordered_map>
26 template <
class Tkey,
class Tdata>
29 typedef std::pair<Tkey, Tdata *> Tpair;
30 typedef typename std::list<Tpair>::iterator Titer;
33 std::unordered_map<Tkey, Titer>
lookup;
51 return this->lookup.find(key) != this->lookup.end();
60 Tdata *
Insert(
const Tkey key, Tdata *item)
66 old = this->lookup[key]->second;
67 this->lookup[key]->second = item;
70 if (this->data.size() >= this->capacity) {
71 Tpair last =
data.back();
72 this->lookup.erase(last.first);
73 this->data.pop_back();
79 this->data.push_front(std::make_pair(key, item));
80 this->lookup.emplace(key, this->data.begin());
92 if (this->data.empty())
return nullptr;
94 Tdata *value = this->data.back().second;
95 this->lookup.erase(this->data.back().first);
96 this->data.pop_back();
106 inline Tdata *
Get(
const Tkey key)
108 if (this->lookup.find(key) == this->lookup.end())
throw std::out_of_range(
"item not found");
110 this->data.splice(this->data.begin(), this->data, this->lookup[key]);
112 return this->data.front().second;