Iterator

[id:lethevert:20051223:p2]
前の記事を書いた後に、Iteratorのことを考えたので、そのことについて。
リストの要素に対して順次処理を行う場合、「繰り返し処理 + インデックス」を使ったり、イテレータを使ったりする。で、前の記事のようにダウンカウンタループを使った場合、リストの要素に対して逆順に処理を行ってしまうなぁと思ったのですが、そういう場合は、イテレータを使うべきなのか、と思って、よく考え直してみたら、「リストの処理は、必ずイテレータを使うべき」だということに気づいたのでした。
ま、分かっている人には、分かっていることだと思うので、いまさらな感じでもあるのですが・・・

• • • -

非常に単純な話なのですが、いわゆるLinkedListの場合、インデックスによる要素アクセスはコストが高いので、下のようなコードは書くべきでないのです。

for(int i=0; i<list.size(); ++i){
  doSomethingWith(list.get(i));
}

これを下のようにイテレータを使って書けば、要素アクセスは順次処理になるので、要素アクセスはコストがかかりません。

Iterator itr = list.iterator();
while(itr.hasNext()){
  doSomethingWith(itr.next());
}

しかし、こういう勘違いは内部イテレータを使わない言語でおこりがちなことで、内部イテレータを使う言語なら、こういう間違いは起こらないわけで。たとえば、Perlならこんな風に書くのが普通。

map doSomethingWith, @list;