2

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

可以说结构可以定义为：

// 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()

  • 任何人都可以提出一种典型/惯用的方式来处理这种非线性数据结构吗？
  • 可以/应该为这样的结构创建迭代器吗？如何？
4

1 回答 1

1

使用迭代器。

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

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

如果您想真正健壮，请为每个XPath 轴实现迭代器模式。

于 2013-10-21T18:24:13.400 回答