c++ - std::transform 自定义树为新树

Question

我有一个树状数据结构定义为:

template<typename T>
struct node {
  T val;
  node<T>* parent;
  unique_ptr<node<T>> next_sibling;
  unique_ptr<node<T>> first_child;
};

template<typename T>
struct tree {
    ...
  private:
    unique_ptr<node<T> _head;
};

我还为树类定义了几个迭代器(前序、中序...)。

在给定树上使用 std::transform 有效:

tree<int> t;
...
std::transform(t.begin(), t.end(), t.begin(), [](){});

但是我知道想要有类似于 back_inserter 的东西来构建具有相同层次结构的新树:

tree<int> t_n;
std::transform(t.begin(), t.end(), my_inserter(t_n));

如何做到这一点？

Answer 1

好吧，这完全取决于您是否可以定义 back_inserter .

它可以做到，但不能 value_type = T .问题在于普通序列不包含足够的信息来重建树的形状(除了二叉堆等特殊情况)。

因此，您必须遍历组成节点值的不同值类型和有关树的形状的一些信息。我看到两个选项:

• 在 T ( boost::option<T> ) 周围使用可为空的包装器，并在每个节点之后序列化 next_sybling 和 first_child，如果不存在则为无，或者
• 使用一个额外的标志来指定节点是否有 child 以及是否有更多的 sibling ，比如std::tuple<T, bool, bool> .

然后您应该能够在插入器中重建树，使用预序迭代，最好是深度优先，但广度优先也可以。无论哪种方式，您都必须在插入器中保持与在读取迭代器中相同的迭代状态，因此这将是相当多的代码。