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++实现

回答

相关问题