```
class LRUCache{
public:
LRUCache(int capacity) {
head = tail = nullptr;
m_capacity = capacity;
m_size = 0;
}
int get(int key) {
if( !m_hash.count( key ) )
return -1; // we don't have the key
assert( head && tail && m_size >= 1 );
ListNode *prev = m_hash[ key ];
ListNode *me = prev ? prev->next : head;
assert( me );
assert( me->key == key );
if( me != tail ) {
assert( m_size >= 2 ); // there's at least me and tail
assert( me->next ); // me is not the tail!
// detach 'me' from present location
m_hash[ me->next->key ] = prev;
( prev ? prev->next : head ) = me->next;
me->next = nullptr;
// attach 'me' to the end
m_hash[ key ] = tail;
tail->next = me;
tail = me;
}
return me->value;
}
void set(int key, int value) {
if( m_capacity <= 0 )
return; // nothing can be done
if( m_hash.count( key ) ) { // if the key already exists...
get( key ); // ... just refresh it,
tail->value = value; // and set the new value.
return;
}
m_hash[ key ] = tail;
tail = ( tail ? tail->next : head ) = new ListNode{ key, value, nullptr };
++m_size;
if( m_size > m_capacity ) {
// we mustdrop the least recently used node
ListNode *deleteMe = head;
head = deleteMe->next;
m_hash.erase( deleteMe->key );
m_hash[ head->key ] = nullptr;
delete deleteMe;
--m_size;
}
}
private:
// head is the LRU and tail is the MRU element
// A singly linked list suffices
struct ListNode { int key; int value; struct ListNode *next; } *head, *tail;
/* The hashtable maps keys to the previous node in the list,
i.e. m_hash[key]->next is the node that corresponds to key.
If the key corresponds to the head node, m_hash[key] is null.
This "previous" antic enables us to use a singly linked list.
*/
std::unordered_map<int, ListNode *> m_hash;
int m_size; // how many elements are currently in the cache?
int m_capacity; // max. elements allowed in the cache
};
```