我是 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);
}
最佳答案
有几项改进。
首先,您要复制一个 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;
}
关于C++ 返回一个对象或在函数内部更改对象,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12919691/