0

在我的应用程序中，我有一个（不平衡的）树数据结构。这棵树只是由“std::list of std::lists”组成 - 节点包含子节点的任意“列表”。使用它而不是单个列表使应用程序的其余部分变得更加容易。（该程序是关于将移动节点从一棵树更改为另一棵树/树中的另一部分/到它自己的树）。

现在一个明显的任务是在“树”中找到一个子树。对于非递归搜索，它很简单：

subtree_iterator find_subtree(const N& n) {         
    auto iter(subtrees.begin());
    auto e(subtrees.end());
    while (iter != e) {
        if ((*iter)->name == n) {
            return iter;
        }
        ++iter;
    }
    return e;
}

它将迭代器返回到子树位置。然而，当我尝试实现多级搜索时，问题就开始了。即，我希望搜索hello.world.test点标记新级别的位置。

搜索工作正常

subtree_iterator find_subtree(const pTree_type& otree, std::string identify) const {
    pTree_type tree(otree);
    boost::char_separator<char> sep(".");
    boost::tokenizer<boost::char_separator<char> > tokens(identify, sep);
    auto token_iter(tokens.begin());
    auto token_end(tokens.end());

    subtree_iterator subtree_iter;
    for (auto token_iter(tokens.begin()); token_iter != token_end; ++token_iter) {
        std::string subtree_string(*token_iter);
        subtree_iter = tree->find_subtree_if(subtree_string);
        if (subtree_iter == tree->subtree_end()) {
            return otree->subtree_end()
        } else {
            tree = *subtree_iter;
        }
    }
    return subtree_iter;
}

乍一看，它似乎“正确”工作，但是当我尝试使用它时，它失败了。使用它就像

auto tIn(find_subtree(ProjectTree, "hello.world.test"));
if (tIn != ProjectTree->subtree_end()) {
    //rest
}

但是，这会导致调试断言错误“列表迭代器不兼容”。这并不太奇怪：我正在比较来自不同列表的迭代器。但是我可以实现这样的事情吗？我的“备份”选项将返回一个std::pair<bool,iterator>布尔部分确定树是否实际存在的位置。除了制作整个树的单个列表之外，还有其他方法吗？

4

2 回答 2

1

您不应该在内部使用迭代器。改为使用节点。

template <typename T>
struct Node {
 T item;
 Node<T>* next;
};

然后将您的节点封装在一个迭代器外观中，如下所示：

template<typename T>
class iterator {
private:
  Node<T>* node;
public:
  ...
};

然后使用在达到或返回 end() 时返回的通用无效节点（当节点为 nullptr 时）。请注意，我建议的是单链表（不是标准的双链表）。这是因为您不能从指向无效空节点的无效通用 end() 迭代器返回。如果您不在算法中使用迭代器运算符--()，这应该没问题。

于 2012-11-27T12:49:24.933 回答
0

std::vector<list_iterator>堆栈遍历？堆栈的哪里.back()是唯一允许等于end()前一个的，并且.front()是根的迭代器list？

于 2012-11-27T13:25:19.870 回答