C++:指向数据成员或特征的指针？

Question

我正在用 C++ 练习一些二叉树算法，并尝试编写尽可能通用的代码。特别是，我希望我的函数(算法)能够对任何(当然在某种程度上)树状数据结构进行操作。

树节点结构可以用不同的方式定义，例如:

struct binary_tree_node
{
    int data;
    struct binary_tree_node *left;
    struct binary_tree_node *right;
};

或者像这样:

struct binary_tree_node2
{
    long key;
    struct binary_tree_node2 *first_child;
    struct binary_tree_node2 *second_child;
};

或者无论如何，但与该模式非常相似。 所以我希望我的函数/算法能够处理任何这些或类似的数据结构。

例如，这是我定义一个简单函数的方式:

template <typename TreeNode, typename DataType = typename TreeNode::data_type>
TreeNode*
binary_tree_new_node(DataType value = DataType(),
                     DataType  TreeNode::* data  = &TreeNode::data,
                     TreeNode* TreeNode::* left  = &TreeNode::left,
                     TreeNode* TreeNode::* right = &TreeNode::right)
{
    TreeNode *newnode = new TreeNode();
    newnode->*data  = value;
    newnode->*left  = nullptr;
    newnode->*right = nullptr;
    return newnode;
}

因此，可以将该函数与您选择的任何合适的树节点类型一起使用。如果数据成员有不同的名称(不是data、left 和right)，那么可以调用该函数并将指针传递给相应的数据成员。这样，该函数不依赖于(或者至少可以自行调整)输入类型的数据成员的命名方式。

到目前为止它工作得很好，但是随着我实现越来越多的函数，我对这些指向数据成员的指针参数感到厌倦，我必须将它们列为函数的可选参数。那么有没有更好的方法来处理这个问题呢？也许是某种特质？或者别的什么？

我希望对输入类型的要求尽可能少。例如，不应强制客户端程序定义除树节点类型之外的任何内容。它也不得被迫使用/派生自任何提供的类型或模板。当然，客户端程序可能会重复使用一些提供的模板，例如下面的模板，我也定义了这些模板，但实际上不应该被迫这样做。

template<typename T>
struct binary_tree_node
{
    using data_type = T;
    data_type data;
    struct binary_tree_node *left;
    struct binary_tree_node *right;
};

这里有哪些可用选项？ 它有任何意义吗？ :)

提前致谢

Answer 1

STL 集合库的工作方式是树库的作者将提供节点类，这样模板的所有用户需要做的就是提供数据。您似乎想要的另一个选择是侵入式数据结构(这对于谷歌搜索想法来说是一个很好的术语)。对于那些你有几个选择，第一个是要求数据成员是左、右和数据。其次需要具有特定名称的访问函数，以便模板可以找到它们。第三，要求将仿函数作为模板参数传入，以便您可以使用它们来查找所需的数据。就我个人而言，我发现 STL 方式最不困惑，其次是仿函数方式。