C++ STLメモ6 iterator補足

STLでは,コンテナ(配列など複数のデータを格納できる構造のこと)内の各要素のデータへアクセスするためにiterator(イテレーター)というものを使ってる。

しかし,iteratorと一言に言っても様々な種類がある。

iteratorはiteratorでも,同じもの,似ているもの,全然違うものなどだ。

しかも,iteratorという型は単独では存在しない。必ず何らかの型が頭に付く形となる
たとえば,deque<string>のiteratorは以下の太字の部分の様な型となる。

#include <iostream>
#include <deque>
using namespace std;

int main( )
{
  deque<int> d_str;

  d_str.push_back(10);
  d_str.push_back(20);
  d_str.push_back(30);

  // iteratorを使った例:全ての要素を先頭から順番に見ていく
  deque<int>::iterator ii;
  for(ii = d_str.begin( ); ii != d_str.end( ); ii++) {
    cout << *ii << endl;
  }

  cout << endl;

  // iteratorを使わないと以下の様なコードになる
  int i;
  for(i = 0; i < d_str.size( ); i++) {
    cout << d_str[i] << endl;
  }

  return 0;
}

上のプログラムの実行結果は
10
20
30

10
20
30
となる。


// dequeを配列にしてiteratorをポインタ変数に直すとこんな感じ
#include <iostream>
using namespace std;

int main( )
{
  int d_str[3];

  d_str[0] = 10;
  d_str[1] = 20;
  d_str[2] = 30;

  // ポインタを使った例:全ての要素を先頭から順番に見ていく
  int* ii;
  for(ii = d_str; ii - d_str < 3 ; ii++) {
    cout << *ii << endl;
  }

  return 0;
}


これの実行結果は
10
20
30
となる

iteratorの使い方は,++や--で移動するので,C言語の配列をポインタ変数で扱う方法に似ている。

事実,dequeのiteratorの実装はポインタ変数である。

じゃあ,なぜポインタ変数とせずにitratorとしているのか?

以下のプログラムを見ていただきたい。dequeがlistに変わった。


#include <iostream>
#include <list>
using namespace std;

int main( )
{
  list<int> d_str;

  d_str.push_back(10);
  d_str.push_back(20);
  d_str.push_back(30);

  // iteratorを使った例:全ての要素を先頭から順番に見ていく
  list<int>::iterator ii;
  for(ii = d_str.begin( ); ii != d_str.end( ); ii++) {
    cout << *ii << endl;
  }

//   cout << endl;

  // listはiteratorを使わないと使えない。
//  int i;
//  for(i = 0; i < d_str.size( ); i++) {
//    cout << d_str[i] << endl;
//  }

  return 0;
}

データ構造がdeque可変長配列からlist双方向連結リストへ変わった場合でも
iteratorを使わない部分が使えなくなったのを除けば,書き換え部分はわずかだ。

iteratorの目的の1つは,データ構造とアルゴリズムの分離だ。
完全に分離は出来ないが,ある程度分離が出来ていているので,
iteratorの癖を理解すれば,どんなデータ構造でも,iteratorで
扱えるようになっているので,STLの様々なコンテナがどんどん使えてしまう。

iteratorの癖は
コンテナの変数.begin(); で先頭を取得できる
コンテナの変数.end(); で終端の1つ先を取得できる
コンテナの変数.find( ); でコンテナ内を検索したら,検索結果をiteratorで返す。
コンテナの変数.rbegin(); で逆向きに進むiteratorの先頭を取得できる
コンテナの変数.rend(); で逆向きに進むiteratorの終端の1つ先を取得できる

などがある。


iteratorの主な種類

通常版
iterator 先頭から後ろへ移動するiterator通常版 ++で後ろに移動 -- で前に移動する
reverse_iterator 後ろから先頭へ移動するiterator通常版 ++で前に移動 -- で後ろに移動する

