-2

I am trying to implement a n-ary tree for a project. The structure of the node is as follows, I specifically need to have the link to both the parent node and the children nodes of the said node for my requirements.

struct treeNode {
    struct treeNode* parentNode;
    std::list<struct treeNode*> childNode;
};

I am using a insertNode() function to create a node, which is a child node to a particular node which is passed through the argument. The implementation of the said function is as follows -

struct treeNode* treeImplement::insertNode(struct treeNode *pNode) {
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->parentNode = pNode;
    //std::cout << pNode->childNode.size() << std::endl;
    pNode->childNode.push_back(node);
    return node;
}

The root node is created at the time of object initialization through class constructor treeImplement() .

Now I am trying to test my code in the int main() by calling the insertNode() function. Here getCurrentNode() and setCurrentNode() are to read and write to a currentNode variable which keeps track of which node we are currently on.

treeImplement ti;
    std::cout << ti.getCurrentNode() << std::endl; // to check root node is succesfully created
    struct treeNode* t = ti.insertNode(ti.getCurrentNode()); 
    ti.setCurrentNode(t);
    std::cout << ti.getCurrentNode() << std::endl;

Running it gives a SIGSEGV error when I am trying to call the insertNode(). Debugging by commenting and un-commenting the implementation of the insert function, made me found that a specific line within the insertNode() is creating the issue.

pNode->childNode.push_back(node);

The function runs fine when I do something else(like assigning the child node pointer to a variable) instead of doing a std::push_back() to the list inside the struct through the pointer.

Now I found the solution to my problem in this previously asked question - segmentation-fault-when-accessing-a-list-inside-a-struct. But I still have some questions and need clarity. Basically the answers in the above link, suggest using new instead of malloc() as the malloc doesn't run any constructor(lack of which apparently causes the problem).

My main question is why do we need a constructor here? What precise function does the said constructor carries out, which is lacking when I am using the malloc? A particular answer in the above link said that the subobjects inside the struct are unitialised. I am unable to understand to what does that exactly mean? Calling a pNode->childNode.size() before doing any push backs gives a 0, which means that it is not as if some garbage value is within the list already.

