LRU緩存C++實現

設計和實現一個數據結構最近最少使用（LRU）高速緩存。它應該支持以下操作：get和set。

get(key) - 如果密鑰存在於緩存中，則獲取密鑰的值（總是正數），否則返回-1。

set(key, value) - 如果密鑰不存在，請設置或插入值。當緩存達到其容量時，它應該在插入新項目之前使最近最少使用的項目無效。

我的程序

class LRUCache { 
public: 
    LRUCache(int capacity) { 
     LRUCache::capacity = capacity; 
     len = 0; 
    } 

    int get(int key) { 
     if (table.find(key) != table.end()) { 
      removeNode(table[key]); 
      setHead(table[key]); 
      return table[key]->value; 
     } else { 
      return -1; 
     } 
    } 

    void set(int key, int value) { 
     if(table.find(key) != table.end()) { 
      ListNode *curr = table[key]; 
      curr->value = value; 
      removeNode(curr); 
      setHead(curr); 
     } else { 
      ListNode *curr = new ListNode(key, value); 
      if(len < capacity) { 
       setHead(curr); 
       table[key] = curr; 
       len++; 
      } else { 
       ListNode *tmp = tail; 
       tail = tail->prev; 
       if(tail) { 
        tail->next = nullptr; 
       } 
       table.erase(tmp->key); 
       delete tmp; 
       setHead(curr); 
       table[key] = curr; 
      } 
     } 
    } 
private: 
    struct ListNode { 
     int key, value; 
     ListNode *prev, *next; 
     ListNode(int key, int value) 
      : key(key) 
      , value(value) 
      , prev(nullptr) 
      , next(nullptr) { 
     } 

    }; 
    unordered_map<int, ListNode*> table; 
    ListNode *head, *tail; 
    int capacity; 
    int len; 
    void removeNode(ListNode *node) { 
     if(node->prev) { 
      node->prev->next = node->next; 
     } else { 
      head = node->next; 
     } 
     if(node->next) { 
      node->next->prev = node->prev; 
     } else { 
      tail = node->prev; 
     } 
    } 

    void setHead(ListNode *node) { 
     node->next = head; 
     node->prev = nullptr; 
     if(head) { 
      head->prev = node; 
     } 
     head = node; 
     if(!tail) { 
      tail = node; 
     } 
    } 
};

樣品輸入：

1 // capacity 
2 1 // set(int, int) 
1 // get(int)

輸出在我的機器：

-1

產出在線評測編譯：

運行時錯誤

哪些錯誤實際？ The problem is of Leetcode。

來源

2014-09-11 Kaidul Islam

也沒有斷言你*跑*它意味着你*調試*它。這是你唯一的數據集嗎？（並且我讀過它，例如：通過'get（）'中的operator []'重複進行的不必要的查找效率非常低下）。例如，在哪裏，你是否爲你的鏈表初始化'head'和'tail'爲NULL？ – WhozCraig 2014-09-11 09:43:53

是的。初始化'head'和'tail'後，現在接受它。 :)奇怪的是，如果沒有初始化，它可以完美地對抗我係統中的所有測試用例。 – 2014-09-11 09:56:15

我懷疑你的調試分配器零內存（在追蹤這樣的問題時，這是一個最沒有用的屬性）。也許在將來某個時候重新使用'std :: list <>'作爲你的值並將鍵映射到迭代器。祝你好運。 – WhozCraig 2014-09-11 09:57:35

您不初始化head和tail，因此它們具有不確定的值。如果這些值恰好爲空，那麼該程序將按照您的預期工作;如果沒有，任何事情都可能發生

像Valgrind這樣的運行時分析工具很適合尋找這樣的錯誤。

來源

2014-09-11 09:49:13

行動！ 'LRUCache（int capacity）{LRUCache :: capacity = capacity; len = 0; head = tail = nullptr;}'現在接受！謝謝先生！ – 2014-09-11 09:53:10

奇怪的是 - 它對我係統中的所有測試用例都是完美的工作 – 2014-09-11 09:54:20

@KaidulIslam：如果內存碰巧包含零值，則會發生這種情況，所以指針無效。這是未定義行爲的最大問題：任何事情都可能發生。 – 2014-09-11 10:06:02

LRU緩存C++實現

回答

相關問題