C ++：这个模式有一个名字，可以改进吗？ [英] C++: Does this pattern have a name, and can it be improved?

问题描述

动机

假设我在写一个 Tree 类。我将通过 Tree :: Node 类来表示树的节点。类的方法可能返回 Tree :: Node 对象，并将其作为参数，例如获取节点父项的方法： Node getParent （Node）。

我还需要一个 SpecialTree 类。 SpecialTree 应该扩展 Tree 的接口，并且可以在树是

幕后， Tree 和 SpecialTree 可能有完全不同的实现。例如，我可以使用库的 GraphA 类来实现 Tree ，以便 Tree :: Node 是 GraphA :: Node 的一个thin wrapper或typedef。另一方面， SpecialTree 可以用 GraphB 对象和 Tree :: Node 包装一个 GraphB :: Node 。

具有处理树的功能，如深度优先搜索功能。此函数应接受 Tree 和 SpecialTree 对象。

< h2>模式

我将使用模板化接口类来定义树和特殊树的接口。模板参数将是实现类。例如：

  template< typename Implementation> 
 class TreeInterface 
 {
 public：
 typedef typename Implementation :: Node Node; 
 
 virtual Node addNode（）= 0; 
 virtual Node getParent（Node）= 0; 
 
}; 
 
类TreeImplementation 
 {
 GraphA graph; 
 
 public：
 typedef GraphA :: 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（）; } 
 
}; 
  

然后我可以从 SpecialTreeInterface c $ c> TreeInterface ：

  template< typename Implementation> 
 class SpecialTreeInterface：public TreeInterface< Implementation> 
 {
 virtual void specialTreeFunction（）= 0; 
}; 
  

并定义 SpecialTree 和 SpecialTreeImplementation 类似于 Tree 和 TreeImplementation 。

我的深度优先搜索功能可能看起来像这样：

  template< typename T& 
 void depthFirstSearch（TreeInterface< T>& tree）; 
  

且自 SpecialTree 派生自 TreeInterface ，这将适用于 Tree 对象和 SpecialTree 对象。 p>

替代方案

另一种方法是更多地依赖模板，使 SpecialTree 不是类型层次结构中的 TreeInterface 的后代。在这种情况下，我的DFS函数看起来像 template< typename T> depthFirstSearch（T& tree）。这也抛出刚性定义的接口，描述 Tree 或其后代应该有什么方法。由于 SpecialTree 应始终表现得像 Tree ，但提供一些额外的方法，像使用接口。

而不是 TreeInterface 模板参数的实现，我可以采取一个表示类，定义 Node 的样子（它还必须定义 Arc ， 等等）。但是因为我可能需要为每个实现这些之一，我想我想保持这一起实现类本身。

我该怎么做增益使用这种模式？大多数情况下，松耦合。如果我想改变 Tree 后面的实现， SpecialTree 根本不介意，因为它只继承

问题

那么，这个模式有没有名字？我通过在 ContourTree 中存储 ContourTreeImplementation 的指针来使用handle-body模式。但是，有一个模板化接口的方法呢？这有一个名字吗？

有更好的方法吗？看起来我重复了很多，并写了很多样板代码，但是嵌套的 Node 类给我带来麻烦。如果 Tree :: Node 和 SpecialTree :: Node 有合理类似的实现，我可以定义 在 TreeInterface 中为节点创建一个NodeInterface 接口，并覆盖节点类的实现在 Tree 和 SpecialTree 中。但是，因为它是，我不能保证这是真的。 Tree :: Node 可以包装 GraphA :: Node 和 SpecialTree :: Node 可以包装一个整数。所以这个方法不会工作，但似乎可能还有改进的余地。任何想法？

解决方案

看起来像是好奇地重复模板模式和 Pimpl成语 。

