c++ - 如何围绕std :: move构建unique_ptrs的二叉树？

Question

我目前正在尝试创建一棵二叉树，它的每个节点都包含一个指向树中其他节点的 unique_ptr。我的问题是一个关于设计的问题：我不完全确定如何编写一个递归函数来构建这样的树，而无需对节点中包含的指针调用 move 以便将它们作为参数传递给下一个递归函数调用。

我有一个看起来像这样的函数：

void MParser::parseExpression(unique_ptr<Symbol>& parent, string expression){

    Scope mainScope = findMainScope(expression);
    unique_ptr<Symbol> child;
    
    if (mainScope.type == ScopeType::Atomic){

        child = buildAtom(expression);
        parent->appendChild(child);
        return;

    }else{

        child = buildOperation(mainScope.type);
        parent->appendChild(child);

        vector<string> operands = separateOperands(mainScope, expression);

        parseExpression(child, operands[0]);
        parseExpression(child operands[1]);
    }  
}

问题是，我的 appendChild() 函数涉及到一个 std::vector.push_back()，它要求传入的子级通过 std::move() 移动。现在没关系，子节点已被推入树的正确位置。但是，这个函数中的子变量现在是一个 nullptr，当我尝试将它传递给下一个函数调用时，我得到了不希望的行为。

另一个问题是，如果我实现一个 getter 方法来从树中检索子节点以将其带回函数的范围，它也必须被移动，因此它在树中的父节点将指向一个 nullptr .

我宁愿不使用 shared_ptr 因为实际上没有任何共享所有权，它会大大减慢功能。

我确定这是一个我没有正确思考的设计问题。感谢您对我如何解决此问题的任何帮助。

标签： c++treeunique-ptr

Answer 1

问题是，我的appendChild()函数涉及一个std::vector.push_back()，它需要传入的孩子被移动std::move()。现在没关系，子节点已被推入树中的正确位置。但是，这个函数中的子变量现在是一个 nullptr，当我尝试将它传递给下一个函数调用时，我得到了不希望的行为。

使用移动语义时，您需要确保已完成对被移动对象的访问。在这种情况下，只需重新排序语句就可以解决问题。此外，我建议std::vector::emplace_back直接调用移动构造函数，而不使用默认构造函数+移动赋值。

}else{

    child = buildOperation(mainScope.type);

    vector<string> operands = separateOperands(mainScope, expression);

    parseExpression(child, operands[0]);
    parseExpression(child operands[1]);

    parent->appendChild(child);

}

或者，您可以appendChild返回对新构造节点的 const 引用；只要确保在使用参考时不要添加更多的孩子。

}else{

    child = buildOperation(mainScope.type);

    const std::unique_ptr<Symbol>& currentChildHolder = parent->appendChild(child);

    vector<string> operands = separateOperands(mainScope, expression);

    parseExpression(currentChildHolder, operands[0]);
    parseExpression(currentChildHolder, operands[1]);
}

---

另一个问题是，如果我实现一个 getter 方法来从树中检索子节点以将其带回函数的范围，它也必须被移动，因此它在树中的父节点将指向一个 nullptr .

返回一个常量引用。这允许在不分配新对象的情况下访问节点，例如：

const std::unique_ptr<Symbol>& ParentSymbol::GetChild(size_t index)
{
    return m_children[index];
}

再次注意，如果子列表的长度被修改，此引用可能会变得不可用，因此您可能希望unique_ptr使用std::unique_ptr::get. 或者，您可以直接返回一个非智能指针。