如何初始化嵌套结构的 unique_ptr（例如，对于二叉树）

Question

在现代 C++ 中，通常建议在处理二叉树时使用 unique_ptr 以使子树的所有权明确。例如，Elements of Programming Interviews 推荐：

template <typename T>
struct Node {
  T data;
  unique_ptr<Node<T>> left, right;
};

刚开始学习C++11的特性，想知道初始化某个结构对应的二叉树最方便的方法是什么。我的用例是为特定树编写单元测试。比如我要生成这棵树：

下面的确实可以，但是真的很麻烦：

// first attempt: temporary variables & high syntactic noise
unique_ptr<Node<int>> tmp_n1(new Node<int>{1, nullptr, nullptr});
unique_ptr<Node<int>> tmp_n2(new Node<int>{2, nullptr, nullptr});
unique_ptr<Node<int>> tmp_n3(new Node<int>{3, move(tmp_n1), move(tmp_n2)});
unique_ptr<Node<int>> tmp_n4(new Node<int>{4, nullptr, nullptr});
unique_ptr<Node<int>> root(new Node<int>{5, move(tmp_n3), move(tmp_n4)});

我希望实现的是摆脱临时变量，并在一个嵌套语句中初始化树。如果代码结构类似于树结构，那就太好了。但是，以下尝试失败并出现 "could not convert" 错误：

// second attempt: nested, but still a lot of syntax noise
unique_ptr<Node<int>> root(new Node<int>{5,
  new unique_ptr<Node<int>>(new Node<int>{3,
    new unique_ptr<Node<int>>(new Node<int>{1, nullptr, nullptr}),
    new unique_ptr<Node<int>>(new Node<int>{2, nullptr, nullptr})
  }),
  new unique_ptr<Node<int>>(new Node<int>{4, nullptr, nullptr})
});

关于如何以语法清晰、简洁、灵活的方式编写此类树初始化有什么想法吗？

Answer 1

感谢@Satus 的评论，我能够想出一些（现在可用的）辅助函数：

template <typename T>
unique_ptr<Node<T>> new_node(const T& data, 
                             unique_ptr<Node<T>> left = nullptr,
                             unique_ptr<Node<T>> right = nullptr) {
  return unique_ptr<Node<int>>(new Node<int>{data, move(left), move(right)});
}

这允许构建这样的树：

auto root =
  new_node(5,
    new_node(3,
      new_node(1),
      new_node(2)),
    new_node(4)
  );

我仍然不确定这是否是更有经验的 C++11 程序员会做的，但对我来说这是朝着正确方向迈出的一步。

Answer 2

这是一个使用 C++14 make_unique 的解决方案，左右子树的默认参数设置为 nullptr，以避免原始 new:

#include <iostream>
#include <memory>

template<class T>
struct Node;

template<class T>
using node_ptr = std::unique_ptr<Node<T>>;

template<class T>
struct Node 
{
    T data;
    node_ptr<T> left, right;

    Node(T const& value, node_ptr<T> lhs, node_ptr<T> rhs)
    :
        data(value), left(std::move(lhs)), right(std::move(rhs))
    {}
};

template<class T>
auto make_node(T const& value, node_ptr<T> lhs = nullptr, node_ptr<T> rhs = nullptr)
{
    return std::make_unique<Node<T>>(value, std::move(lhs), std::move(rhs));    
}

template<class T>
void print_tree(Node<T> const& node)
{
    std::cout << "{ ";
    std::cout << node.data;
    if (node.left) {
        std::cout << ", "; 
        print_tree(*(node.left));
    }
    if (node.right) {
        std::cout << ", "; 
        print_tree(*(node.right));
    }
    std::cout << " }";
}

int main()
{
    auto const root = make_node(
        5, 
        make_node(
            3, 
            make_node(1), 
            make_node(2)
        ), 
        make_node(4)
    );    
    print_tree(*root);
}

Live Example 也打印树。

Update：感谢@Jarod42 的评论，我将 print_tree 的签名更改为 Node<T> const&，这样它现在是 const-正确，您不必在任何地方键入 .get()。我还制作了一个 template-alias node_ptr<T> 以在实现中为 unique_ptr<Node<T>> 提供更简洁的符号。

如何初始化嵌套结构的 unique_ptr（例如，对于二叉树）

How to initialize unique_ptr of nested structs (e.g. for binary trees)

c++

binary-tree

initialization

unique-ptr

c++11