Invisible <voi### [at] devnull> wrote:
> On 14/03/2012 02:15 PM, Warp wrote:
> > Orchid Win7 v1<voi### [at] devnull>  wrote:
> >> So 16 bytes of space overhead per node is worth it if you can avoid one
> >> indirect jump instruction?
> >
> >    No, it's worth it if you can avoid one extraneous memory allocation
> > (or having to manage the allocated memory manually).
> >
> >    A memory allocation will easily consume those 16 bytes of extra space
> > anyways (the memory allocator bookkeeping, memory alignment, and the pointer
> > used to refer to the allocated object), so it's not like you are gaining
> > anything.

> Heh, really? Most languages I work with can allocate new objects in O(1) 
> time and using O(1) memory for bookkeeping. I'm not used to dynamic 
> allocation being anything to worry about.

  Last time I checked, 16 bytes is O(1) memory.

> >> Mmm, I hadn't even thought of using an /array/. I suppose the upper
> >> bound on the tree size is statically known, so why not?
> >
> >    The array doesn't necessarily have to be fixed in size.

> It does if it's static. Either that or the source I'm reading is 
> incorrect...

  You don't have to use a static array.

> Well, sure. If I was going to allocate, I don't know, one object for 
> every pixel on the screen, then sure

  But that's exactly what object-oriented design would have you do.

  Anyways, the major issue with dynamic allocation is memory management.
If by avoiding allocating individual objects manually you save yourself
the trouble of having to manage the memory, it's a win-win situation.
Why would you not want to do that?

> >> OK, well, if there is a single TreeNode class, I could write something like
> >
> >>     TreeNode(TreeNode t0, TreeNode t1)
> >>     {
> >>       child0 = new TreeNode;
> >>       child1 = new TreeNode;
> >>       *child0 = t0;
> >>       *child1 = t1;
> >>     }
> >
> >    Since TreeNode there is managing dynamically allocated memory, you'll
> > have to write a proper copy constructor and assignment operator or else
> > you have a leak and/or accesses to deleted memory. (And as I said in my
> > previous post, that's not trivial because of all the options you have.)

> How about if I never actually need to duplicate the tree? Does that make 
> things any simpler?

  You are copying TreeNode objects in the above code. If you want to do that,
there's no way around it: You have to write a proper copy constructor and
assignment operator for the TreeNode class, else you'll have leaks and
bad accesses.

  What do you think "*child0 = t0" means?

-- 
                                                          - Warp

Post a reply to this message