読み出し専用版
const_iterator 先頭から後ろへ移動するiterator読み出し専用版
const_reverse_iterator 後ろから先頭へ移動するiterator読み出し専用版
 これは,書き換え許可されていないiteratorで,値の参照は出来るが,書き換えが出来ないものいconstなメソッドやconstなオブジェクトのメソッドが返したiteratorはこれになる。


iteratorの根本的な違いの種類が2つあります。どちらも,見た目はiterator型で似ている操作が出来ます。

ランダム アクセス反復子
vectorやdequeなどの可変長配列系のiterator
 beginとendの間が連続したメモリに配置されている。C言語の配列のポインタ変数と同じ

双方向反復子
listやmapやsetなどの連結リスト,二分探索木などのiterator
 次の位置と前の位置が不連続。前の位置と次の位置情報もあわせて持っている。内部構造が複雑だが,iteratorを使う分には,構造は,「データはメモリ上に連続で並んでいない」以外を意識する必要はほどんどない。


mapのiteratorのみ特殊で,これだけ使い方がコードで明確に意識しなければならない。

#include <iostream>
#include <map>
using namespace std;

int main( )
{
  map<int,double> m;
  m[10] = 1.2;
  m[20] = 5.6;
  m[30] = 10.3;
  map<int,double>::iterator ii;

  for(ii = m.begin( ); ii != m.end( ); ii++) {
    cout << (*ii).first << endl;; // キーでここではint型
    cout << (*ii).second << endl;// 値でここではdouble型
  }

  return 0;
}


ちなみに,この書き方でもよい。

#include <iostream>
#include <map>
using namespace std;

int main( )
{
  map<int,double> m;
  m[10] = 1.2;
  m[20] = 5.6;
  m[30] = 10.3;
  map<int,double>::iterator ii;

  for(ii = m.begin( ); ii != m.end( ); ii++) {
    cout << ii->first << endl; // キーでここではint型
    cout << ii->second << endl; // 値でここではdouble型
  }

  return 0;
}



mapのiteratorについて,補足

mapは,m[30] = 10;(値の設定)や double g = m[50];(値の参照)を[ ] 演算子で行うと,最初に,[ ] の中に指定しているキーがあるかどうか,検索を行い,無ければ追加を行う。そして,その要素を返してくる。ない時は,デフォルトの値を返す。(intやdouble等は,0を返し,クラス型は,引数なしのコンストラクタで生成されるオブジェクトを作成して返す)

ということは,見つからなかったときに,追加を行わないようにしたい場合は,mapのメンバ関数find( )を使わなければならない。ちなみに,findはiterator型で返す

具体的なコードは以下の様になります。



#include <iostream>
#include <map>
using namespace std;

int main( )
{
  map<int,double> m;
  map<int,double>::iterator ii;

  // m[10] = 1.2; を細かくコントロールしたいとき
  ii = m.find(10); // m[10] があるかどうか検索
  if(ii == m.end() ) { // mapのfindは,見つからないと end()を返す
    m[10] = 1.2; // 新に追加
  } else {
    ii->second = 1.2; // 見つけたら,secondに代入 m[10] = 1.2; でも良いが,こっちの方が効率がいい・・・。
  }


  // m[20] = 5.6; を細かくコントロールしたいとき。別の書式で書くとこうなります。
  ii = m.find(20);
  if(ii == m.end() ) { // mapのfindは,見つからないと end()を返す
    map<int,double>::value_type vals(20, 5.6);
    m.insert(vals);
  } else {
    (*ii).second = 5.6; // 見つけたら,secondに代入 m[20] = 5.6; でも良いが,こっちの方が効率がいい・・・。
  }

  m[30] = 10.3; // やはり,この書き方が一番簡単かな・・・。すでにkeyが30で追加されているかどうかを確認する必要がない場合,これでも問題ない。

  for(ii = m.begin( ); ii != m.end( ); ii++) {
    cout << ii->first << endl; // キーでここではint型
    cout << ii->second << endl; // 値でここではdouble型
  }

  return 0;
}

この記事へのコメント

この記事へのトラックバック