In c++ you use pointers very often, and they are the main reason for memory leaks and other problems. They allocate memory and if they are not deleted that is a memory leak. To avoid this problem the Smart pointers are to prefer.
A Smart pointer contains a Raw pointer – pointing to it, and it has the same size -, only the Smart pointer deletes the Raw pointer when it is no longer used. This means that you don’t have to worry about forgetting to delete it yourself.
This is an example from MSDNs website that shows the difference between the different pointer types:
The Smart pointer is then used just as a Raw pointer with the operators -> and *, but it has also got its own member functions which you can reach by using the dot like; smart_pointer.member_function();
This is a very useful pointer and I will absolutely be reading more about this and start to use Smart pointers instead of Raw pointers. But this is as far as I have gotten in researching this topic so far!
When using Visual Leak Detector (vld) there are some problems you might encounter. The problem (I thought I had) was that it wouldn’t show what file and line number it found the memory leaks in. No matter how much I searched for this on google no one seemed to give me an answer that worked.
When the running was done the top line of the vld output said (inside the green rectangle): “0x0F37C260 (File and line number not available): MSVCR120D.dll!operator new”. And where “File and line number not available” is; I thought the actual file and line number was supposed to show. This is however not the case!
It is the line after that which tells you where the leak is (inside the orange rectangle). The text before the orange arrow tells you which file has the leak, and the number the arrow is pointing to is the line number in the file. The text after the number tells you which method the leak is in. Then it’s just finding and correcting the leak and you’re done!
This week in programming we have learnt about Binary Search Trees (BST). While creating the program for a BST recursion is a great method to know and to use. Recursion is when a method calls itself from inside. You can read more about it on wikipedias page about recursion: http://en.wikipedia.org/wiki/Recursion_%28computer_science%29
I thought I could go through how I wrote my code to find the node to erase in the tree and why I chose to do it in that way. Let’s begin with the parameters; I send in a generic value – the value of the node that I want to erase, and two nodes. The first node is the one the function should check if it’s the one to erase and the second is the node the function checked the last time. Why I want the parent node is for when I erase a node I need to change the pointer pointing at it from its parent. I won’t explain how I erase the nodes in this blogpost since that isn’t really relevant to the recursion. And if you really want to know more about BSTs and how you remove nodes you can read about it in this Wikipedia page: http://en.wikipedia.org/wiki/Binary_search_tree
The first time this method is called the first node is the root node – the node that is in the top of the tree, before this method is called I check that there actually is a root node else the tree is empty and there are no nodes to erase. And the second node is a null pointer since there is no node pointing to the root.
The first thing I check is that the node to check is not a null pointer since that would mean the function has reached the end of the tree and has not found the right value. If that happens I return false so the recursion will stop and this false will tell my program that the value was not found and it will write in the console something like “That value was not found, try again”.
If the node is not a null pointer I check if it’s value is the one I was looking for. If it was not I check if the value I am searching for is bigger or smaller than this nodes value. If it is bigger I call the function again sending the same value to find, the current nodes bigger child to be checked and the current node as the parent. If it’s smaller I send the smaller child instead of the bigger one. And the function starts from the beginning with the new parameters.
But if a node with the right value is found I have to check how many children it has. If it has one or no child I call another function to remove them and then I return true telling my program that the node was found and erased and it writes something like “The value was found and erased” in the console. And the recursion is done
But what I have done if the node has two children is to call a function that finds the value to replace the current nodes value with then change its value, and then I call the previous function again. But this time I send in the value of the node which value I copied to be found and erased, the node that is the current nodes smaller child to be checked and the current node as the parent. I don’t start looking from the top again because firstly it would be unnecessary since I know the node to erase is under this node, and secondly because the node found would only be the same node again since they have the same value.
When the previous function finds this value it will erase it as a node with one or no children! (If you don’t understand why, look at the second Wikipedia page I linked in the beginning.)