2

我写了这个哈希图（这是电话面试练习的一部分），new Node(key, value)当我放置一个元素时我会在其中做一个。我想确保在哈希图本身超出范围时进行清理。

我在这里错过了什么吗？有什么方法可以检查是否存在内存泄漏？

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() 吗（因为我已经释放了列表中的所有节点）？

4

4 回答 4

1

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

但是，如果您必须使用原始指针（作业？），就会缺少一些东西：复制构造函数和赋值运算符。如果没有禁用或实现它们，复制此 HashMap 将产生悬空指针（在其中一个映射被破坏后）。

于 2012-08-10T07:07:11.343 回答
1

似乎put正在构造 aNode放入您的哈希表中，将 and 关联key起来value。没有必要使用 a 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 *>，那么您还应该实现一个复制构造函数和一个赋值运算符（三规则）。

于 2012-08-10T07:10:34.963 回答
1

清理工作很好。小点：

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

出于性能原因，最好使用前缀增量。后缀形式必须在增量之前给出迭代器的状态。该对象将立即被丢弃。编译器可能会优化，但这取决于。

于 2012-08-10T07:11:48.737 回答
1

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

这两个片段是等价的

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

if((*it)->key == key){
    return (*it);
}
于 2012-08-10T07:29:33.920 回答