shobhit
  • 91
  • 3
  • 12
  • 3
    In which C++ textbook were you instructed to use `malloc` in C++ code? Whichever textbook it is, it is very urgent that you immediately throw it away, shred it, and bury the remainders in some deep, deep hole that noone can find. Then, [get a better C++ textbook](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) that actually teaches proper C++, instead of C using C++ grammar. `malloc` is for C. This is C++, with objects. `malloc` is a C library function does not know anything about any C++ object, like the one you're trying to create. – Sam Varshavchik Aug 26 '23 at 13:11
  • 3
    The `malloc` function allocates memory. It *only* allocates memory. It will not construct any object, it will not invoke any constructors. That means the `childNode` object is unconstructed. Using it will lead to *undefined behavior*. – Some programmer dude Aug 26 '23 at 13:15
  • 1
    And as a general rule of thumb: If you ever feel the need to do a C-style cast (like you do with the result of `malloc`) then you should take it as a sign that you're doing something wrong. – Some programmer dude Aug 26 '23 at 13:16
  • 1
    *My main question is why do we need a constructor here?* -- `std::list childNode;` -- Do you believe that the `std::list` itself isn't going to need to be constructed? You still have to construct a `std::list`, regardless of what `T` is. By using `malloc`, you have a member, `childNode`, that is not a `std::list` but just a blob of memory that is not a `std::list`, but has the same memory footprint as a `std::list`. If I gave you a bunch of steel, tyres, a steering wheel, and engine parts dumped on the floor, is that a driveable car? – PaulMcKenzie Aug 26 '23 at 13:22
  • All objects in C++ must be initialised before they are used. This is a rule of C++, and it seems to me, a fairly easy one to understand. `malloc` does not initialise objects, a constructor does initialises the object(s). – john Aug 26 '23 at 13:28
  • @SamVarshavchik I am still learning c++ and my concepts regarding objects are not very clear. I know that the preferred way of dynamically allocating memory in c++ is using ```new``` but it never caused any issues in the past when I used one one instead of the other in small pieces of code. I was only interested in knowing what exactly goes behind the scene that's why I asked it. – shobhit Aug 26 '23 at 13:32
  • 2
    You need to stop thinking about *garbage values* and the like. That is not the correct way to understand C++. Using uninitialised objects results in *undefined behaviour*, this is a bad thing, and that is why you need to initialise your objects, – john Aug 26 '23 at 13:32
  • 1
    @shobhit The reason you got away with it previously was because *undefined behaviour* does not mean garbage values, it does not mean a crash, it does not mean your program will not 'work'. It means undefined behaviour. – john Aug 26 '23 at 13:33
  • @shobhit *but it never caused any issues in the past when I used one one instead of the other in small pieces of code* -- Then that was your mistake. You believed that things "working" meant that things were correct. Go back to the code you wrote that you claim worked, and add `std::cout << std::is_trivially_copyable();` where `T` is the type you used `malloc` on. If the output to that `cout` is 0, then your code was broken and you never realized it. You also have to `#include ` for you to see this issue. – PaulMcKenzie Aug 26 '23 at 13:33
  • @PaulMcKenzie What exactly is an object? I mean suppose when I use a integer data type which was defined inside a struct I am able to use it directly and I don't need object construction, then why do we need to do so when I am trying to use ```std::list```? – shobhit Aug 26 '23 at 13:36
  • 1
    @shobhit Here we are dependent on what you mean by 'use'. If you were to read that `int` then we are back in undefined behaviour (UB) territory again, but in this case writing to the `int` is OK. Everything is an object, even `int` but there are different types of object. – john Aug 26 '23 at 13:38
  • 1
    @shobhit -- *then why do we need to do so when I am trying to use std::list* -- Because a `std::list` is a *type*. It isn't just an `int`. It needs to exist to maintain the `int`'s it will manage. It seems you are still trying to fit the `C` square-peg into the `C++` round-hole. – PaulMcKenzie Aug 26 '23 at 13:38
  • [Here is an example](https://godbolt.org/z/oEnjKbje1). See the different output, depending on what the members of the `struct` are? An output of 0 means that the type is not trivially copyable, meaning `malloc` is off-limits in creating such an object. The one possible exception of using `malloc` is if you are using `placement-new`, which your code does not do (you are not subsequentally calling `new` with placement after the `malloc` is done). – PaulMcKenzie Aug 26 '23 at 13:46
  • @PaulMcKenzie _It needs to exist to maintain the int's it will manage._ Does that mean that since ```std::list``` itself needs to be allocated dynamically(to store values) that's why we need to create object? – shobhit Aug 26 '23 at 13:51
  • @PaulMcKenzie _It seems you are still trying to fit the C square-peg into the C++ round-hole_ Yes I am not a c++ expert, I have only recently picked it up again that's why I am asking the question in the first place. – shobhit Aug 26 '23 at 13:53
  • All of your questions are answered in every beginner C++ textbook. Unfortunately, Stackoverflow does not really work very well as a C++ textbook replacement, we only answer ***specific*** programming questions here. C++ is just too complicated. It cannot be effectively learned by reading a blog or watching a Youtube video, or doing coding puzzles. Any clown can upload a video or publish a rambling blog, even I can do that (and I did). You will only effectively learn C++ by getting a good C++ textbook that fully explain these fundamental concepts, that just can't be summarized in 1-2 sentences. – Sam Varshavchik Aug 26 '23 at 13:54
  • P.S. What gave you the idea that "std::list itself needs to be allocated dynamically"? Noone here stated that, and this is not true. There are plenty of `std::list`s, everywhere, that get created in automatic scope. See -- this is what I mean -- C++ is the most complicated and hardest to use general purpose programming language in use today. The only way to effectively learn it, and understand it fully, is by following an organized, textbook-guided curriculum that introduces and fully explains every concept, before moving on to the next harder one. – Sam Varshavchik Aug 26 '23 at 14:01
  • @SamVarshavchik I get your point, I need to learn it in a structural way. But my reasoning was that by definition a linkedlist creates new nodes whenever newer values are inserted to it and to do that at runtime you need to allocate memory dynamically. – shobhit Aug 26 '23 at 14:05
  • And a good textbook will explain that the objects, and its contents, are two completely independent entities. It is true that `std::list`'s contents are allocated dynamically. But this has nothing to do, whatsoever, with the `std::list` itself. It can be allocated dynamically, or not. Furthermore, `new` is the dynamic allocation for C++ objects, not `malloc`. `malloc` is for C, this is not C but C++. – Sam Varshavchik Aug 26 '23 at 14:08

0 Answers0