明らかな終わりのないコンテナにイテレータを実装することは理にかなっていますか？木？

Question

C ++の学習と最も一般的なアルゴリズムとデータ構造の学習という2つの理由で、バイナリ検索ツリーテンプレートを作成しています。
それで、ここに質問があります-イテレータを実装したい限り、どこでツリーが終了するかについての厳密な定義はないようです。あなたの提案は何ですか？どうすればいいですか？

Answer 1

ツリーの場合、ツリーをトラバースするための標準があります。つまり、ノードの列挙：事前順序トラバーサル、順序順トラバーサル、および順序後トラバーサルです。これらすべてをここで説明するのではなく、 http://en.wikipedia.org/wiki/Tree_traversal 。概念は主にバイナリツリーに適用されますが、さらにケースを追加することにより、アイデアを任意のツリーに拡張できます：事実上、ノードを処理してから再帰し、再帰してからノードを処理し、すべての子を処理してからそれぞれに再帰します...など。私が知っているこのアプローチの標準的な分類はありません。

Answer 2

イテレータを記述するときは、何か明確にする必要があります。データ構造のイテレータは、アイテムへの線形シーケンスとしてコレクションへのアクセスを提供します。配列、リスト、キューなどの特定のコレクションは、線形シーケンスとして扱われることと自然に互換性があります。他のタイプのコレクション-ツリー、辞書、グラフ-は、必ずしも線形リストとしての単純な解釈を持つわけではありません。実際、一般的に複数の解釈が有効です。

ツリーなどのコレクションのイテレータを作成するときに実際にすべきことは、次の問題に対処することです。

1. コレクションの反復はどこから始まりますか（ルート？
2. 次の要素への反復はどのように進行します（中置？後置？接尾語？幅？）
3. イテレーションはいつ終了しますか（終了しますか？ルート？最終ノード？）

選択するものは何でも、どのようにノードにアクセスして発行するかを明確にするために、イテレータの命名方法（および文書化方法）を非常に明確にする必要があります。

サポートする予定のさまざまな種類のトラベラルに対して、複数のイテレータを作成する必要がある場合があります。ここにいくつかの良い記事がありますツリートラバーサルモデル。

Answer 3

「厳格」とは、すべてを網羅する単一の定義である場合、その通りではありません。

ただし、選択しているトラバーサル方法に依存しますが、ツリーの「終了」は非常に明確に定義されています。

• 順序どおりに（または対称的に）トラバースする場合、右端の要素は end になります。
• 先行予約（または深さ優先）では、右端の要素は end などになります。
• ポストオーダーでは、ルート要素は end などになります。

最も一般的なツリートラバーサルメソッド。

Answer 4

イテレータの定義は少し間違っています。イテレータは、 start から finish にはならず、 front から back にもなりません。代わりに、その構造のすべてのメンバーに渡ります。

順序付けられた構造（配列、リンクリストなど）の反復を要求すると、（通常）メンバーが順番に返されます。

セットなどの順序付けられていないアイテムの場合、セットイテレータが提供したい順序でアイテムを取得しますが、すべてのアイテムを一度に1つずつ取得します。配列イテレータを使用します。

木に関しては、他の人々がすでに言及しています：彼らは完全な順序の明確に定義された概念を持っています、あなたはただ1つを選ぶ必要があります：）

Answer 5

ツリーをどのように処理するかによって異なります。たとえば、Breadth-First-SearchまたはDepth-First-Search（またはその両方）のイテレータがあればいいかもしれません。

ツリーを精査する特定の方法がある場合、実際には開始と終了があります。リストやセットの線形関係ほど明白ではありませんが、何らかの順序付けを行いたい場合は存在します。

Answer 6

そのような場合、特に意味があります。クラスのユーザーが、状況に応じてさまざまな方法ですべての要素を簡単に歩く方法を提供するからです。それらがなければ、ユーザーは複雑で、通常は再帰的な方法を自分で記述する必要があります。例と比較してイテレータがfor（i = 0; iを使用するよりもタイピングしているベクトル     

Answer 7

イテレータではより抽象的な方法だと思います。イテレータパターンには、開始または終了があると実際に言っているものは何もありません。それでは、なぜそのビジョンに制約されるのでしょうか。次の要素のみに関係するイテレータを想像できます。それだけです。つまり、（特に大量処理で）始めからコレクションの拡張がわからない、いつか終了するのかわからない、またはすべてが揃っていないという状況に直面している要素がメモリに読み込まれ、気にしません。次の要素を取得することのみを考慮します。これらの実装の1つでは、次の要素メソッドが呼び出された直後に次のノードが作成されます。私たちは心を開き、すべての数字のコレクション、すべての乱数のコレクションのように、無限のコレクション（最終的にコレクションは数学的セットの一種です）について考えることができます。実際にすべての要素をメモリに格納する必要はありません（無限のコレクションの場合は明らかです）。もちろん、これは実用的な例ではありませんが、私のメッセージは、イテレータのユーザーが実際のコレクションの構造や拡張に依存する必要がないということです。次をくれたら（もしあれば）。