self referential template parameters?

[SpeedBump]

This is mostly just another "gee it would be nice if it had X" post.

Recently I have come across two separate problems which both exhibit the
need for a way to self reference when instantiating a template.

Example #1: B-trees

While implementing a B-Tree I ended up with an (abbreviated) node structure
looking something like this:

template <class KeyType, class ChildType, int ORDER>
class BTreeNode {
public:
...
private:
KeyType key[ORDER-1];
ChildType child[ORDER];
};

for the assignment KeyType was a simple integer and the child type was an
offset into on-disk storage. While doing initial development I decided
what I would like to keep the tree entirely in memory (to make debugging a
bit simpler). This presents me with a problem. I need to use a template
to define itself (ChildType = BTreeNode<int,ChildType,32>). erk.

I resigned myself to the idea that this was just an unusual situation and
implemented a special BTreeSelfNode for use when in memory...a hack but it
kind of works.
Example #2: Functors (function objects)

A few weeks later I run across a situation where I need to handle function
pointers to member functions of a class. I think "functors" and begin
writing a fairly standard set of wrapper classes, looking something like
this:

class FunctorBase {
public:
virtual void callFunction();
};

template <class BaseType, class ParamType>
class Functor : public FunctorBase {
public:
Functor( BaseType &obj, BaseType::*mfp, ParamType param ):
m_obj(obj),m_mfp(mfp),m_param(param) {};
virtual void callFunction() {
m_obj::*m_mfp(m_param);
}
private:
...
};

And all was right and good (assuming I remember the code vaguely correctly
here)...until I wanted to pass the functor object in as the parameter
(ParamType = Functor<Foo,ParamType>).

Hmm....so in the last month I've found two separate reasons to need such a
self referential template, but I don't think there is a way to define it
that a compiler will accept. It would appear *possible* for the compiler
to generate a concise symbol name for such a thing (say: Functor<Foo,^13>
^13 == self reference to symbol name starting 13 characters previous), and
it would seem possible to come up with a non-conflicting syntax for the
compiler (maybe: Functor<Foo,<1> >, <1> == self ref, up one template level,
that would be fun to read :P ).

Maybe I'm just sick and twisted, but it seems like something that would be
worth having. Also, suggestions on how to implement these self referencing
templates would be appreciated, since I doubt this extension will ever make
it into my compiler.

Thanks for your time
-Scott Tillman aka SpeedBump

[David B. Held]

"SpeedBump" <sp*******@speedbump.org> wrote in message
news:lE*********************@twister.southeast.rr. com...

[...]
template <class KeyType, class ChildType, int ORDER>
class BTreeNode {
public:
...
private:
KeyType key[ORDER-1];
ChildType child[ORDER];
};
[...]
I need to use a template
to define itself (ChildType = BTreeNode<int,ChildType,32>).
[...]

There is nothing stopping you from using a template class as
one of its own arguments. However, you can't create a recursive
class definition, because it has infinite size (imagine trying to
instantiate your example above). You could certainly store a
pointer to children of the same class, just like you can store a
pointer to a struct of the same type (which is necessary to
create a linked list node). However, you can't use the BTreeNode
as a ChildType, because BTreeNode is a template, and
ChildType is a non-template template argument. However, if
you really wanted to make a recursive node type, you could do
something like this:

struct BTreeNode
{
template <class KeyType, class ChildType, int ORDER>
class apply
{
typedef ChildType::apply<KeyType, ChildType, ORDER>
child_type;
private:
KeyType key[ORDER-1];
child_type* child[ORDER];
};
};

BTreeNode::apply<int, BTreeNode, 32> node;

I think this is easier with Boost.MPL.Lambda, but unfortunately,
I'm not fluent enough in that to speak it off the top of my head.
However, you should probably take a close look at MPL yourself.
Also, Google for Curiously Recurring Template Pattern or
Barton-Nackman.

Dave

---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.532 / Virus Database: 326 - Release Date: 10/27/2003