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

Question

Motivation

Say I'm writing a Tree class. I will represent the nodes of the tree with the Tree::Node class. Class methods can return Tree::Node objects and treat them as arguments, such as a method that receives the parent element node: Node getParent(Node) .

I also need the SpecialTree class. SpecialTree should extend the Tree interface and be used anywhere in a Tree .

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

Later I will have functions that deal with trees, for example, a depth search function. This function must accept interchangeable Tree and SpecialTree objects.

Sample

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

 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(); } }; 

Then I could get TreeInterface from TreeInterface :

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

And define TreeImplementation and TreeImplementation similarly to Tree and TreeImplementation .

My first depth search function might look like this:

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

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

Alternatives

An alternative is to rely more on templates so that SpecialTree not a descendant of TreeInterface in the type hierarchy at all. In this case, my DFS function will look like template <typename T> depthFirstSearch(T& tree) . It also produces a hard-coded interface that describes which methods a Tree or its descendants should have. Since SpecialTree should always act like a Tree , but provide some additional methods, I like using the interface.

Instead of the TreeInterface template TreeInterface , which is the implementation, I can force it to take a “presentation” class that defines what Node looks like (it will also need to determine what Arc looks like, and soon). But since I will potentially need one of them for each of the implementations, I think I would like to keep this together with the implementation class itself.

What can I get using this template? Basically, a weaker connection. If I wanted to change the implementation behind Tree , SpecialTree doesn't mind at all, because it only inherits the interface.

Questions

So, does this template have a name? I am using the handle-body template, storing a pointer to ContourTreeImplementation in ContourTree . But what about the approach to a templated interface? Does it have a name?

Is there a better way to do this? It seems like I am repeating and writing a lot of patterns a lot, but those nested Node classes give me problems. If Tree::Node and SpecialTree::Node had fairly similar implementations, I could define the NodeInterface interface for Node in TreeInterface and override the node class implementation in Tree and SpecialTree . But be that as it may, I cannot guarantee that this is true. Tree::Node can wrap GraphA::Node , and SpecialTree::Node can wrap an integer. So this method will not work, but it looks like there may still be room for improvement. Any thoughts?

Answer 1

Looks like a mixture of curiously repeating pattern template and pimpl idiom .

In CRTP, Tree is derived from TreeInterface<Tree> ; in your code, you get a Tree from TreeInterface<TreeImplementation> . Just like @ElliottFrisch said: this is a strategy template application. Certain parts of the code maintenance that Tree correspond to TreeInterface , and some other parts take care that it uses a specific TreeImplementation strategy.

Is there a better way to do this? I seem to be repeating a lot

Well, that depends on your runtime requirements. When I look at your code, what pops up on me is that you use virtual methods - slooooow! And your class hierarchy looks like this:

 Tree is a child of TreeInterface<TreeImplementation> SpecialTree is a child of TreeInterface<SpecialTreeImplementation> 

Please note that the fact that TreeInterface<X>::addNode() is virtual has absolutely no effect on whether TreeInterface<Y>::addNode() virtual! Therefore, using these virtual methods does not give us any polymorphism at runtime; I can not write a function that accepts an arbitrary instance of TreeInterfaceBase , because we do not have a single TreeInterfaceBase . All we have is a bag of unrelated base classes TreeInterface<T> .

So why do those virtual methods exist? Yeah. You use virtual to pass information from the derived class back to the parent: the child can "see" its parent through inheritance, and the parent can "see" the child through virtual . This is a problem that is usually resolved using CRTP.

So, if we used CRTP (and therefore no longer needed virtual material), we would only have 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 notice that we don't need the ugly CRTP CRTP casting, 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 agree with them.

Well, you are worried that there is then no way to ensure through the type system that the T calling on depthFirstSearch actually matches TreeInterface . Well, I think the most C ++ 11th way to provide this restriction would be with static_assert . For instance:

 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"); ... } 

Note that my conforms_to_TreeInterface<T>() will actually be static-assert-fail if T does not match; it will never return false . You can also return it true or false , and then click static_assert in depthFirstSearch() .

Anyway, how do I approach the problem. Please note that my entire post was motivated by the desire to get rid of these ineffective and confusing virtual - someone else can click on another aspect of the problem and give a completely different answer.