前のページ | 次のページ

キーポイント

• 配列やmapなどのコンテナの各要素に対して順番に処理を行うときにイテレータを用いることができる
• イテレータを変数に入れる場合はautoを用いる
• イテレータの操作

• 要素を削除したり、追加することによってイテレータが無効になることがある
• 無効なイテレータを使用しないように注意が必要

イテレータ

配列やmapなどのコンテナの各要素に対して順番に処理を行うときにイテレータを用いることができます。 イテレータを用いると処理を一般化できることが多く、 実際にSTLにおいて「一連の要素に対して何かを行う」ような関数はイテレータを引数に取る形で実装されています。

例えば配列をソートするときに用いるsortはイテレータを引数に取ります。 sortに渡していた配列.begin()や配列.end()がイテレータを表します。

配列に対するイテレータは次の図のように「各要素を指すもの」として考えることができます。

上の図で、イテレータ1は3つ目の要素である5を指すイテレータで、イテレータ2は7つ目の要素である4を指すイテレータです。

イテレータに対する操作としては、「次の位置のイテレータを得る」ことや「イテレータが指す要素にアクセスする」などの操作ができます。

次のサンプルプログラムは、配列の2番目の要素にアクセスする例です。

#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> a = {3, 1, 5, 6, 7, 2, 4};

  auto itr1 = a.begin();  // aの先頭を指すイテレータ
  itr1 = itr1 + 2;        // a[2]を指すイテレータ
  auto itr2 = itr1 + 4;   // 末尾の要素(a[6])を指すイテレータ

  cout << *itr1 << endl;  // itr1が指す要素(a[2])へのアクセス
  cout << *itr2 << endl;  // itr2が指す要素(a[6])へのアクセス
}

実行結果

5
4

次のサンプルプログラムは、for文を用いて配列の要素に順番にアクセスする例です。

#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> a = {1, 2, 3};
  // a.begin() .. 先頭の要素を指すイテレータ
  // a.end() .... 終端を指すイテレータ
  // it++ ....... イテレータを1つ分進める (it = it + 1と同じ)
  for (auto it = a.begin(); it != a.end(); it++) {
    cout << *it << endl;
  }
}

実行結果

1
2
3

配列の要素に対するアクセスはインデックスを指定してa[1]のように書くことができるので、 実際に上のサンプルプログラムのように書くことはあまりないかもしれません。

しかしイテレータには配列以外のデータ構造に対しても同じように扱えるというメリットがあります。
これによって、例えば「配列専用のソート関数」を用意しなくてよくなり、 イテレータをサポートする任意のデータ構造に対して、同じソート関数sortを用いることができるようになっています。

イテレータの型

イテレータの型はコンテナ毎に定義されていて、複雑なものになっています。 手書きするのは大変なので通常はautoを用います。

vector<int> a = {1, 2, 3};
auto itr1 = a.begin();
set<int> b = {4, 5, 6};
auto itr2 = b.begin();
// itr1とitr2は別の型

厳密な型が必要な場合はcppreference.comなどを参照してください。

先頭の要素のイテレータ

コンテナ.begin()

コンテナの先頭の要素を指すイテレータを返します。 コンテナが空の場合は「末尾の要素の次」を指すイテレータを返します。

終端のイテレータ

コンテナ.end()

コンテナの終端 (最後の要素の次)を指すイテレータを返します。末尾の要素を指すイテレータではないことに注意してください。
一見扱いにくいように見えますが、for文での終了判定する際などに便利な場合があります。

また、endが返すイテレータの指す位置にアクセスしてはならないことに注意してください。
このような、それが指す位置に要素が存在しないようなイテレータに対してアクセスを行うことは未定義な動作を引き起こします。

イテレータの比較

イテレータ1 == イテレータ2

2つのイテレータが同じ位置を指すときにtrueになります。

イテレータ1 != イテレータ2

2つのイテレータが違う位置を指すときにtrueになります。

イテレータ間の距離

distance(イテレータ1, イテレータ2)

「イテレータ1を何回進めるとイテレータ2に一致するか」を返します。

mapやsetのイテレータの場合、イテレータ1がイテレータ2よりも後ろの要素を指す場合、動作は未定義です。

イテレータの移動

これらの操作ではイテレータの変数自体が変更されます。

1つ進める

イテレータ++;

k個分進める

イテレータをk回進めるときには以下のように書くこともできます。

advance(イテレータ, k);

1つ後ろに進める

イテレータ--;

k個分後ろに進める

advanceに負の値を渡すことで、指定回数分後ろに進めることができます。

