C++: Does this pattern have a name, and can it be improved?

Question

The motivation

Let's say I'm writing a Tree class. I will represent nodes of the tree by a Tree::Node class. Methods of the class might return Tree::Node objects and take them as arguments, such as a method which gets the parent of a node: Node getParent(Node).

I'll also want a SpecialTree class. SpecialTree should extend the interface of a Tree and be usable anywhere a Tree is.

Behind the scenes, Tree and SpecialTree might have totally different implementations. For example, I might use a library's GraphA class to implement a Tree, so that Tree::Node is a thin wrapper or a typedef for a GraphA::Node. On the other hand, SpecialTree might be implemented in terms of a GraphB object, and a Tree::Node wraps a GraphB::Node.

I'll later have functions which deal with trees, like a depth-first search function. This function should accept both Tree and SpecialTree objects interchangeably.

The pattern

I will use a templated interface class to define the interface for a tree and a special tree. The template argument will be the implementation class. For example:

template <typename Implementation>
class TreeInterface
{
    public:
    typedef typename Implementation::Node Node;

    virtual Node addNode() = 0;
    virtual Node getParent(Node) = 0;

};

class TreeImplementation
{
    GraphA graph;   

    public:
    typedef GraphA::Node Node;

    Node addNode() { return graph.addNode(); }
    Node getParent() { // ...return the parent... }

};

class Tree : public TreeInterface<TreeImplementation>
{
    TreeImplementation* impl;

    public:
    Tree() : impl(new TreeImplementation);
    ~Tree() { delete impl; }

