>> The most obvious way to implement this is to physically build a binary
>> tree. That requires either inheritance, or else doing something sly with
>> unions. (Or even being /really/ dirty and just having one node type, and
>> ignoring the unused fields.)
>
>    I don't see why you need different types of objects for such a binary
> tree. Each object can be identical to each other in structure. (If in
> some nodes some of the fields are unused, so what? It will still be
> significantly more efficient than dynamic binding.)

So 16 bytes of space overhead per node is worth it if you can avoid one 
indirect jump instruction? That seems like an odd trade-off from an 
efficiency point of view. (Program complexity is another matter...)

>    You don't need to mess with unions unless you really, really need to
> make the objects as small as physically possible.

Granted. That's why I wasn't going to try to do that.

>> Now for the /encoding/ part itself, I don't actually need a physical
>> tree. I have a vague recollection that last time I did this, I ended up
>> cheating and just storing a vector of codewords, and manually munging
>> that. It's a lot less elegant, but avoids dynamic allocation. (Or
>> rather, no it doesn't, but it hides it in STL containers, so you don't
>> have to do it manually.)
>
>    Using an array of objects (rather than individually allocated objects)
> doesn't completely avoid memory allocation, but it minimizes their amount,
> which is often very significant. (In other words, if your program makes
> 20 allocations instead of a million, it will have a significant impact
> on the speed of the program.)

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?

>    If you really must have nodes of differing types, then it will become
> complicated from the point of view of memory management. Lack of garbage
> collection can be a b**** sometimes.

Ah well, that's why all large-scale applications are developed in C++, 
right? Because it doesn't force you to have garbage collection.

>    It's sometimes quite a bummer, but when writing efficient C++ you have
> to always think "how many memory allocations will this perform?"

Right. So what you're saying is that it's not dynamic binding /itself/ 
which is slow, but rather the dynamic allocations which necessarily go 
with it. (?)

>    Avoiding dynamic binding does not automatically mean that your program
> becomes more complicated and harder to maintain. In fact, it can sometimes
> mean the opposite. Sometimes your programs actually become *simpler* and
> much easier to understand. Full OOP (beyond simple encapsulation using
> classes) is not always the universal panacea for clarity and maintainability.
> (Of course this depends on each individual case.)

I usually find the OOP approach to be a good one. (Not always, of 
course.) Whether that's the type of code I write or what, I don't know.

Out of curiosity, if /you/ were writing a piece of code that's supposed 
to take a text string, parse it as an expression, and then execute the 
resulting expression, how would you implement that? The most obvious way 
is to make every valid kind of expression be a different class, and have 
an abstract base class with an "execute this" method, which gets 
implemented differently for each type of expression. But this 
necessarily involves dynamic binding and dynamic allocation, which you 
seem to make out is the Ultimate Evil to be avoided at all costs. So how 
would you do it?

(The obvious alternative is to design a single type that contains every 
field that any expression type will ever need, and write a giant switch 
statement to analyse each node to figure out how to execute it - which 
is exactly what OOP was designed to get rid of.)

>    But even then you have to think which design is easiest in terms of
> memory management. The less you have to manage memory manually, the
> better. Your program becomes safer and simpler.

Not manually managing memory certainly /is/ simpler than manually 
managing memory. No arguments there! ;-)

>> The problem is, I want to copy some data, but since I don't know what
>> class it belongs to, I have no idea how big it will be.
>
>    I didn't understand your problem from that description alone.

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;
   }

If, however, the TreeNode class is abstract, obviously this won't work 
at all. I now need to know what the /actual/ type of t0 is before I can 
allocate sufficient space for it. (I'm also fuzzy on what happens when 
you try to delete a pointer - does it know what the "real" size of the 
object is, or does it use the declared type of the pointer?)

>>>     Now, writing a class that properly manages its dynamically allocated
>>> memory is a non-trivial task of its own.
>
>> Is that not just a case of allocating the memory correctly in the
>> constructor, and freeing it properly in the destructor? (I mean,
>> assuming nobody tries to copy the object or free its dynamic memory or
>> anything like that...)
>
>    The simplest design is to delete the allocated memory in the destructor
> (it doesn't really matter where inside the class the memory is allocated
> as long as the pointer is kept as 0 when there's nothing allocated) and
> then disabling the copy constructor and assignment operators. (In C++98
> this is done by declaring them private and not implementing them. In C++11
> you can explicitly express this with a keyword.)
>
>    Often this is enough. However, sometimes you would want to be able
> to copy and assign objects of that class type around. That's where the
> non-triviality kicks in.

Right. Yeah, I can see how that might get confusing - especially if 
you're trying to minimise actual data copying...

Post a reply to this message