在CRTP中，我们从 TreeInterface< Tree> Tree c $ c>;在您的代码中，您从 TreeInterface< TreeImplementation> 中派生 Tree 。所以它也是@ElliottFrisch说：它是一个应用程序的策略模式。代码的某些部分关心 Tree 符合 TreeInterface ，而某些其他部分关心它使用特定策略 TreeImplementation 。

方法做到这一点？

好吧，这取决于你的运行时需求。当我看你的代码，跳出来的东西是我使用 virtual 方法 - slooooow！您的类层次结构如下所示：

  Tree是
的子节点TreeInterface< TreeImplementation> 
 
 SpecialTree是
的子节点TreeInterface< SpecialTreeImplementation>请注意， TreeInterface< X> :: addNode（） 
 
  刚好 virtual 对是否绝对没有影响 TreeInterface< Y& ）是虚拟的！所以使这些方法 virtual 不会获得任何运行时多态性;我不能写一个函数，它接受 TreeInterfaceBase 的任意实例，因为我们没有获得单个 TreeInterfaceBase 。我们得到的是一个无关的基类 TreeInterface< T> 。
 
 
 
  virtual 方法存在？ Aha。您使用 virtual 将信息从派生类传递回父级：子级可以通过继承查看其父级，父级可以查看孩子通过 virtual 。这是通常通过CRTP解决的问题。
 
 
 
因此，如果我们使用CRTP（因此不需要 virtual  stuff），我们只需要这样：
  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; 
 
节点addNode（）{return graph.addNode（）; } 
 Node getParent（Node n）const {// ... return the parent ...} 
}; 
 
 struct BTree：public TreeInterface< BTree> {
 GraphB graph; 
 typedef GraphB :: Node Node; 
 
节点addNode（）{return graph.addNode（）; } 
 Node getParent（Node n）const {// ... return the parent ...} 
}; 
 
 template< typename Implementation> 
 void depthFirstSearch（TreeInterface< Implementation>& tree）; 
  
在这一点上，有人可能会说我们不需要丑陋的指针我们可以写
  struct ATree {
 GraphA graph; 
 typedef GraphA :: Node Node; 
 
节点addNode（）{return graph.addNode（）; } 
 Node getParent（Node n）const {// ... return the parent ...} 
}; 
 
 struct BTree {
 GraphB graph; 
 typedef GraphB :: Node Node; 
 
节点addNode（）{return graph.addNode（）; } 
 Node getParent（Node n）const {// ... return the parent ...} 
}; 
 
 template< typename Tree> 
 void depthFirstSearch（Tree& tree）; 
  
，我个人同意。
 
 
 
 Okay，你担心的是，然后没有办法确保通过类型系统， T 调用者传递到 depthFirstSearch 实际上符合 TreeInterface 。嗯，我认为最强大的C ++ 11-ish方式强制执行这个限制将是 static_assert 。例如：
  template< typename Tree> 
 constexpr bool conforms_to_TreeInterface（）{
 using Node = typename Tree :: Node; //我们最好有一个Node typedef 
 static_assert（std :: is_same< decltype（std :: declval< Tree>（）。addNode（）），Node> :: value，addNode错误类型）; 
 static_assert（std :: is_same< decltype（std :: declval< Tree>（）。getParent（std :: declval< Node>（））），Node> :: value，getParent类型）; 
 return true; 
} 
 
 template< typename T> 
 void depthFirstSearch（T& tree）
 {
 static_assert（conforms_to_TreeInterface< T>（），T必须符合我们定义的TreeInterface 
 ... 
} 
  
注意我的如果 T 不符合，则conforms_to_TreeInterface< T>（）它永远不会返回 false 。你也可以让它返回 true 或 false ，然后点击 static_assert 在 depthFirstSearch（）。
 
 
 
无论如何，这是我如何处理的问题。注意，我的整个职位是由于想要摆脱那些低效和混乱的虚拟的动机 - 别人可能锁定问题的一个不同方面，给一个完全不同的回答。
 
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?
解决方案
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.

                        
这篇关于C ++：这个模式有一个名字，可以改进吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！