LeetCode (26) LRU Cache

タイトルの説明
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
トピックでは、キャッシュ・データ構造を実現する必要があります.要件の主な操作は、取得(get)と挿入です.(set).キャッシュがいっぱいになった場合、setで最も長く使用されていない要素を削除し、新しい要素を挿入する必要があることに注意してください.これは、データ構造で各要素の使用順序を記録するか、要素の使用順序に基づいて要素を保存する方法を設計する必要があります.get要素の場合、要素が保存されている場合に注意してください.キャッシュでは、エレメントの使用順序が繰り上げられます.
キャッシュ内のデータは、双方向チェーンテーブルを使用して表すことができます.チェーンテーブルのヘッダは最近使用された要素を表し、チェーンテーブルの末尾は最長時間使用されていない要素を表す.エレメントを取得/挿入すると、チェーンテーブルのヘッダにエレメントが配置されます.挿入された要素のkeyがキャッシュにすでに存在する場合は、元のデータ(key,value)ノードを削除することに注意してください.
チェーンテーブルへのランダムアクセスの時間的複雑さはO(n)であり,上のデータ構造が要素を取得し挿入するたびに時間的複雑さはO(n)であることを知った.時間的複雑さを低減するために,keyによりノード位置を保存し,時間的複雑さをO(logn)とするmap構造を用いることができる.より高い時間効率が必要な場合はunordered_も使用できます.mapはmapの代わりにノード位置を保存します.
map構造は以下の通りである.

map<int, node*> cache;

上記の考え方に基づいて得られた完全なコードは以下の通りである.

struct node
{
    int key;
    int value;
    node* pre;
    node* next;
    node(int k, int v) :key(k), value(v), pre(NULL), next(NULL) {};
};

class LRUCache{
private:
    int m_capacity;
    int m_size;
    node* m_head;
    node* m_tail;
    map<int, node*> m_cache;
public:

    LRUCache(int capacity) {
        m_capacity = capacity;
        m_size = 0;
        m_head = new node(0, 0);
        m_tail = new node(0, 0);
        m_head->next = m_tail;
        m_tail->pre = m_head;
        m_cache.clear();
    }

    ~LRUCache() {
        delete m_head;
        delete m_tail;

        map<int, node*>::iterator it;
        for (it = m_cache.begin(); it != m_cache.end(); ++it)
        {
            delete(it->second);
        }
        m_cache.clear();
    }

    void putTohead(node* cur)
    {
        cur->next = m_head->next;
        cur->next->pre = cur;
        m_head->next = cur;
        cur->pre = m_head;      
    }

    int get(int key) {
        map<int, node*>::iterator it = m_cache.find(key);
        if (it != m_cache.end())
        {
            node* cur = it->second;
            cur->pre->next = cur->next;
            cur->next->pre = cur->pre;
            putTohead(cur);
            return cur->value;
        }
        else
            return -1;
    }

    void set(int key, int value) {      
        map<int, node*>::iterator it = m_cache.find(key);
        if (it != m_cache.end())
        {
            node* cur = it->second;
            cur->value = value;
            cur->pre->next = cur->next;
            cur->next->pre = cur->pre;
            putTohead(it->second);
        }
        else 
        {
            node* new_node = new node(key, value);
            putTohead(new_node);
            m_cache[key] = new_node;
            if (m_size < m_capacity)
                m_size++;
            else
            {
                node* del = m_tail->pre;
                del->pre->next = m_tail;
                m_tail->pre = del->pre;
                it = m_cache.find(del->key);
                m_cache.erase(it);
                delete del;
            }
        }
    }
};