C++ 返回一个对象或在函数内部更改对象

Question

我是 C++ 的新手，所以仍在学习中。我正在尝试编写一种算法来递归地构建树，我通常会根据下面的方法 1 来编写它，但是，当函数返回时它会生成 RandomTreeNode 的(我希望很深)拷贝，我担心调用它递归地，因此更喜欢方法 2。我的想法是否正确？

方法一

RandomTreeNode build_tree(std::vector<T>& data, const std::vector<funcion_ptr>& functions){
        if(data.size() == 0 || data_has_same_values(data)){
            RandomeTreeNode node = RandomTreeNode();
            node.setData(node);
            return node;
        }

        RandomTreeNode parent = RandomTreeNode();
        vector<T> left_data = split_data_left(data);
        vector<T> right_data = split_data_right(data);
        parent.set_left_child(build_tree(left_data));
        parent.set_right_child(build_tree(right_data));
        return parent;
    }

方法二

void build_tree(RandomTreeNode& current_node, vector<T> data){
    if(data.size() == 0 || data_has_same_values(data)){
        current_node.setData(node);
    }

    vector<T> left_data = split_data_left(data);
    vector<T> right_data = split_data_right(data);

    RandomTreeNode left_child = RandomTreeNode();
    RandomTreeNode right_child = RandomTreeNode();
    current_node.set_left_child(left_child);
    current_node.set_right_child(right_child);

    build_tree(left_child, left_data);
    build_tree(right_child, right_data);

}

Answer 1

有几项改进。

• 首先，您要复制一个 vector 。据我了解您的函数名称，您将 vector 分成两个 block ([left|right] 而不是 [l|r|lll|r|...])。因此，您可以只传递索引来指定范围，而不是每次都传递 vector 。

• 如果实现得当，方法 2 的内存效率会更高。所以，你应该改进它背后的想法。

• 最后，您可以使用辅助函数，这将更适合该问题(方法 1 和方法 2 的混合)。

下面是一些示例代码:

// first is inclusive
// last is not inclusive
void build_tree_aux(RandomTreeNode& current_node, std::vector<T>& data, int first, int last)
{
    if(last == first || data_has_same_values(data,first,last))
    {
        current_node.setData(data,first,last);
        // ...
    }

    // Find new ranges
    int leftFirst = first;
    int leftLast = split_data(data,first,last);
    int rightFirst = leftLast;
    int rightLast = last;

    // Instead of copying an empty node, we create the children
    // of current_node, and then process these nodes
    current_node.build_left_child();
    current_node.build_right_child();

    // Recursion, left_child() and right_child() returns reference
    build_tree_aux(current_node.left_child(),data,leftFirst,leftLast);
    build_tree_aux(current_node.right_child(),data,rightFirst,rightLast);
    /*
        // left_child() and right_child() are not really breaking encapsulation,
        // because you can consider that the child nodes are not really a part of
        // a node.
        // But if you want, you can do the following:
        current_node.build_tree(data,leftFirst,leftLast);
        // Where RandomTreeNode::build_tree simply call build_tree_aux on the 2 childrens
    */
}

RandomTreeNode build_tree(std::vector<T>& data)
{
    RandomTreeNode root;

    build_tree_aux(root,data,0,data.size());

    return root;
}