    virtual Node addNode() { return impl->addNode(); }
    virtual Node getParent() { return impl->getParent(); }

};

I could then derive SpecialTreeInterface from TreeInterface:

template <typename Implementation>
class SpecialTreeInterface : public TreeInterface<Implementation>
{
    virtual void specialTreeFunction() = 0;
};

And define SpecialTree and SpecialTreeImplementation analogously to Tree and TreeImplementation.

My depth-first search function might look like this:

template <typename T>
void depthFirstSearch(TreeInterface<T>& tree);

and since SpecialTree derives from TreeInterface, this will work for Tree objects and SpecialTree objects.

Alternatives

An alternative is to rely more heavily on templates so that SpecialTree isn't a descendent of TreeInterface in the type hierarchy at all. In this case, my DFS function will look like template <typename T> depthFirstSearch(T& tree). This also throws out the rigidly defined interface describing exactly what methods a Tree or its descendents should have. Since a SpecialTree should always act like a Tree, but provide some additional methods, I like the use of an interface.

Instead of the TreeInterface template parameter being the implementation, I could make it take a "representation" class that defines what a Node looks like (it will also have to define what an Arc looks like, and so on). But since I'll potentially need one of these for each of the implementations, I think I'd like to keep this together with the implementation class itself.

What do I gain by using this pattern? Mostly, a looser coupling. If I'd like to change the implementation behind Tree, SpecialTree doesn't mind at all because it only inherits the interface.

The questions

So, does this pattern have a name? I'm using the handle-body pattern by storing a pointer to ContourTreeImplementation in ContourTree. But what about the approach of having a template-ized interface? Does this have a name?

Is there a better way to do this? It does seem that I am repeating myself a lot, and writing a lot of boilerplate code, but those nested Node classes give me trouble. If Tree::Node and SpecialTree::Node had reasonably similar implementations, I could define a NodeInterface interface for a Node in TreeInterface, and override the implementation of the node class in Tree and SpecialTree. But as it is, I can't guarantee that this is true. Tree::Node may wrap a GraphA::Node, and SpecialTree::Node may wrap an integer. So this method won't quite work, but it seems like there might still be room for improvement. Any thoughts?

Answer 1

Looks like a mixture of the Curiously Recurring Template Pattern and the Pimpl idiom.

In the CRTP, we derive Tree from TreeInterface<Tree>; in your code you're deriving Tree from TreeInterface<TreeImplementation>. So it's also as @ElliottFrisch said: it's an application of the strategy pattern. Certain parts of the code care that Tree conforms to TreeInterface, while certain other parts care about the fact that it uses the particular strategy TreeImplementation.

Is there a better way to do this? It does seem that I am repeating myself a lot

Well, it depends what your runtime requirements are. When I look at your code, the thing that jumps out at me is that you're using virtual methods — slooooow! And your class hierarchy looks like this:

Tree is a child of
  TreeInterface<TreeImplementation>

SpecialTree is a child of
  TreeInterface<SpecialTreeImplementation>

Notice that the fact that TreeInterface<X>::addNode() happens to be virtual has absolutely no bearing on whether TreeInterface<Y>::addNode() is virtual! So making those methods virtual doesn't gain us any runtime polymorphism; I can't write a function that takes an arbitrary instance of TreeInterfaceBase, because we haven't got a single TreeInterfaceBase. All we've got is a bag of unrelated base classes TreeInterface<T>.

So, why do those virtual methods exist? Aha. You're using virtual to pass information from the derived class back up to the parent: the child can "see" its parent via inheritance, and the parent can "see" the child via virtual. This is the problem that is usually solved via CRTP.

So, if we used CRTP (and thus didn't need the virtual stuff anymore), we'd have just this:

template <typename Parent>
struct TreeInterface {
    using Node = typename Parent::Node;
    Node addNode() { return static_cast<Parent*>(this)->addNode(); }
    Node getParent(Node n) const { return static_cast<Parent*>(this)->getParent(n); }
};

struct ATree : public TreeInterface<ATree> {
    GraphA graph;
    typedef GraphA::Node Node;

    Node addNode() { return graph.addNode(); }
    Node getParent(Node n) const { // ...return the parent... }
};

struct BTree : public TreeInterface<BTree> {
    GraphB graph;
    typedef GraphB::Node Node;

    Node addNode() { return graph.addNode(); }
    Node getParent(Node n) const { // ...return the parent... }
};

template <typename Implementation>
void depthFirstSearch(TreeInterface<Implementation>& tree);

At this point someone would probably remark that we don't need the ugly pointer-casting CRTP at all and we could just write

struct ATree {
    GraphA graph;
    typedef GraphA::Node Node;

    Node addNode() { return graph.addNode(); }
    Node getParent(Node n) const { // ...return the parent... }
};

struct BTree {
    GraphB graph;
    typedef GraphB::Node Node;

    Node addNode() { return graph.addNode(); }
    Node getParent(Node n) const { // ...return the parent... }
};

template <typename Tree>
void depthFirstSearch(Tree& tree);

and personally I would agree with them.

Okay, you're concerned that then there's no way of ensuring through the typesystem that the T the caller passes to depthFirstSearch actually conforms to TreeInterface. Well, I think the most C++11-ish way of enforcing that restriction would be with static_assert. For example:

template<typename Tree>
constexpr bool conforms_to_TreeInterface() {
    using Node = typename Tree::Node;  // we'd better have a Node typedef
    static_assert(std::is_same<decltype(std::declval<Tree>().addNode()), Node>::value, "addNode() has the wrong type");
    static_assert(std::is_same<decltype(std::declval<Tree>().getParent(std::declval<Node>())), Node>::value, "getParent() has the wrong type");
    return true;
}

template <typename T>
void depthFirstSearch(T& tree)
{
    static_assert(conforms_to_TreeInterface<T>(), "T must conform to our defined TreeInterface");
    ...
}

Notice that my conforms_to_TreeInterface<T>() will actually static-assert-fail if T doesn't conform; it will never actually return false. You could equally well make it return true or false and then hit the static_assert in depthFirstSearch().

Anyway, that's how I'd approach the problem. Notice that my entire post was motivated by the desire to get rid of those inefficient and confusing virtuals — someone else might latch onto a different aspect of the problem and give a totally different answer.