C++ 覆盖派生 class 的成员函数 returns 派生 class 的数组

Question

我正在尝试编写一个程序，从根节点开始搜索树中的节点。因为我希望搜索算法尽可能通用，所以我想使用模板，并且我想使用 SFINAE 来检查给定类型是否实现了我需要的所有功能。

要计算节点的后继节点，节点类型必须具有函数 successors()，其中 returns 节点向量：

#include <vector>

class has_successors_t {
public:
  virtual std::vector<has_successors_t> successors() = 0;
};

执行搜索的 class 如下所示：

#include <type_traits>

template <class node_t,
          class = std::enable_if_t<std::is_base_of<has_successors_t, node_t>::value>>
class breadthFirstSearch {
public:
    static node_t search(node_t root_node) {
        // search for the target node
    }
};

通过这种方式，我试图让程序仅在给定类型具有计算其后继者的函数时才能编译。但是当我尝试执行以下操作时：

#include <vector>

class some_node_t : public has_successors_t {
public:
  std::vector<some_node_t> successors() {
    // return the successors
  }
};

我得到一个错误：error: invalid covariant return type for 'virtual std::vector<some_node_t> some_node_t::successors()'。

所以，我知道错误是什么意思，但是我该如何解决这样的问题呢？我可以想象我不是第一个遇到问题的人，我有一个基础 class 和一个派生 class，我想在派生 class 中覆盖一个函数 [=39] =] 包含派生 class 元素的向量（或数组、队列或类似的东西）。但我就是找不到解决方案。

在此先感谢您的帮助！

您好，塞巴斯蒂安

Answer 1

您违反了基本的经验法则。运行 C++ 中的时间多态性又名 OOP 仅适用于指针或引用。如果你没有指针或引用，没有多态性，你根本不需要虚函数，甚至根本不需要 base classes。您可以直接在 successor 方法上使用 SFINAE，而不是在 class.

基础上

像这样的东西应该符合要求。

template <class N, 
     class = enable_if_t<is_same_v<vector<N*>,
        decltype(declval<N>().successors())>>> ...

以下假设您将拥有指针（智能指针或其他指针），因为按值处理节点可能不是一个有吸引力的提议。为了简洁起见，我将使用常规指针

您也许可以使用 CRTP 实现类似的功能。

template <typename S>
class has_successors_t {
public:
  virtual 
std::vector<S *> successors() = 0;
};

class some_node_t : public has_successors_t<some_node_t> {
public:
  std::vector<some_node_t *> 
successors() {
    // return the successors
  }
};

那么搜索功能就变成了

template <class node_t>
class breadthFirstSearch {
public:
    static node_t 
search(has_successors_t<tnode_t> * root_node) {
    // search for the target node
    }
};

然而，这意味着您将需要处理 has_successors_t<some_node_t> * 而不仅仅是 has_successors_t *。这就引出了下一个问题。如果您已经拥有 has_successors_t<some_node_t> *，为什么不更进一步，只拥有 some_node_t * 而完全放弃 has_successors_t。哎呀！我们又回到了 SFINAE 上 successors，这次只有指针。

CRTP 有一些用途，但您需要自己看看它是否适合您的设计。

C++ 覆盖派生 class 的成员函数 returns 派生 class 的数组

C++ overwritten member function of derived class returns array of derived class

c++

inheritance

stl

sfinae

container-data-type