c++ - 如何遍历非线性容器

Question

考虑一个分层树结构，其中一个项目可能有兄弟项目(在层次结构中的同一级别)，也可能有子项目(在层次结构中的下一级)。

假设结构可以这样定义:

// an item of a hierarchical data structure
struct Item {
    int          data;     // keep it an int, rather than <T>, for simplicity
    vector<Item> children;
};

我希望能够在此结构上使用算法，例如 std::map、std::vector 等的算法。因此，我创建了一些算法，例如:

template <class Function>
Function  for_each_children_of_item( Item, Function f );  // deep (recursive) traversal

template <class Function>
Function  for_each_direct_children_of_item( Item, Function f );  // shallow (1st level) traversal

template <class Function>
Function  for_each_parent_of_item( Item, Function f );  // going up to the root item

让我困扰的一件事是，同一个结构有 3 个 for_each() 函数。但他们很好地描述了他们如何迭代，所以我决定接受它。

然后，很快就出现了对更多算法的需求(如 find_if、count_if、any_of 等)，这让我觉得我在设计方面不在正确的轨道上。

我能想到的一个可以减少工作量的解决方案是简单地写:

vector<Item>  get_all_children_of_item( Item );         // recursive
vector<Item>  get_all_direct_children_of_item( Item );  // 1st level items
vector<Item>  get_all_parents_of_item( Item );          // up to the root item

然后我可以使用所有的 STL 算法。我对这个解决方案有点担心，因为它涉及到复制。

我想不出一种方法来实现 iterator，因为在遍历的递归版本中没有明显的 end() 迭代器。

• 谁能提出一种典型/惯用的方法来处理这种非线性数据结构？
• 可以/应该为这样的结构创建迭代器吗？怎么样？

Answer 1

使用迭代器。

I cannot think of a way to implement an iterator, as there is no obvious end() iterator in the recursive version of the traversal.

end() 可以是为您的迭代器类指定的任何特殊值，只要您的增量运算符在步过最后一个元素时生成它即可。和/或为您的迭代器覆盖运算符 ==/!=。

如果你想变得非常健壮，为每个 XPath axes 实现一个迭代器模式.