2

項目に兄弟項目 (階層内の同じレベル) があり、子項目 (階層の 1 レベル下) がある場合がある階層ツリー構造を考えてみましょう。

構造を次のように定義できるとしましょう。

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

私を悩ませたのはfor_each()、同じ構造に対して3つの機能があることです。しかし、彼らは彼らがどのように反復するかをよく説明しているので、私はそれを受け入れることにしました.

その後、すぐに、より多くのアルゴリズム ( 、 、 など) の必要性が生じたためfind_if、count_if設計any_ofに関して正しい方向に進んでいないと感じました。

私が考えることができる解決策の 1 つは、作業負荷を軽減するために、単純に次のように書くことです。

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 に答える