ここ数週間、イテレータについて学んできました。リンクリストを反復することと、リンクリストをトラバースすることの主な違いをまだ理解していません。トラバースとはリンク リストを通過する (すべての要素にアクセスする) ことを意味し、反復するときは基本的に同じことを行いますが、何が違うのか、なぜすべて (標準ライブラリのデータ構造) を反復できないのでしょうか?
11283 次
5 に答える
27
「トラバーサル」とは、データ構造の (すべてまたは一部の) 要素をたどることを意味します。
歴史的に、コンピュータ サイエンスにおける「反復」は、追加のスタック スペースを必要としない特別な形式の再帰です1、つまり末尾再帰です。この形式は、計算上、現在私たちが口語的に「反復」として知っているもの、つまり有限ループ (for固定された下限と上限を持つループなど) とまったく同じです。
これにより、反復は (一般的な再帰と比較して) 線形データ構造のトラバースに特に適しています2。すべてのコンテナー (一般的なグラフなど)では機能しないことに注意してください。これは、既にアクセスしたノードを記憶する必要があるためです (たとえば、反復子の C++ の概念ではなく、隣接するノードに関して再帰的に定義される深さ優先検索を使用する)。 ）。
コンテナーに適用される C++ で「反復」という用語が使用されるのは、このコンテキストです。
要約すると、すべてのトラバーサルが反復ではありませんが、(データ構造に対する) すべての反復がトラバーサルです。ただし、多くの人がそのような区別をせず、用語を同じ意味で使用していることに注意してください。
1特に、これはSICPで有名な Gerald Sussman の用法です。
2しかし、ツリーなどの一見非線形のデータ構造は、右手の法則 (壁追従アルゴリズム)を適用することで反復の目的で線形化できるため、スタックなしでトラバースできます。
于 2013-05-01T22:45:29.923 に答える
5
注: この定義は作成したばかりですが、私のメンタル モデルに合っているので、そのまま使用します。
反復は離散的であり、トラバーサルは離散的である場合とそうでない場合があります。そのため、スピーカーのアナログ ボリューム ノブで許容ボリュームの範囲をトラバースすることはできますが、それらを繰り返すことはできません。
しかし、反復はトラバーサルの一種です。したがって、すべての反復はトラバーサルですが、すべてのトラバーサルが反復であるとは限りません。
于 2013-05-01T22:56:34.793 に答える
3
私はiterator「エージェント」とtraverse「アクション」と呼んでいます。実際、人々がtraversing何か以上のものを何かと呼ぶとき、私はしばしば混乱iteratingします (私にとってiterationは、反復によって数学的点に向かって収束している数値的方法に関連しているためです)。一方で、私でさえ言葉を同じ意味で使っています。
iterateの概念がないコンテナをオーバーすることはできませんtraversal。少なくとも、何かをするためにtraverseは、少なくとも隣人がいるかどうか、そしてそこにたどり着く方法を知る必要があります。
于 2013-05-01T22:47:42.563 に答える