LRUCache

class LRUCache {
    template<typename T>
    class my_deque {
    public:
        class deque_element {
        public:
            deque_element(T val, deque_element *nxt) : value(val), next(nxt) {
            }
            deque_element *previous = nullptr;
            deque_element *next = nullptr;
            T value;
        };

        deque_element *head = nullptr;
        deque_element *tail = nullptr;
        std::size_t size{};

        T back() {
            return tail->value;
        }

        void pop_back() {
            auto current_tail = tail;
            if (tail) {
                if (tail->previous) {
                    tail = tail->previous;
                    tail->next = nullptr;
                } else {
                    head = nullptr;
                    tail = nullptr;
                }

                delete current_tail;
                --size;
            }
        };

        void erase(deque_element *elem) {
            if (elem->previous != nullptr && elem->next != nullptr) {
                elem->previous->next = elem->next;
                elem->next->previous = elem->previous;
            }

            if (elem->previous != nullptr && elem->next == nullptr) {
                tail = elem->previous;
                tail->next = nullptr;
            }

            if (elem->next != nullptr && elem->previous == nullptr) {
                head = elem->next;
                head->previous = nullptr;
            }

            if (elem->previous == nullptr && elem->next == nullptr) {
                head = nullptr;
                tail = nullptr;
            }

            delete elem;
            --size;
        }

        void emplace_front(T value) {
            deque_element *current_deque = new deque_element(value, head);
            if (head != nullptr) {
                head->previous = current_deque;
            }
            head = current_deque;

            if (tail == nullptr) {
                tail = current_deque;
            }

            ++size;
        }
    };

    template<typename T> using ptr_to_deque_elem = typename my_deque<T>::deque_element*;

    const std::size_t available_size;
    my_deque<int> elements;
    std::unordered_map<int, std::pair<int, ptr_to_deque_elem<int>>> cache;
public:
    LRUCache(int capacity) :
        available_size(static_cast<std::size_t>(capacity)),
        cache(std::unordered_map<int, std::pair<int, ptr_to_deque_elem<int>>>{}),
        elements(my_deque<int>{})
    {
    }

    int get(int key) {
        auto elem = cache.find(key);
        if (elem != cache.end()) {
            elements.erase(elem->second.second);
            elements.emplace_front(key);

            elem->second.second = elements.head;

            return elem->second.first;
        }

        return -1;
    }

    void put(int key, int value) {
        auto elem = cache.find(key);
        if (elem != cache.end()) {
            elements.erase(elem->second.second);
            elements.emplace_front(key);
            elem->second.first = value;
            elem->second.second = elements.head;

            return;
        }

        if (elements.size == available_size) {
            cache.erase(elements.back());
            elements.pop_back();
        }

        elements.emplace_front(key);
        cache.insert(std::make_pair(key, std::make_pair(value, elements.head)));
    }
};