从C++的链表中删除指针

我写了这个哈希映射（这是电话访谈练习的一部分），当我放置一个元素时，我做了一个new Node(key, value)。我想确保当hashmap本身超出范围时我正在清理。从C++的链表中删除指针

我错过了这里的任何东西吗？有什么方法可以检查是否有内存泄漏？

class HashMap { 
private: 
    list<Node*> data[SIZE]; 

public: 
    ~HashMap(); 
    Node* get(int key); 
    void put(int key, int value); 

    int hashFn(int val){ return val % 13; } 
}; 

HashMap::~HashMap(){ 
    for(int i = 0; i < SIZE; ++i){ 
     list<Node*>& val = data[i]; 
     for(list<Node*>::iterator it = val.begin(); it != val.end(); it++){ 
      Node* n = *it; 
      delete n; 
     } 
    } 
}

对于古玩：完整的代码是在这里：http://rextester.com/EHPCYW12862

编辑：

而且，我真的需要调用list.clear（）到底（因为我已经释放列表中的所有节点）？

来源

2012-08-10 brainydexter

看起来不错，但就是它最好使用智能指针 – Andrew 2012-08-10 07:02:27

使用boost :: ptr_list，问题消失了。 – BatchyX 2012-08-10 07:02:34

为什么你不使用列表的向量呢？ – 2012-08-10 07:04:51

看起来put正在构建一个Node放入您的哈希表，关联key和value。没有必要使用list<Node *>，使用list<Node>代替它会更清洁。

list<Node> data[SIZE]; 
//... 
data[bucket].push_front(Node(key, value));

然后，你可以避免实现析构函数。

你的get函数仍然可以返回一个指针。

Node* HashMap::get(int key){ 
    //... 
    list<Node>::iterator it = data[bucket].begin(); 
    //... 
      if (it->key == key) return &*it; 
    //... 
    return NULL; 
}

如果你留下list<Node *>实施，那么你也应该实现一个拷贝构造函数和赋值运算符（the rule of three）。

来源

2012-08-10 07:10:34 jxh

我最初使用了一个节点。但是，当我试图再次“放置”相同的值时，我被要求覆盖该节点的值。我将如何做只使用节点？ – brainydexter 2012-08-10 07:13:07

你的'get'可以返回一个引用，允许你修改返回的'Node'。但更简洁，可能是一个私人'get_iter'，它返回迭代器，以便'get'和'put'都可以使用它。 – jxh 2012-08-10 07:15:04

正是我想的:)。但是，当找不到节点时，我无法通过引用返回NULL。所以像这样的东西是行不通的：'Node＆get（int key）' – brainydexter 2012-08-10 07:16:22

检查是否没有内存泄漏的最佳方法是使用不能泄漏的智能指针类。 shared_ptr<Node>或unique_ptr<Node>可能在这里，第一个为可复制地图，第二个为非复制地图。

但如果你必须使用原始指针（家庭作业？），有些东西是缺少的：复制构造函数和赋值运算符。没有他们要么禁用或实施，复制这个HashMap将产生悬挂指针（在其中一个地图被销毁后）。

来源

2012-08-10 07:07:11 hamstergene

表示同意。这里应该遵循三项法则。我被要求实现一个重点放在get（）/ put（）函数的哈希映射 – brainydexter 2012-08-10 07:08:51

清理很好。小点：

for(list<Node*>::iterator it = val.begin(); it != val.end(); ++it)

为了达到理由，最好使用前缀增量。后缀表单必须在增量之前给出迭代器的状态。这个对象将被立即丢弃。编译器可能会优化，但这取决于。

来源

2012-08-10 07:11:48

啊，是的，我了解了一段时间。感谢您指出了这一点。（我在上面的循环中使用了'++ i'） – brainydexter 2012-08-10 07:14:20

是否还需要调用list.clear（）？（请参阅我的编辑） – brainydexter 2012-08-10 07:15:07

对于int值，这并不重要。对于作为对象的迭代器来说，这更重要。 – 2012-08-10 07:15:44

看着扔你的代码，并注意到你正在使用一些架空结构。

这两个片段是等价

Node ** d = &(*it); 
if((*d)->key == key){ 
    return *d; 
} 

if((*it)->key == key){ 
    return (*it); 
}

来源

2012-08-10 07:29:33 Ulterior

啊是的！在面试时，我惊慌失措，不想将副本传递给指针。我后来意识到这一点:) – brainydexter 2012-08-10 07:33:30

从C++的链表中删除指针

回答

相关问题