Breaking return-by-value recursive relationships

One of the classic problems in C++ is when you have two tightly interlocking classes, and you want to do something like this:

class A
{
   B getB();
};

class B
{
   A getA();
};

There are plenty of cases where something like this might come up. I ran into it because I was working with a topological mesh--I wanted Edges to return adjacent Faces, and Faces to return adjacent Edges. The problem with the above situation is that it's impossible. C++ won't allow you to return an undefined type by value, because it doesn't know the size of the undefined type and therefore can't compute the function signature. The classic solution is usually to do it by reference:

class A;
class B;

class A
{
   B &getB();
};

class B
{
   A &getA();
};

That works in cases where A and B refer to something which exists in some third location, but if A and B are constructed by the function itself, you're stuck again. So the third option is to return a pointer:

class A;
class B;

class A
{
   B *getB();
}

class B
{
   A *getA();
}

B *A::getB() { return new B; }
A *B::getA() { return new A; }

So far so good--except that now the caller of the get functions owns the memory, and we've taken a (potentially enormous) performance hit by touching the heap. We could alleviate the problem of memory ownership by using smart pointers, although that would likely double the performance hit, and is frankly an absurdly complicated solution for what ought to be a really simple problem.

The good news is that there exists a better way. The bad news is that it uses templates, which means that the code looks a lot like punctuation soup.

The basic idea is to have both A and B be specializations of a single template. Template specializations are interesting beasts, because there is no requirement that they have anything in common (as opposed to, say, class inheritance, which always packages everything from the base class into the child classes). The template parameter will be a dummy integer, and will be used purely to give A and B different type names. I'll use some typedefs to keep things readable, but they are optional. Here's how it looks:

template< int T > class BaseTemplate {};
typedef BaseTemplate< 0 > A;
typedef BaseTemplate< 1 > B;
// A
template<> class BaseTemplate< 0 >
{
public:
   BaseTemplate() {} // A constructor
   B getB();
}

// B
template<> class BaseTemplate< 1 >
{
public:
   BaseTemplate() {} // B constructor
   A getA();
}

inline B A::getB() { return A(); }
inline A B::getA() { return B(); }

This code will work! So, why does it work? The reason has to do with how templates are compiled. Templates delay the creation of function signatures until you actually use the template somewhere. This means that neither getA() nor getB() will have their signatures analyzed until after both classes A and B have already been fully declared. That's the magic of this method.

Unfortunately, there are a few inconvenient caveats associated with this trick. You can't define getB() inside the class, because B hasn't been declared yet. Attempting to declare it in the class will result in an error from using an undefined type. You can avoid these issues by always declaring all the member functions at the end of the header file, after all your interlocking classes are defined. Secondly, since this is a template, you must include all the member function definitions in the header file. If your class is complex, that can result in some rather ugly header file dependencies. You can work around that by having your member functions call through to a worker function as necessary:

B A_getB( A &a );
inline B A::getB() { return A_getB(*this); }

The worker function can be defined in a separate file, which can help break the header-file dependency loops. You'll probably need to friend the worker functions as well. You may have quite a lot of typing on your hands if you go this way.

So, is it worth the effort? That's going to depend on your project. In my case, I loved the results:

return my_edge.next().opposite().face(0).getVert(0);

This calls "next" on my_edge, which returns an edge; it then calls "opposite," which gets the edge on the other side, and then "face" which gets a face next to the edge. Finally, it gets vertex 0 from that face. Faces can return edges and vertices, edges can return faces and vertices, and vertices can return faces and edges. It's much nicer.