LRU Cache C++ Реализация

Question

Проблема

Разработка и внедрение структуры данных для наименее недавно использовавшихся (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.

Answer 1

Вы не инициализируете head и tail, поэтому они имеют неопределенные значения. Если эти значения имеют значение null, программа будет работать так, как вы ожидаете; если нет, все может случиться.

Средство анализа времени выполнения, например Valgrind, полезно для поиска ошибок.