advance(イテレータ, -k);  // k回分後ろに進める

前後のイテレータを得る

イテレータをコピーした後で、++やadvanceを用いれば同じことができます。

次

next(イテレータ)     // 次の要素を指すイテレータ
next(イテレータ, k)  // k個先の要素を指すイテレータ
イテレータ + k       // k個先の要素を指すイテレータ (map/setでは使えない)

1つ後ろ

prev(イテレータ)     // 1つ後ろの要素を指すイテレータ
prev(イテレータ, k)  // k個後ろの要素を指すイテレータ
イテレータ - k       // k個後ろの要素を指すイテレータ (map/setでは使えない)

nextやprevは返り値として前後のイテレータを返します。 引数に渡したイテレータ自体は書き換わりません。

イテレータが指す要素へのアクセス

*イテレータ

コンテナ.end()が返すイテレータや、空のコンテナ.begin()が返すイテレータに対してアクセスを行うことは未定義な動作を引き起こします。

イテレータが指す要素のメンバへのアクセス

イテレータ->メンバ変数
イテレータ->メンバ関数()  // メンバ関数の呼び出し

具体例

#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<pair<int, int>> a = {{1, 4}, {2, 5}, {3, 6}};
  auto itr = a.begin() + 1;
  // cout << (*itr).first << ", " << (*itr).second << endl; と書くのと同じ
  cout << (itr->first) << ", " << (itr->second) << endl;
}

実行結果

2, 5

イテレータの使用例

i番目の要素を指すイテレータ

next(コンテナ.begin(), i)

各要素に対して処理

for (auto it = コンテナ.begin(); it != コンテナ.end(); it++) {
  // 各要素に対する処理
}

要素の削除

イテレータが指す要素を削除することもできます。

コンテナ.erase(イテレータ);  // イテレータが指す要素を削除

要素の削除によってそのイテレータが無効化されます。詳しくは注意点で説明します。

for文で各要素に対する処理を行っているときに、削除を行う場合には次のようにします。

for (auto it = コンテナ.begin(); it != コンテナ.end()) {
  if (要素を削除する条件) {
    // eraseは削除後の次の要素のイテレータを返します。
    it = コンテナ.erase(it);  // itの指す要素を削除
  } else {
    it++;
  }
}

末尾の要素を指すイテレータ

endは終端を指すイテレータを返すことを説明しましたが、 末尾の要素を指すイテレータが欲しい場合は次のようにすればよいです。

prev(コンテナ.end())

空のコンテナに対してこの操作を行ってはいけないことに注意してください。

sort(イテレータ1, イテレータ2);

find(イテレータ1, イテレータ2, 値)  // 見つからなかった場合はイテレータ2を返す

オブジェクト.find(イテレータ1, イテレータ2, 値)  // 見つからなかった場合はイテレータ2を返す

#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> a = {1, 2, 3, 5};
  // 3の要素を指すイテレータ
  auto itr = find(a.begin(), a.end(), 3);

  // もし存在しなければ、a.end()が返る
  if (itr == a.end()) {
    cout << "not found" << endl;
  } else {
    // itrが添字の何番目を指すかを求める
    int idx = distance(a.begin(), itr);
    cout << "a[" << idx << "] = " << *itr << endl;
  }
}

a[2] = 3

find_if(イテレータ1, イテレータ2, 条件の関数)  // 見つからなかった場合はイテレータ2を返す

#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> a = {1, 3, 4, 5, 9, 10};
  // 偶数であるような最初の要素を指すイテレータ
  auto itr = find_if(a.begin(), a.end(), [](int x) { return (x % 2 == 0); });
  if (itr == a.end()) {
    cout << "not found" << endl;
  } else {
    cout << *itr << endl;
  }
}

4

lower_bound(イテレータ1, イテレータ2, 値)  // 見つからなかった場合はイテレータ2を返す

オブジェクト.lower_bound(イテレータ1, イテレータ2, 値)  // 見つからなかった場合はイテレータ2を返す

#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> a = {8, 5, 3};
  sort(a.begin(), a.end());  // lower_boundを使うためにソートする

  // 5以上の最小の要素を指すイテレータ
  auto itr = lower_bound(a.begin(), a.end(), 5);
  if (itr == a.end()) {
    cout << "not found" << endl;
  } else {
    cout << *itr << endl;
  }

  // 6以上の最小の要素を指すイテレータ
  itr = lower_bound(a.begin(), a.end(), 6);
  if (itr == a.end()) {
    cout << "not found" << endl;
  } else {
    cout << *itr << endl;
  }
}

5
8