コグノスケ


link 未来から過去へ表示(*)  link 過去から未来へ表示

link もっと前
2014年5月1日 >>> 2014年5月1日
link もっと後

2014年5月1日

イテレータ

Javaを始めたときにコケたので思い出深いのですが、C++ とJavaってイテレータの概念が全然違いますね。

C++ のイテレータはコレクションの要素そのものを指しています。N個要素を持つ配列aのイテレータitであれば、a.begin() はa[0] を指し、itはa[0] からa[N - 1] の間まで有効な要素を指し続けます。a.end() は存在しないa[N] を指します。

C++ のイテレータ

begin()                                        end()
|                                              |
a[0]   a[1]   a[2]   ... a[N - 2]   a[N - 1]   a[N]
|      コレクションの有効範囲       |

C++ 方式の利点は、イテレータが何を指すのか直感的に理解しやすく、イテレータ経由での要素の書き換えや削除のイメージが沸きやすいことです。

欠点はbegin() は参照して良いのに、end() は参照してはいけない、という非対称な仕様になってしまうことです。例えば、逆転イテレータ(reverse_iterator)を実装するとbegin() をend(), ++ を -- として扱うだけでは作れずに、悲しい思いをします。

Javaのイテレータは要素と要素の「間」を指しています。Javaにbegin(), end() はありませんが、対比のため無理やり書くと下記のようなイメージです。

Javaのイテレータ

 begin() = iterator()                           end() = hasNext() がfalse
 |                                              |
   a[0]   a[1]   a[2]   ... a[N - 2]   a[N - 1]
   |      コレクションの有効範囲       |

Java方式の利点はbeginとendが対称的になることです。もうbeginとendで悲しい思いをすることはありません。

欠点は書き換えや削除の対象がわかりづらいことです。特に双方向イテレータ(ListIterator)が顕著なので、もう少し詳しくご紹介しましょうか。

Javaコレクションの仕様ではイテレータが「最後に返した要素」が書き換え(set)や削除(remove)の対象、となります。ListIteratorは進む/戻るのどちらもできますから、イテレータの現在位置の「直前」あるいは「直後」どちらかの要素が対象となります。下記に図示します。

JavaのListIteratorのset()/remove() の対象

最後の操作がnext() だった場合
------------------------------
       set()/remove() の対象
       |    現在位置
       |    |
a[0]   a[1]   a[2]   ...


最後の操作がprevious() だった場合
----------------------------------
            現在位置
            | set()/remove() の対象
            | |
a[0]   a[1]   a[2]   ...

現在位置が全く同じでもset()/remove() の対象が変わる、この動きは正直ややこしいです。

利点の両立は難しいでしょうから、あとは皆さんの好みでしょうか。私は対称性を取ってJava方式に一票かなあ…。

編集者:すずき(2014/05/01 12:03)

コメント一覧

  • IKeJIさん(2014/05/02 13:04)
    常に内部イテレータを使うべき(極論)
  • すずきさん(2014/05/06 00:51)
    >IKeJIさん
    内部イテレータって foreach ですか?
    コレクションの要素が多すぎて単純な全列挙→フィルタで処理できないときや、イテレータを飛ばしたり戻したりするのが難しそうです。
  • IKeJIさん(2014/05/11 04:11)
    foreachに限らず、eachとかmapとかfoldとかそういうのも含めて考えてました。

    > コレクションの要素が多すぎて単純な全列挙→フィルタで処理できないときや、イテレータを飛ばしたり戻したりするのが難しそうです。

    どういう処理でしょう?何か例がありますか?

    俺みたいな低能力プログラマには外部イテレータは難しすぎる気がします。
    もし、for文を書かないといけない時は、椅子に座りなおして、コーラを取ってきてから、気合を入れてかきます。
  • すずきさん(2014/05/11 17:53)
    >IKeJI さん

    >どういう処理でしょう?何か例がありますか?

    特殊すぎる処理で申し訳ないですが、現に困ってるのは、
    「最初の 4バイトがタイプで、最初の 4バイトがサイズ、そのあとサイズ分だけのデータが続く」
    というバイナリを見るとき、もし A, B, C と並んでいれば頭から順に解析できますが、A, C, B と並んでいる場合は頭から順に解析することができない、という構造です。

    さらに C は数 GB あったりして、とにかく全部メモリに置くという作戦もとれません。

    今は外部イテレータにして、わからない部分は飛ばして、位置だけ「仮 C」として覚えておき、後で読む、としていますが、それを foreach や map や fold でどうやって書くのか思いつきませんでした。

    特に Scala の場合、map や fold を List に対してぶちかますと、List の全要素に対して述語の評価を行うので、List の要素が数 GB 以上になると map や fold が現実的な時間で帰ってきません。


    >俺みたいな低能力プログラマには外部イテレータは難しすぎる気がします。
    >もし、for文を書かないといけない時は、椅子に座りなおして、コーラを取ってきてから、気合を入れてかきます。

    たしかに for + 外部イテレータは面倒くさいです。
    外部イテレータ以外の方法があれば使ってみたいんですけど…。
open/close この記事にコメントする



link もっと前
2014年5月1日 >>> 2014年5月1日
link もっと後

管理用メニュー

link 記事を新規作成

<2014>
<<<05>>>
----123
45678910
11121314151617
18192021222324
25262728293031

最近のコメント5件

  • link 21年3月13日
    すずきさん (03/05 15:13)
    「あー、このプログラムがまずいんですね。ご...」
  • link 21年3月13日
    emkさん (03/05 12:44)
    「キャストでvolatileを外してアクセ...」
  • link 24年1月24日
    すずきさん (02/19 18:37)
    「簡単にできる方法はPowerShellの...」
  • link 24年1月24日
    KKKさん (02/19 02:30)
    「追伸です。\nネットで調べたらマイクロソ...」
  • link 24年1月24日
    KKKさん (02/19 02:25)
    「私もエラーで困ってます\n手動での回復パ...」

最近の記事3件

  • link 24年3月25日
    すずき (03/26 03:20)
    「[Might and Magic Book One TASのその後] 目次: Might and Magicファミコン版以前(...」
  • link 21年10月4日
    すずき (03/26 03:14)
    「[Might and Magicファミコン版 - まとめリンク] 目次: Might and Magicファミコン版TASに挑...」
  • link 24年3月19日
    すずき (03/20 02:52)
    「[モジュラージャックの規格] 古くは電話線で、今だとEthernetで良く見かけるモジュラージャックというコネクタとレセプタク...」
link もっとみる

こんてんつ

open/close wiki
open/close Linux JM
open/close Java API

過去の日記

open/close 2002年
open/close 2003年
open/close 2004年
open/close 2005年
open/close 2006年
open/close 2007年
open/close 2008年
open/close 2009年
open/close 2010年
open/close 2011年
open/close 2012年
open/close 2013年
open/close 2014年
open/close 2015年
open/close 2016年
open/close 2017年
open/close 2018年
open/close 2019年
open/close 2020年
open/close 2021年
open/close 2022年
open/close 2023年
open/close 2024年
open/close 過去日記について

その他の情報

open/close アクセス統計
open/close サーバ一覧
open/close サイトの情報

合計:  counter total
本日:  counter today

link About www.katsuster.net
RDFファイル RSS 1.0

最終更新: 03/26 03:20