removing pointers from linked list in c++

Question

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.

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

EDIT:

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

@AndersK : I wanted a fixed size array and not something that would grow. (Check out the link I gave for how I implemented it). There can only be `SIZE -1` number of buckets and hence I don't need the array to grow. — brainydexter, Aug 10 '12 at 07:06

score 1 · Answer 1 · answered Aug 10 '12 at 07:07

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.

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).

agreed. The rule of threes should be followed here. I was asked to implement a hash map with focus on get()/put() functions — brainydexter, Aug 10 '12 at 07:08

score 1 · Accepted Answer · edited May 23 '17 at 12:27

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.

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.

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).

edited May 23 '17 at 12:27

Community

1
1

answered Aug 10 '12 at 07:10

jxh

69,070
8
110
193

I initially used a Node. However, when I am trying to `put()` the same value again, I was asked to overwrite the value of that Node. How would I do that using a Node only ? – brainydexter Aug 10 '12 at 07:13
Your `get` could return a reference, allowing you to modify the returned `Node`. But cleaner, would probably be a private `get_iter` that returned the iterator so that both `get` and `put` could use it. – jxh Aug 10 '12 at 07:15
Exactly what I thought :). However, when the node is not found, I can't return NULL through a reference. So something like this would not work: `Node& get(int key)` – brainydexter Aug 10 '12 at 07:16
@brainydexter: Did the interviewer define the interface? If not, you can return a `bool`, and accept a reference to a `Node &` to populate. Or, return the address of the of the found `Node` with `&*iter`. – jxh Aug 10 '12 at 07:17
@user315052 No, I could define the interface. You lost me with your suggestion. Can you write the function definition to clarify ? Thanks – brainydexter Aug 10 '12 at 07:21
@user315052 Implemented it with `Node` only here: http://ideone.com/i91fQ. (Sidenote, I wonder why is ideone throwing a runtime error) – brainydexter Aug 10 '12 at 07:35
@user315052 I just wanted to confirm: If I were to use list data[SIZE], I don't have to implement the rule of threes since mighty c++ will take care of it for me ? – brainydexter Aug 10 '12 at 19:33
@brainydexter: Yes, because you don't need to implement your own destructor. The rule of 3 is essentially: if you need to implement a destructor for you class, you also need to implement a copy constructor and an assignment operator. – jxh Aug 10 '12 at 20:16

score 1 · Answer 3 · answered Aug 10 '12 at 07:11

1

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.

answered Aug 10 '12 at 07:11

Kirill Kobelev

10,252
6
30
51

Ah yes, I learnt that a while back. Thanks for pointing this out. (I did use `++i` in the loop above it :) – brainydexter Aug 10 '12 at 07:14
For an int value this does not matter. For iterator that is an object this is more important. – Kirill Kobelev Aug 10 '12 at 07:15
1

Dector of `list<>` will clean it up in any case. I would recommend not to call. – Kirill Kobelev Aug 10 '12 at 07:16

score 1 · Answer 4 · answered Aug 10 '12 at 07:29

1

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

answered Aug 10 '12 at 07:29

Ulterior

2,786
3
30
58

ah yes! At the time of interview, I was panicking and didn't want to pass a copy to a pointer. I realized this later :) – brainydexter Aug 10 '12 at 07:33

removing pointers from linked list in c++

4 Answers4