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

Question

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

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

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()，需要传入的child用std::move()移动。这暂时没问题，子节点已经被推入树中正确的位置。但是，此函数中的子变量现在是 nullptr，当我尝试将它传递给下一个函数调用时，我得到了不希望的行为。

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

我不想使用 shared_ptr 因为实际上没有任何共享所有权，而且它会大大降低功能。

我确定这是我没有正确考虑的设计问题。感谢任何帮助我解决这个问题的方法。

Answer 1

The problem is, my appendChild() function involves a std::vector.push_back(), which requires the child passed in to be moved with std::move(). This is ok for now, the child node has been pushed into the tree at the right position. However, the child variable within this function is now a nullptr, and when I try to pass it into the next function call I get undesired behaviour.

使用移动语义时，您需要确保已完成对正在移动的对象的访问。在这种情况下，只需对语句重新排序就可以解决问题。此外，我建议使用 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 return 对新建节点的 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]);
}

The other problem is that if I implement a getter method to retrieve the child node from the tree to bring it back into the scope of the function, it will also have to be moved and so its parent node in the tree will point to a nullptr.

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

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

再次注意，如果子列表的长度被修改，此引用可能变得不可用，因此您可能希望使用 std::unique_ptr::get 从 unique_ptr 对象中“提取”信息。或者，您可以直接 return 一个非智能指针。

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

How to build a binary tree of unique_ptrs working around std::move?

c++

tree

unique-ptr