在c ++中从链表中删除指针

I wrote this hash map (this was a part of telephonic interview exercise), where I do a new Node(key, value) when I put an element. I want to make sure I'm cleaning up when the hashmap itself goes out of scope.

我写了这个哈希映射(这是电话访谈练习的一部分),当我放置一个元素时,我做了一个新的节点(键,值)。我想确保当hashmap本身超出范围时我正在清理。

Did I miss anything in here ? Is there any way I can check if there is a memory leak ?

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

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;
        }
    }
}

For the curios: complete code is here: http://rextester.com/EHPCYW12862

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

EDIT:

Also, do I really need to call list.clear() in the end (since I've already deallocated all the nodes in a list) ?

另外,我真的需要最后调用list.clear()(因为我已经释放了列表中的所有节点)吗?

4 个解决方案

#1

It seems put is constructing a Node to put into your hash table, associating the key and value. There was no need to use a list<Node *>, it would have been cleaner to use list<Node> instead.

似乎把构建一个Node放入你的哈希表中,关联键和值。没有必要使用列表 ,使用list 会更清晰。

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

Then, you could have avoided implementing a destructor.

然后,您可以避免实现析构函数。

Your get function can still return a pointer.

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

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

If you leave the implementation with list<Node *>, then you should also implement a copy constructor and an assignment operator (the rule of three).

如果您使用list 保留实现,那么您还应该实现复制构造函数和赋值运算符(规则为3)。

#2

The best way to check if there is no memory leak is to use smart pointer classes that can not leak. shared_ptr<Node> or unique_ptr<Node> may do here, the first for the copyable map, the second for noncopyable one.

检查是否没有内存泄漏的最佳方法是使用无法泄漏的智能指针类。 shared_ptr 或unique_ptr 可以在这里执行,第一个用于可复制映射,第二个用于不可复制映射。

But in case you have to use raw pointers (homework?), there are things that are missing: copy constructor and assignment operator. Without them either disabled or implemented, copying this HashMap will produce dangling pointers (after one of the maps is destroyed).

但是如果你必须使用原始指针(作业?),有些东西是缺失的:复制构造函数和赋值运算符。如果没有它们被禁用或实现,复制此HashMap将产生悬空指针(在其中一个地图被销毁之后)。

#3

The cleanup is fine. Minor point:

清理很好。小点:

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

it is better to use prefixed increment for perf reasons. The postfix form has to give out the state of the iterator before the increment. This object will be immediately discarded. Compiler may optimize, but it depends.

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

#4

Looked throw your code and noticed you are using some overhead constructs.

看起来抛出你的代码并注意到你正在使用一些开销结构。

These two snippets are equivalent

这两个片段是等效的

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

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

#1