Implement an LRU Cache

Implementing an LRU Cache requires two data types:

• queue
• map

The queue is used to push multiple elements while a map is used to reference an item in the queue.

<template t>
class LRUCache {
    private:
        queue<t> q;
        unordered_map<t> map;
    public:
        LRUCache() {}
        t getElm(t elm) {
            // found
            if(map.find(elm) != map.end()) {
                return map[elm];
            }

            if(q.full()) {
                // pop LRU
                t elm = q.top();
                map.erase(elm);
                q.pop_front();
            }

            //not found
            map[elm] = elm;
            q.push_back(elm);

            return elm;
        }
}