# my c++ solution, not very neat, but sometimes it can beat 100%, 53ms

• ...
/*
*the private struct Node presents the priority of Cache,
*head->next is the least recently used
*use list<Node *> hash[prime] to store the prev Node of the present Node
*to change the order of Cache
*cap means capacity, siz means the cuurent number of used Cache
*/

#define prime 997
class LRUCache {
private:
struct Node {
int key, val;
Node *next;
Node(int a = 0, int b = 0, Node *n = nullptr) : key(a), val(b), next(n) {}
};

public:

``````int get(int key)
{
//check wether the key is in the Cache(hash table)
if (hash[key % prime].empty())
return -1;
auto p = hash[key % prime].begin();
Node *now = nullptr;
for (; p != hash[key % prime].end(); ++p)
if ((*p)->next->key == key) {
now = *p;
break;
}
if (now == nullptr) return -1;

//if we need to change the priority of this Node
if (now->next != tail) {
tail->next = now->next;
now->next = now->next->next;
*p = tail;
tail = tail->next;
tail->next = nullptr;
//and this
for (auto p = hash[now->next->key % prime].begin(); p != hash[now->next->key % prime].end(); ++p)
if (*p == tail) {
*p = now;
break;
}
}
return tail->val;
}

void set(int key, int value)
{
bool flag = true;
//the same as get()
auto p = hash[key % prime].begin();
Node *now = nullptr;
if (hash[key % prime].empty())
flag = false;
else {
for (; p != hash[key % prime].end(); ++p)
if ((*p)->next->key == key) {
now = *p;
break;
}
if (now == nullptr) flag = false;
}

if (flag) {
//this code is exactly the same as above...
if (now->next != tail) {
tail->next = now->next;
now->next = now->next->next;
*p = tail;
tail = tail->next;
tail->next = nullptr;
tail->val = value;

for (auto p = hash[now->next->key % prime].begin(); p != hash[now->next->key % prime].end(); ++p)
if (*p == tail) {
*p = now;
break;
}
}
tail->val = value;
} else {
if (siz == cap) { //if full
for (auto q = hash[head->next->key % prime].begin(); q != hash[head->next->key % prime].end(); ++q) {
break;
}
}

--siz;
}
++siz;
tail->next = new Node(key, value);
hash[key % prime].push_back(tail);
tail = tail->next;
}
}
``````

private: