我有一个树状数据结构定义为:
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));
如何做到这一点?
最佳答案
好吧,这完全取决于您是否可以定义 back_inserter
.
它可以做到,但不能 value_type = T
.问题在于普通序列不包含足够的信息来重建树的形状(除了二叉堆等特殊情况)。
因此,您必须遍历组成节点值的不同值类型和有关树的形状的一些信息。我看到两个选项:
- 在 T (
boost::option<T>
) 周围使用可为空的包装器,并在每个节点之后序列化 next_sybling 和 first_child,如果不存在则为无,或者 - 使用一个额外的标志来指定节点是否有 child 以及是否有更多的 sibling ,比如
std::tuple<T, bool, bool>
.
然后您应该能够在插入器中重建树,使用预序迭代,最好是深度优先,但广度优先也可以。无论哪种方式,您都必须在插入器中保持与在读取迭代器中相同的迭代状态,因此这将是相当多的代码。
关于c++ - std::transform 自定义树为新树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39362806/