Greg said:
I don't see this particular tree pattern arising from the current
implementation. It is on the right track, but one problem is that the
template generation requires both the "left" and "right" int parameters
to be zero in order to stop the instantiations. But as far as I can
tell that specialization is not enough to prevent _I from becoming
negative while _J is still positive. Another problem is that each
successive instantation of RDES_T adds a pointer type to the _property
type parameter. In other words, if the first RDES_T template is
instatiated with J = 10 and _property = int, then the last RDES_T would
be instatiated would be with J=0 and _property=int********** - which is
unlikely to be correct.
In the way it is used I and J always become zero... I did have that problem
before and maybe I posted the old code were J could have been negative but I
fixed it. But the code does compile(so I can't see how J could become
negative except maybe if J > I but since its recursive eventually J < I and
it will fail(Which it doesn't)). I will try to analyze it and see again
though.
I think I see your point about the pointer stuff. I'm not sure if it is
doing that or not but it was doing that until I fixed the problem with J
going negative. So its probably still doing that. This seems like it will
be an issue. I want Container to hold a vector of *pointers but I guess I
don't really need the * on the lement and property. But the problem seems
that when I define Properties... hell now I'm not even sure why I made any
of the parameters pointers ;/ Only think I need is to have RDES_T a pointer
so I have a pointer of vectors(the reason I do this is I simply don't want
vector copying the objects themselfs since I want to handle it... so I'd
rather it just handle the vector of pointer memory management and stuff.
So I removed all the * except for RDES_T... i.e.
private:
std::vector< RDES_T<_I - 1, _J - 1, _element, _property > * > Container;
public:
// A sub container to hold for the properties of this container
The class template also seems to be complicated than it could be; that
makes it harder to understand its code. For example the _property and
_element type parameters have no apparent purpose and certainly looks
like they could be eliminated. And what is the use of the vector as a
data member? Wouldn't it simplify matters if Property and Container
were the same type?
? Property and container are not of the same type? Container is a vector and
Property is just an inherited structure(its right notes are all "empty").
If you mean what container holds then it has pointes to
RDES_T<_I - 1, _J - 1, _element, _property >
while properties is just the template
RDES_T<0, _J-1, empty_class, _property > Properties;
these are two different things though. The first generating a "true" tree
structure while the second generates. Actually I just realized that I need
something else. I need properties to create a recursive structure in a more
complicated way. Though I think it doesn't matter for the discussion. Its
just a matter of specializing and using the right I,J in the recursive
process.
So how can I do this by removing those parameters? I had to have a way to
parameterize the "terminal" classes, which can be different. (i.e. I might
call the class as RDES_T<4,2, Some_Class, Some_Other_Class>)
But I surely don't know much about templates so if you have any suggestions?
I just did what I could to get the stuff to work and it happend to work...
so I could be doing things completely wrong or using inefficient means.
The names chosen are also a barrier to comprehension. For example, most
programmers would expect RDES_T to be a macro. It's not a familiar
acronym and generally only macros have all uppercased letters.
Furthermore, "RDES_T" is not English. So one can only guess what it
might mean. I would guess that it would have something to do with the
DES encryption standard. In fact I still don't know what it stands for.
Heh, thats ok... The name has nothing to do with the issue. Its an acronym
and doesn't bear any meaning to the issue. You can rename the class to
whatever you like.
I would suggest making the implementation look more like the tree
binary tree above. In that way anyone looking at this code will have
some confidence that the implementation matches the intended design.
Specifically each node in the binary tree would have, depending on
their position: both a left and a right sub node, a left subnode only,
or no nodes at all (when the node is a terminal node). Each node would
also maintain a left-right counter that is manipulated to form the
desired structure of the tree:
(3,3) = (LeftDepth, RightDepth)
/ \
(2,0) (3,2)
/ / \
(1,0) (2,0) (3,1)
/ / \
(1,0) (2,0) (3,0)
/ /
(1,0) (2,0)
/
(1,0)
For example, this pattern can be implemented with this class template:
template <int LeftDepth, int RightDepth, class T>
struct BTreeNode
{
BTreeNode<LeftDepth-1, 0, T> left;
BTreeNode<LeftDepth, RightDepth-1, T> right;
T content;
};
Ok, first your right about the left and right depths naming making it easier
to understand the tree structure... but your wrong in assuming that was the
exact pattern of the problem
Remember that there are two different
terminals depending on which end branch you are on... so a T won't cut it..
I want a T class to end on the left and an S class to end on the right. But
also remember that the actual right sides are vectors and contain many
branches. The tree was only an outline of the semantics but not the
semantics itself.
While your example is pretty simple and the names do make sense for a Btree
they do not model my problem well ;/ My actual tree is
(3,3) = (LeftDepth, RightDepth)
/ \
(2,0) (3,2)
\ / \
(1,0) (2,0) (3,1)
\ / \
(1,0) (2,0) (3,0)
\ / \
(1,0) (2,0) (3,0)*
\
(1,0)
Also, I was approaching it from my original model which had nothing to do
with a binary tree(well except that it had a recursive process in it.... but
not a very simple one)
Now, thing to remember about the above tree is that all notes that come from
a right branch are a different class(actually a vector of classes i.e. what
I'm calling a container) and all the that branch right are a properties
class.
all the (1,0)'s are terminal classes and of the same kind BUT (3,0)* is a
final terminating class of the right branches and is a class of its own too.
Now thing to note is that the classes (1,0) and (3,I) are of the fundamental
type except that (1,0) end the recursive process while (3,I) continue it).
See my original threads for code that demonstrates the problem(though it
might be more work to sort out all those details)... I also explain what
lead me to this problem of wanting to define a recursive structure using
templates.
Note how the BTreeNode template class encapsulates other instantiations
of the BTreeNode template. Of course at some point BTreeNode has to
have no other BTreeNodes as members. So two partial specializations of
BTreeNode stop the tree from growing forever:
// when RightDepth is 0 there is only a left subnode
template <int LeftDepth, class T>
struct BTreeNode< LeftDepth, 0, T>
{
BTreeNode< LeftDepth-1, 0, T> left;
T content;
};
Yes, this is what my main problem is about. I have to specialize but when I
do have to "rewrite" the whole class basicaly except for a few minor
changes(i.e. deleted the recursion on one side basicaly). There are many
many more methods and variables that the template will have... and by doing
the recursion each tree has those same functions and variables... actually
all will have those same functions except the end nodes. It seems if I
specialize then I have to basicaly copy the whole class. I was doing this
before manually 7 times and so if I have to do it 2... which isn't much
better because I can/have wrote a utility that just copys my base class and
then refactors it so it works and hence I only have to manage one class.
// when LeftDepth and RightDepth are both zero there are no
subnodes
template <class T>
struct BTreeNode<0, 0, T>
{
};
And now some simple accesses to make sure the nodes in this BTree are
where we expect them:
...
myNode.left.left.content = 3;
myNode.right.right.left.left.content = 6;
Now, I'm not saying this class should replace the existing
implementation. Rather it's just an example of some techniques that
could make the current implementation a bit more clear, and a bit more
simple. At least in my opinion.
Yeah, well the do make it clear in understanding the recursive process but
they then start to move away from the actual model I am trying to do. But
the problem is slightly more complex than just a simple Btree as I have
pointed out. Though thanks for going to the trouble... It does help in
clarifying some issues.
No, performance is unlikely to be an issue here. On the contrary,
templates generally offer excellent runtime performance by having
performing compile-time optimizations and precalculations.
yeah, I figured that but wasn't sure if using an empty class would do
strange things.
Thanks for your time.
Here are some more observations on the current implementation:
Whis is RDES_T's destructor virtual? It's unusual for a template class
to have virtual methods. Generally, a class template doesn't need them.
Ok, I didn't know that. Since it was a generalization from a non-templated
class I just kept that idea. But yeah, I suppose you are right specially
since I'm not inheriting anything in the recursive process(I as before
though)
The Count() method should be a const method:
size_t Count() const { return mContainer.size(); }
and its return to type should match mContainer::size()'s return type.
Why would it be different?
Because Container is a vector of variable size? Returning a const of the
size would say that the size doesn't change? the reason I return int instead
of size_t is I hate dealing with casting from size_t to ints when I have to.
One more minor point:
Constructors and destructors should not be declared with a "void"
parameter list. They should have no parameter list. A void parameter
list is a C-ism that is not meaningful in C++. In fact, it's somewhat
surprising that the compiler accepted a constructor and destructor
being declared in this way.
really? heh... why? whats wrong with saying void as a argument? isn't void
some_func(void) the exact same as void some_func()?
just some quick search gives
http://www.cmis.csiro.au/iap/liar2/node16.html
ofcourse thats not for C++ but surely there is some non compile/programming
language specific reason?
Thanks,
Jon
