c++在遍历树时延迟返回结果

Question

我有以下树结构:

template<typename T>
class Tree : public std::enable_shared_from_this<Tree<T>>
{
public:
Tree(T data);
Tree(T data, std::vector<std::shared_ptr<Tree<T>>> children);
void add_child(std::shared_ptr<Tree<T>>& child);
void add_children(std::vector<std::shared_ptr<Tree<T>>> children);
void set_parent(std::shared_ptr<Tree<T>> parent)
{ this->parent = parent; }

const T get_data() const
{ return this->data; }
const std::shared_ptr<Tree<T>>& get_parent() const
{ return this->parent; }
const std::vector<std::shared_ptr<Tree<T>>>& get_children() const
{ return this->children; }
private:
T data;
std::shared_ptr<Tree<T>> parent=nullptr;
std::vector<std::shared_ptr<Tree<T>>> children;
};

template<typename T>
Tree<T>::Tree(T data): data(data)
{ }

template<typename T>
Tree<T>::Tree(T data, std::vector<std::shared_ptr<Tree<T>>> children): data(data)
{ 
this->add_children(children);
}

template<typename T>
void Tree<T>::add_child(std::shared_ptr<Tree<T>>& child)
{
this->children.push_back(child);
child->set_parent(this->shared_from_this());
}

template<typename T>
void Tree<T>::add_children(std::vector<std::shared_ptr<Tree<T>>> children)
{
for (auto&& child : children)
{
this->children.push_back(child);
child->set_parent(this->shared_from_this());
}
}

我想创建一个函数find:

template<typename T>
generator<std::shared_ptr<Tree<T>>> find(const std::shared_ptr<Tree<T>>& t, T value);

你给一个树和一个值，它返回一个生成器，找到每个子树的根节点包含value。我的问题是，如何在c++中创建这个生成器?我研究了协同程序，但它们似乎过于复杂(或几乎任何事情)。我还试图考虑使用helper静态变量进行搜索，但我想不出一种不意外跳过节点的编码方法。

下面是创建树的帮助代码:

#include <vector>
#include <memory>
#include <iostream>
#include "tree.hpp"
std::shared_ptr<Tree<int>> create_tree()
{
// init tree and nodes
std::shared_ptr<Tree<int>> tree(new Tree<int>(1));
std::shared_ptr<Tree<int>> leaf1(new Tree<int>(5));
std::shared_ptr<Tree<int>> leaf2(new Tree<int>(4));
std::shared_ptr<Tree<int>> leaf11(new Tree<int>(3));
// construct tree
leaf1->add_child(leaf11);
std::vector<std::shared_ptr<Tree<int>>> v;
v.push_back(leaf1);
v.push_back(leaf2);
tree->add_children(v);
return tree;
}

int main() 
{
std::shared_ptr<Tree<int>> tree = create_tree();
return 0;
}

Answer 1

首先你不能在你的类中使用std::shared_ptr<Tree<T>>类型的parent。由于您在std::shared_ptr之间创建了循环依赖关系，并且它们永远不会被删除，因此会造成内存泄漏。您可以使用普通指针或std::weak_ptr，稍后可能是更好的选择，以保持统一的接口。在本例中，get_parent()函数是这样的:

std::shared_ptr<Tree<T>> get_parent() const
{ return this->parent.lock(); }

现在关于生成器，创建一个生成器非常简单。是的，你需要保留一些状态，但是对于树来说，不需要保留太多的状态。你可以这样做:

template<typename T>
struct generator {
generator(std::shared_ptr<Tree<T>> t, T v) : value(v), tree(t) {}
std::shared_ptr<Tree<T>> getNext() {
std::shared_ptr<Tree<T>> next = advance();
while (next != nullptr && next->get_data() != value) {
next = advance();
}
return next;
}
private:
std::shared_ptr<Tree<T>> advance() {
if (tree == nullptr) return nullptr;
// Special case for first entry
if (state.empty()) {
// If we don't have children, this is last chance
if (tree->get_children().empty()) {
return std::exchange(tree, nullptr);
}
state.push(0);
return tree;
}
// Going up, till next node, can be few levels
while (state.top() >= tree->get_children().size()) {
state.pop();
tree = tree->get_parent();
if (tree == nullptr) return nullptr;
}
std::shared_ptr<Tree<T>> child = tree->get_children()[state.top()];
if (!child->get_children().empty()) {
// Go deeper
state.top()++;
state.push(0);
tree = child;
return child;
}
state.top()++;
return child;
}
T value;
std::shared_ptr<Tree<T>> tree;
std::stack<size_t> state;
};

Answer 2

你应该为生成器类实现一个迭代器。