AI - 4.04.イテレータ /

Time Limit: 0 msec / Memory Limit: 0 KB

前のページ | 次のページ

キーポイント

  • 配列やmapなどのコンテナの各要素に対して順番に処理を行うときにイテレータを用いることができる
  • イテレータを変数に入れる場合はautoを用いる
  • イテレータの操作
操作 記法
コンテナの先頭の要素を指すイテレータを得る コンテナ.begin()
コンテナの末尾の要素の次を指すイテレータを得る コンテナ.end()
イテレータの比較 イテレータ1 == イテレータ2, イテレータ1 != イテレータ2
イテレータ間の距離 distance(イテレータ1, イテレータ2)
イテレータの移動 advance(イテレータ, k);(イテレータをk回進める), イテレータ++;, イテレータ--;
前後のイテレータを得る next(イテレータ, k)k個先のイテレータ。kの指定は省略すると1として扱われる),
prev(イテレータ, k)k個前のイテレータ)
イテレータ + k,イテレータ - kmap/setでは使えない)
イテレータの指す要素へのアクセス *イテレータmap/setのイテレータは読み取り専用)
イテレータの指す要素のメンバへのアクセス イテレータ->メンバmap/setのイテレータは読み取り専用)
イテレータの指す要素の削除 コンテナ.erase(イテレータ)
  • 要素を削除したり、追加することによってイテレータが無効になることがある
  • 無効なイテレータを使用しないように注意が必要

イテレータ

配列や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 = begin(a); it != end(a); 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に一致するか」を返します。

mapsetのイテレータの場合、イテレータ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では使えない)

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

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

*イテレータ

コンテナ.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())

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

イテレータの操作の計算量

イテレータの操作にかかる計算量はコンテナによって異なります。

配列

配列のイテレータを操作するときの計算量は以下の通りです。

操作 計算量
begin(), end() O(1)
next, prev, +, - O(1)
advance, ++, -- O(1)
distance O(1)
*->によるアクセス O(1)
要素の削除 削除する要素以降の要素数をNとして、O(N)

map/set

map/setのイテレータを操作するときの計算量は以下の通りです。

操作 計算量
begin(), end() O(1)
next, prev, ++, -- 移動する回数をNとしてO(N)
advance, ++, -- 移動する回数をNとしてO(N)
distance イテレータ間の距離をNとしてO(N)
*->によるアクセス O(1)
要素の削除 償却計算量でO(1)

「償却計算量でO(1)」とは、同じ処理をN回行ったときに1回あたりの計算量がO(1)になるという意味です。

注意点

無効なイテレータ

コンテナに対して要素の削除や追加を行うと、操作前のイテレータが無効化されることがあります。 無効なイテレータを使用することは未定義の動作を引き起こします。

イテレータを取っておいて、後から使いまわすような場合には注意する必要があります。

以下にイテレータが無効化される場合の例を挙げます。 詳しくはcppreference.comなどを参照してください。

vector

要素を削除すると、その要素を含むそれより後ろの要素に対するイテレータが無効化されます。 必要に応じてerase関数の戻り値を利用することができます。

また、push_backなどによって、コンテナの容量が変更される場合には、全ての要素に対するイテレータが無効化されます。

要素へのアクセスによってイテレータが無効化されることはありません。

map/set

要素を削除すると、その要素に対するイテレータが無効化されます。 必要に応じてerase関数の戻り値を利用することができます。

読み取りや、要素の追加ではイテレータが無効化されることはありません。

map/setのイテレータは読み取り専用

mapsetのイテレータの指す要素を変更することはできません。


細かい話

STLの関数の紹介

STLの関数で、イテレータに関連するものをいくつか紹介します。

sort

既に紹介していますが、データを整列するための関数です。

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

イテレータ1とイテレータ2の間にある要素を整列します。

sort(配列.begin(), 配列.end());のように用いれば配列全体を整列できますし、sort(配列.begin() + 1, 配列.end());のように用いれば先頭以外を整列することができます。


find

イテレータの範囲内から指定した値に一致する最初の要素を探し、その要素を指すイテレータを返します。 見つからなかった場合は、範囲の最後を返します。

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

計算量はイテレータの距離をNとしてO(N)です。

map/setの場合

map/setの場合は次のようにして、メンバ関数版のfindを用いる方が高速です。

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

計算量はコンテナの要素数をNとしてO(\log N)です。

具体例

配列の中に3があるかを探す例です。

#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

イテレータの範囲内から、条件を満たす最初の要素を探し、その要素を指すイテレータを返します。 見つからなかった場合は、範囲の最後を返します。

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

条件の関数には「要素を引数として受け取りbool値を返す」関数を指定します。 find_ifは、この関数がtrueを返す最初のイテレータを返します。

条件にはラムダ式を用いることもできます。

計算量はイテレータの距離をNとしてO(N)です。

具体例

配列の中から偶数の要素を探す例です。

#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

イテレータの範囲内から指定した値以上の最小の要素を探し、その要素を指すイテレータを返します。 見つからなかった場合は、範囲の最後を返します。

lower_boundを用いる場合、指定する範囲がソート済みである必要があります。

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

計算量はイテレータの距離をNとしてO(\log N)です。

map/setの場合

map/setの場合は次のようにして、メンバ関数版のlower_boundを用いる方が高速です。

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

計算量はコンテナの要素数をNとしてO(\log N)です。

具体例
#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

upper_bound

イテレータの範囲内から指定した値より大きな最小の要素を探し、その要素を指すイテレータを返します。 見つからなかった場合は、範囲の最後を返します。

使い方や計算量はlower_boundと同じです。 こちらも、map/setの場合はメンバ関数版を用います。


前のページ | 次のページ