C++ (stl) と Java のイテレーター、概念的な違いはありますか?

StackOverflow https://stackoverflow.com/questions/56347

  •  09-06-2019
  •  | 
  •  

質問

少しの間離れていたので、古いメロンのほこりを払おうとしていた後、C++ に戻ってきました。

Java では、イテレータはメソッドを持つコンテナへのインターフェイスです。hasNext()、next()、remove()。hasNext() の存在はそれを意味します 限界という概念がある 横断中のコンテナの場合。

//with an Iterator
Iterator<String> iter = trees.iterator();
while (iter.hasNext()) 
{
    System.out.println(iter.next());
}

C++ 標準テンプレート ライブラリでは、イテレータは、operator++ およびoperator== をサポートするデータ型またはクラスを表すように見えますが、 限界という概念がない 組み込まれているため、次の項目に進む前に比較が必要です。通常の場合、2 番目の反復子がコンテナーの端である場合、ユーザーは 2 つの反復子を比較して制限をチェックする必要があります。

vector<int> vec;
vector<int>::iterator iter;

// Add some elements to vector
v.push_back(1);
v.push_back(4);
v.push_back(8);

for(iter= v.begin(); iter != v.end(); iter++)
{
    cout << *i << " "; //Should output 1 4 8
}

ここで興味深いのは、C++ ではポインターが配列への反復子であるということです。STL は既存のものを取り入れて、それを中心に慣例を構築しました。

これに私が見逃しているさらなる微妙な点があるでしょうか?

役に立ちましたか？

解決

はい、概念的な大きな違いがあります。C++ は、イテレータのさまざまな「クラス」を利用します。ランダム アクセスに使用されるもの (Java とは異なります) もあれば、順方向アクセス (Java など) に使用されるものもあります。他のものはデータの書き込みに使用されます（たとえば、 transform).

イテレータの概念については、 C++ ドキュメント:

  • 入力反復子
  • 出力反復子
  • 前方反復子
  • 双方向反復子
  • ランダムアクセス反復子

これらは、Java/C# のつまらないイテレータに比べて、はるかに興味深く強力です。これらの規約が C++0x を使用して成文化されることを願っています。 コンセプト.

他のヒント

おそらくもう少し理論的です。数学的には、C++ のコレクションは反復子の半開区間、つまりコレクションの先頭を指す 1 つの反復子とコレクションの先頭を指す 1 つの反復子として記述できます。 すぐ後ろに 最後の要素。

この規約により、さまざまな可能性が開かれます。C++ でのアルゴリズムの動作方法と同様に、アルゴリズムはすべて、より大きなコレクションのサブシーケンスに適用できます。Java でこのようなことを機能させるには、別のイテレータを返す既存のコレクションの周囲にラッパーを作成する必要があります。

イテレータのもう 1 つの重要な側面は、Frank によってすでに言及されています。イテレータにはさまざまな概念があります。Java イテレータは、C++ の入力イテレータに対応します。つまり、これらは読み取り専用の反復子であり、一度に 1 ステップずつのみ増分でき、後戻りすることはできません。

反対に、C++ のランダム アクセス イテレータの概念に正確に対応する C ポインタがあります。

全体として、C++ は、C ポインターや Java イテレーターよりもはるかに豊富で純粋な概念を提供し、さまざまなタスクに適用できます。

前述したように、Java と C# のイテレーターは、混合された位置 (状態) と範囲 (値) を記述しますが、C++ イテレーターは位置と範囲の概念を分離します。C++ イテレータは、「どこに行けるか?」とは別に、「今どこにいるか」を表します。

Java および C# のイテレータはコピーできません。以前のポジションを取り戻すことはできません。一般的な C++ イテレータでは可能です。

考慮する この例:

// for each element in vec
for(iter a = vec.begin(); a != vec.end(); ++a){
  // critical step!  We will revisit 'a' later.
  iter cur = a; 
  unsigned i = 0;
  // print 3 elements
  for(; cur != vec.end() && i < 3; ++cur, ++i){
      cout << *cur << " ";
  }
  cout << "\n";
}

