How to delete dynamically allocated struct consisting dynamically allocated array member in C++?

Question

I am doing my homework which requires me to implement a Trie Tree without using vector. I have a struc defined as following:

typedef struct{
    char _name;
    int32_t * _children;
    int32_t _children_size;
    int32_t _children_capacity;
    int32_t * _location;
    int32_t _location_size;
    int32_t _location_capacity;
} TrieTreeNode;

To reduce the memory use, I store all the pointers of TrieTreeNode into a global variable TrieTreeNode ** nodes_array. Then the _children member of each TrieTreeNode is just an array whose elements are int32_t indices to nodes_array.

For example, say we have TrieTreeNode * parent. To access its first child, we use nodes_array[parent -> _children[0]].

My question is how to delete the whole Trie Tree? I have tried the following approach (tail is the number of pointers nodes_array has):

void delete_node(TrieTreeNode *node){
    delete [] node -> _children;
    delete [] node -> _location;
}

void delete_tree(){
    for (int i = 0; i < tail; i++){
        delete_node(nodes_array[i]);
    }
    delete [] nodes_array;
    nodes_array = NULL;
}

However, when I used both -ps -l command and GDB to monitor the memory use of my program before and after deleting a tree, the memory only decreases a little bit. The RRS goes from 13744 to 13156, while it is only 1072 before I build the tree.

Any suggestions will be appreciated!

Why, instead of `delete_node`/`delete_tree` aren't you using destructors? And `typedef struct` is unnecessary in C++. — Algirdas Preidžius, Jan 25 '17 at 22:30
"To reduce the memory use, I store all the pointers of TrieTreeNode into a global variable TrieTreeNode ** nodes_array" Why do you think using a global variable reduces memory use? And why do you think reducing memory use is important? Also, C++ doesn't need that typedef. — , Jan 25 '17 at 22:30
@NeilButterworth I think it is not necessary either, but one requirement for this homework is to reduce the memory. I thought using a `int32_t` instead of 64 bit pointer could be more efficient. It can be wrong, so I expect your suggestions as well. — Jay Wang, Jan 25 '17 at 22:32
Whoever downvoted, please leave your comment so I can improve my future questions. Thank you. — Jay Wang, Jan 25 '17 at 22:34
@Jay data pointers are all the same size. Typically, solutions that use pointers are slower and take up more memory than ones that don't, though of course sometimes you must use pointers. — , Jan 25 '17 at 22:34
@NeilButterworth Yeah, so I thought instead of storing pointers in each node, storing a shorter index might help (there will be duplicate pointers). — Jay Wang, Jan 25 '17 at 22:36
Even if you are not allowed to use `std::vector` and smart pointer, begin to write your own classes to handle that, then build on that. — Jarod42, Jan 25 '17 at 22:47
@Jarod42 I assume you found the goal of the homework. The OP has to be done some analysis what is necessary to implement a tree: Nodes (already in work) and some helper structures like vectors or lists (still to be done). — Th. Thielemann, Jan 25 '17 at 23:09

Mikel F · Accepted Answer · 2017-01-25T22:41:32.813

1

You are not deleting the nodes, only the pointers within each node.

Consider this:

void delete_tree(){
    for (int i = 0; i < tail; i++){
        delete_node(nodes_array[i]);
        delete node_array[i];  // Delete the node itself.
    }
    delete [] nodes_array;
    nodes_array = NULL;
}

After calling delete_node to free the two pointers in each node, you should then delete the node itself delete node_array[i] to free up the remaining memory for each node.

Personally though, I am a fan of defining constructors and destructors for structures so that I don't have to remember to initialize everywhere I create them or do the extra deletion everywhere I might dispose of one.

edited Jan 25 '17 at 22:41

answered Jan 25 '17 at 22:34

Mikel F

3,567
1
21
33

Sorry I tried your code, but it doesn't work (I didn't downvote you tho). – Jay Wang Jan 25 '17 at 22:41
@JayWong Does it crash, or just fail to remove the memory? Based on what I see of your code, I am fairly sure that the nodes represent at least part of your leak. – Mikel F Jan 25 '17 at 22:45
No it doesn't crash. The RRS still doesn't change significantly. I am researching on the destructor for struct. – Jay Wang Jan 25 '17 at 22:53
1

@JayWong Please consider the possibility that the leak is happening in some other manipulation of your trie tree. – Mikel F Jan 25 '17 at 22:55
1

@JayWong I agree with Mikel F. A destructor on your structure will simplify the clean up, but also give it a constructor to initialize the `_children` and `_location` pointers to `nullptr` to prevent badness should the struct be destroyed without ever setting `_children` and `_location`. Also, know the [Rules about using an underscore in a C++ identifier](http://stackoverflow.com/questions/228783/what-are-the-rules-about-using-an-underscore-in-a-c-identifier) to prevent nasty surprises. And, of course, if at first you don't succeed, Trie, Trie again. – user4581301 Jan 25 '17 at 23:02
@user4581301 , Mikel H. Yes, thank you so much for your suggestions. I now also doubt there will be other memory leak in my code. It is my first time to write a C++ program. I will go to learn more about what you mentioned above. – Jay Wang Jan 25 '17 at 23:09
@JayWong Did I read this correctly? For your first C++ program you were set to writing a Trie? Jinkies! That's hardcore! Usually people are brought up to speed with "Make a calculator", "Make a resizable String" or "Make a linked list" first. You might want to play around with some simpler constructs to make sure you have C++ style memory management and the ideological differences between the other languages you know and C++ down first. For example, [familiarize yourself with RAII](https://en.wikipedia.org/wiki/Resource_acquisition_is_initialization). It can make your time with C++ easier. – user4581301 Jan 25 '17 at 23:19
@user4581301 Yeah I found this project is super overwhelming too. Since we have already taken data structure course in Java, the professor forces us to pick up C++ as soon as possible. I found manually releasing memory is painful and confusing, and just hope it will get better. Thanks for all the resources! – Jay Wang Jan 25 '17 at 23:37
@JayWong The big trick with C++ is rarely do you need to manage your own memory. Statically allocate where possible and try to use library containers where you can't. Take full advantage of constructors, destructors, and [smart pointers](http://en.cppreference.com/w/cpp/memory). – user4581301 Jan 25 '17 at 23:43

How to delete dynamically allocated struct consisting dynamically allocated array member in C++?

1 Answers1