Destroying / clearing a "recursive" vector ?

The Partridge Family were neither partridges nor a family. Discuss.
binbinhfr
Posts: 78
Joined: May 9th, 2019, 10:57 pm

Destroying / clearing a "recursive" vector ?

Post by binbinhfr » March 10th, 2020, 5:48 pm

Hi Chili's adorators,

I have a class of the form :

Code: Select all

class Node
{
	Node();
	Node(const Node&) = delete;
	Node& operator=(Node&) = delete;
	Node(Node&& n) noexcept; // move operator
	~Node();
        (...)
        std::vector<Node> nodes;
};
I wonder if I have to do anything on nodes in the destructor of this Node class (like a nodes.clear()) ?

And if, in anotehr part of the program, I use "nodes.clear()" once, do I have to recurse this clear() all way down, or will everything be unalocated properly ?

I guess all is automatic, but I'm not sure...

thanks for your help.
Last edited by albinopapa on March 11th, 2020, 4:07 pm, edited 1 time in total.
Reason: Just added the [code][/code] tag around the code portion.

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Destroying / clearing a "recursive" vector ?

Post by albinopapa » March 11th, 2020, 4:27 pm

This is kind of a tricky one actually.

With std::vector, you do NOT have to call .clear() before it dies/goes out of scope. That's the short answer.

If you were to call node.nodes.clear(), all std::vectors in the Node objects contained would be destroyed recursively. The biggest thing to watch out for here is recursion depth. You can cause a stack overflow in some cases if your tree goes very deep.

So for instance if your doing something like
Parent
Node ( level 1 )
Node ( level 2 )
...
Node ( level 256 )
You may cause stack overflow, the depth in which you can recurse depends on how much stack memory is used up before the destruction and how much is needed for each recursion, so you may get hundreds or thousands before a stack overflow.

Essentially, what you are attempting is a linked list of vectors. Not sure how that works since your std::vector requires a Node template parameter and the Node class hasn't been completely declared at the point of std::vector<Node> nodes declaration. I would have figured the compiler would complain about not allowing incomplete types, but it's been awhile since I've attempted something like this. In the past, I've had to make my vector: std::vector<Node*> nodes, but this brings another issue in that destructors aren't called on pointers and std::unique_ptr won't allow incomplete types either. You can get around this by having a destructor in the class and perhaps that is why std::vector isn't complaining about it.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

User avatar
chili
Site Admin
Posts: 3948
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: Destroying / clearing a "recursive" vector ?

Post by chili » March 11th, 2020, 4:54 pm

Yeah, my instinct tells me that something like vector isn't going to like it due to incomplete type...
Chili

binbinhfr
Posts: 78
Joined: May 9th, 2019, 10:57 pm

Re: Destroying / clearing a "recursive" vector ?

Post by binbinhfr » March 11th, 2020, 9:00 pm

Hi guys, thanks for your help (and for the youtube channel Chili ! especially the Exapunks ones :-)))) )

I must admit that after reading your answers, I cannot figure out what to do (except for the useless call to clear()).
chili wrote:
March 11th, 2020, 4:54 pm
Yeah, my instinct tells me that something like vector isn't going to like it due to incomplete type...
Chili, can you explain what you mean : I tried to create this class, and for the moment it is working as intended. Did you suspect it could not even compile ?

But maybe, you understood what I want to do and will propose me another solution :
the fact is that I want to store a n-tree (a tree where each node can have any number of subnodes).

How would you do this ? Is there any predefined container for this ?