プログラムの出力を確認するには、上のリンクをクリックしてください。

このやや愚かなループはシーケンスを通過し (前方反復子のセマンティクスのみを使用)、3 要素の連続するサブシーケンスをそれぞれ 1 回だけ出力します (最後にいくつかの短いサブシーケンスを出力します)。ただし、N 個の要素と、1 行あたり 3 個ではなく M 個の要素があると仮定すると、このアルゴリズムでも反復子の増分は O(N*M)、スペースは O(1) になります。

Java スタイルのイテレータには、位置を独立して保存する機能がありません。あなたはどちらかになります

  • (たとえば、反復時に履歴を保存するためにサイズ M の配列を使用すると、O(1) スペースが失われます)
  • リストを N 回走査する必要があるため、時間は O(N^2+N*M) になります。
  • または、GetAt メンバー関数で具体的な Array 型を使用すると、ジェネリック主義とリンク リスト コンテナー型を使用する機能が失われます。

この例では前方反復メカニズムのみが使用されていたため、次のようにリストを交換できました。 問題はありません. 。これは、検索、遅延初期化と評価、並べ替えなどの汎用アルゴリズムを作成する場合に重要です。

状態を保持できないことは、非常に少数のアルゴリズムが構築されている C++ STL 入力反復子に最もよく対応します。

配列要素へのポインタは、実際には配列への反復子です。

あなたが言うように、Java では、イテレータは C++ よりも基礎となるコンテナについての知識を持っています。C++ イテレータは一般的であり、 ペア 反復子の数は任意の範囲を表すことができます。これは、コンテナのサブ範囲、または複数のコンテナにわたる範囲にすることができます (「 http://www.justsoftwaresolutions.co.uk/articles/pair_iterators.pdf または http://www.boost.org/doc/libs/1_36_0/libs/iterator/doc/zip_iterator.html）または数値の範囲（を参照） http://www.boost.org/doc/libs/1_36_0/libs/iterator/doc/counting_iterator.html)

イテレータ カテゴリは、特定のイテレータで何ができるか、何ができないかを識別します。

私にとって根本的な違いは、Java イテレーターが項目間を指すのに対し、C++ STL イテレーターは項目を指すことです。

C++ イテレータは、ポインタの概念を一般化したものです。より幅広い状況に適用できるようになります。これは、任意の範囲を定義するなどの目的に使用できることを意味します。

Java イテレータは比較的愚かな列挙子です (ただし、C# ほど悪くはありません。少なくとも Java には ListIterator があり、コレクションの変更に使用できます)。

イテレータは、配列の内容を順番に繰り返すという単純な場合のポインタとのみ同等です。イテレータは、他の任意の数のソースからオブジェクトを供給することができます。データベース、ファイル、ネットワーク、その他の計算などから。

C++ ライブラリ (以前は STL として知られていた部分) のイテレータは、ポインタと互換性があるように設計されています。ポインター演算のない Java には、よりプログラマーにとって使いやすい自由がありました。

C++ では、最終的に 1 組の反復子を使用する必要があります。Java では、イテレータまたはコレクションを使用します。イテレータは、アルゴリズムとデータ構造の間の接着剤であると考えられています。1.5 以降用に書かれたコードでは、特定のアルゴリズムやデータ構造を実装していない限り、イテレータについて言及する必要はほとんどありません (ほとんどのプログラマは実装する必要がありません)。Java と同様に、動的ポリモーフィズムのサブセットなどは非常に扱いやすくなります。

違いについては良い答えがたくさんありますが、Java イテレータで最も気になる点、つまり現在の値を複数回読み取ることができない点が強調されていないように感じました。これは、多くのシナリオ、特にイテレータをマージする場合に非常に役立ちます。

C++ には、イテレータを進めて現在の値を読み取るメソッドがあります。その値を読み取っても反復は進みません。なので何度も読めます。これは Java イテレータでは不可能なので、最終的にはこれを行うラッパーを作成することになります。

補足:ラッパーを作成する簡単な方法の 1 つは、既存のラッパーを使用することです。PeekingIterator グアバから。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top