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 ).

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]

[...]
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