PS : Chili, I noticed that on latest video, your english language now seems to be more polite. Is it intended ? I was really appreciating the previous version : lots of laughs and a very good way for me to learn english non-technical words :-D (I'm french).

PPS : the email notifications of this forum does not seems to work, or is it ? I did not receive any email notifying me of your answers...

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Destroying / clearing a "recursive" vector ?

Post by albinopapa » March 11th, 2020, 11:42 pm

Wow, just tested it and it seems std::vector doesn't have the same requirements as std::unique_ptr. I didn't even have an explicit destructor.

I don't think there is an n-ary or n-tree type container in the STL.

If you get this finished, I'd like to take a look at the full code if you don't mind sharing it. This would be kind of neat to use as an AST tree for parsing a programming language.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

binbinhfr
Posts: 78
Joined: May 9th, 2019, 10:57 pm

Re: Destroying / clearing a "recursive" vector ?

Post by binbinhfr » March 12th, 2020, 1:16 am

albinopapa wrote:
March 11th, 2020, 11:42 pm
This would be kind of neat to use as an AST tree for parsing a programming language.
Ha ha, you're clever : that's exactly what I'm doing !!!
Create my own simple programming language for a game involving programmation of robots (ask Chili about Exapunks !!!! :-D )
I'll show you if I manage to finish this.

BTW, I transformed the vector of nodes into a list of nodes : was afraid about too many duplication of the vector array during construction of the tree.

User avatar
chili
Site Admin
Posts: 3948
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: Destroying / clearing a "recursive" vector ?

Post by chili » March 12th, 2020, 3:47 am

Oh shit that's dope. Playing exa also started giving me ideas about making something like that (as if I don't already have enough on my plate as it is). Would be interested in seeing this when you got some sort of playable demo going :D
Chili

binbinhfr
Posts: 78
Joined: May 9th, 2019, 10:57 pm

Re: Destroying / clearing a "recursive" vector ?

Post by binbinhfr » March 12th, 2020, 10:40 pm

chili wrote:
March 12th, 2020, 3:47 am
Oh shit that's dope. Playing exa also started giving me ideas about making something like that (as if I don't already have enough on my plate as it is). Would be interested in seeing this when you got some sort of playable demo going :D
I knew you would like it.
But I want to use a higher programming language, with variables, functions, blocks, etc...
I have an idea how to program this (a kind of "on the fly" interpreted compiler), but it will be very recursive (that's why I need a N-tree to store the code structure), and I wonder how to mix it in realtime with the classic game loop. And also with other programs running in parralel as I want to have several bots commanded by separate source code (like EXA in exapunks, but with a higher langage).

I'll probably have to go on the multithread side, don't you think ?
Unless I can figure out how a debugger works (being able to parse/execute step by step a potentially recursive code...).

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Destroying / clearing a "recursive" vector ?

Post by albinopapa » March 13th, 2020, 7:42 pm

Seems legit, build the AST once the program begins, only update it when the script is changed, each frame traverse the tree.

Debugging without stopping the game loop might be a "fun ( sarcasm )" task, but I'm sure just logging and skipping over further traversal would do the trick.
binbinhfr wrote:Ha ha, you're clever : that's exactly what I'm doing !!!
Well, not clever, just had a similar idea. I had an idea of making a shader language similar to HLSL for SIMD instructions for the CPU. In my scenario, I wouldn't need to change the shader on the fly, so I would just compile it once at the beginning of the program's launch. My ideas was to use a stack with pseudo registers emulating a CPU. It's quite the undertaking and I got confused a lot when trying to implement the emulator and just like all my other projects, it got placed on the back burner until I'm ready to make another attempt.

While I know emulation isn't going to be as fast as just writing straight SIMD code, I find it cumbersome to not only write, but take into account all the facets involved. Since a SIMD register can be 128 to 512 bits wide, for efficiency you need to take into account how many elements you are working with, if working with AVX or higher, you need to clear the upper part of the registers before doing anything that involves using the XMM part of the register, you need to handle alignment during loading and storing ( not a huge deal on modern CPUs, but every little bit helps I'm sure ).

I tried making a template version of this idea, it would be mostly a header only C++ library that developers could piece together. There would be no interpreting nor me having to come up with an AST nor compiling on my part, the C++ compiler would handling it all. The developer would be responsible for assigning registers for input and output, which is kind of where things started falling apart for me.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

binbinhfr
Posts: 78
Joined: May 9th, 2019, 10:57 pm

Re: Destroying / clearing a "recursive" vector ?

Post by binbinhfr » March 14th, 2020, 8:34 am

Nice idea. I'm no very familiar with these CPU stuff. I am planning a more classical language to program my robots. A full-function-oriented language very easy to modelize with a n-tree.
I made tests with the C++ multithreading possibilities. Never done that before. It's huge. And very funny to make things synchronize with mutex, etc...

Post Reply