C++編【標準ライブラリ】 第14章 イテレータ

この章の概要

この章の概要です。

イテレータ

イテレータ(反復子)は、コンテナに含まれる複数の要素に対する反復処理を行うためのオブジェクトです。 反復処理というのは、各要素に順番に何らかの処理を行っていく操作のことを言い、走査とも呼ばれます。

STLコンテナの場合、イテレータは、コンテナが持つ beginメンバ関数endメンバ関数 によって取得できます。 beginメンバ関数は、コンテナの先頭要素を指すイテレータを、endメンバ関数は、コンテナの末尾要素の1つ先を指すイテレータを返します。
beginメンバ関数や endメンバ関数が返す型は、コンテナごとに別個に定義された型であり、 例えば、vector にとってのイテレータと、map にとってのイテレータとでは別の型になります
このように、別の型になっているのは、配列構造と木構造とでは走査する方法が違うように、走査の方法はデータ構造に依存するためです。

beginメンバ関数や endメンバ関数が返す型は、具体的には、std::Container<>::iterator型、 あるいは std::Container<>::const_iterator型です(Container には、vector や map などのコンテナクラス名が入る)。
以降、std::Container<>::iterator型を iterator型、std::Container<>::const_iterator型を const_iterator型と表記します。

非const関数版の begin/endメンバ関数の場合は、iterator型を返し、 const関数版の begin/endメンバ関数の場合は、const_iterator型を返すということですが、 iterator型から const_iterator型へは、暗黙的に型変換できるので、常に、const_iterator型で受け取ることは可能です。
逆に、const_iterator型から iterator型への暗黙的な型変換はできません (明示的な型変換を行う方法について、「イテレータの変換」の項で取り上げます)。

C++11 (cbeginメンバ関数、cendメンバ関数)

C++11 の STLコンテナには、戻り値が const_iterator に固定された cbeginメンバ関数と、 cendメンバ関数が追加されています。

const_iterator を使いたい場合は、これらの関数を使う方が意図が明確になり、 C++11 で追加された auto(【言語解説】第2章)と組み合わせたとき、 確実に const_iterator を型推測してくれるという価値があります。

std::vector<int> v;
auto it = v.begin();   // こう書くと std::vector<int>::iterator型
auto it = v.cbegin();  // こう書くと std::vector<int>::const_iterator型

cbeginメンバ関数、cendメンバ関数は、VisualC++ 2013/2015、clang 3.7 のいずれでも使用できます。


イテレータは、ポインタを真似て作られているので、使用感はポインタと似ています。 指し示す先の要素の型を T とすると、 iterator が T*型のようなものであり、const_iterator は const T*型にあたります。 そのため、const_iterator の場合は、指し示している先の要素を書き換えることができません

iterator や const_iterator がどのように定義・実装されているかは、標準ライブラリの実装者に裁量に任されています。 vector の場合、本当に iterator が T* の typedef であり、const_iterator が const T* の typedef であることがあり得ますが、 そうでないこともありますから、イテレータを本当にポインタのように扱ってはいけません。 使用感が似ているのであって、同一のものではありません。

一例として、イテレータを使って、list を走査する例を示します。

#include <iostream>
#include <list>

int main()
{
	typedef std::list<int> IntList;

	const int table[] = {0, 1, 2, 3, 4};

	IntList lst(table, table + 5);

	IntList::const_iterator itEnd = lst.end();
	for (IntList::const_iterator it = lst.begin(); it != itEnd; ++it) {
		std::cout << *it << "\n";
	}
	std::cout << std::flush;
}

実行結果

0
1
2
3
4

list の代わりに、vector や deque、set や map といった、他の STLコンテナを使っても同じです。

C++11 (非メンバ関数の begin、end)

C++11 には、非メンバ関数版の begin関数end関数が追加されています。 これらの関数は、iterator という名前の標準ヘッダに含まれます。
なお、C++11 の時点では、非メンバ関数版の cbegin関数、cend関数は存在しておらず、 C++14 で追加されています

非メンバ関数版の場合、引数に対象のコンテナを指定します。 戻り値は、メンバ関数版と同様です。

#include <iostream>
#include <list>
#include <iterator>

int main()
{
	typedef std::list<int> IntList;

	const int table[] = {0, 1, 2, 3, 4};

	IntList lst(table, table + 5);

	IntList::const_iterator itEnd = std::end(lst);
	for (IntList::const_iterator it = std::begin(lst); it != itEnd; ++it) {
		std::cout << *it << "\n";
	}
	std::cout << std::flush;
}

実行結果

0
1
2
3
4

非メンバ関数版では、配列に対しても適用できる点が大きな違いになります。

#include <iostream>
#include <iterator>

int main()
{
	const int table[] = {0, 1, 2, 3, 4};

	const int* const itEnd = std::end(table);
	for (const int* it = std::begin(table); it != itEnd; ++it) {
		std::cout << *it << "\n";
	}
	std::cout << std::flush;
}

実行結果

0
1
2
3
4

非メンバ関数版の方が、汎用的に使用できるので、 C++11 では、メンバ関数版よりも、非メンバ関数版を使うようにすると良いでしょう。

VisualC++ 2013/2015、clang 3.7 は、いずれも対応しています。

C++14 (非メンバ関数の cbegin、cend)

C++14 になって、C++11 の規格から外れてしまっていた、 非メンバ関数版の cbegin関数cend関数が追加されました。

#include <iostream>
#include <iterator>

int main()
{
	const int table[] = {0, 1, 2, 3, 4};

	auto itEnd = std::cend(table);
	for (auto it = std::cbegin(table); it != itEnd; ++it) {
		std::cout << *it << "\n";
	}
	std::cout << std::flush;
}

実行結果

0
1
2
3
4

メンバ関数版よりも非メンバ関数版を使い、 begin/end と cbegin/cend を使い分けるようにしましょう。 この使い分けを守れば、イテレータを受け取る変数の型も auto に統一できます。

VisualC++ 2013/2015、clang 3.7 は、いずれも対応しています。

配列にとってのイテレータ

配列は、STLコンテナでは無いですし、そもそもクラスですら無いので、beginメンバ関数や endメンバ関数は存在しませんが、 ポインタをイテレータとみなして、同等の処理を行うことが可能です。

beginメンバ関数や endメンバ関数が使わなくても、次のように、イテレータと同じ形のままプログラムを書くことができます。

#include <iostream>

int main()
{
	const int table[] = {0, 1, 2, 3, 4};

	const int* const itEnd = &table[5];
	for (const int* it = table; it != itEnd; ++it) {
		std::cout << *it << "\n";
	}
	std::cout << std::flush;
}

実行結果

0
1
2
3
4

C++11 には、非メンバ関数版の begin関数、end関数が追加されており、これらは配列に対しても適用可能です。

イテレータのカテゴリ

STLコンテナから得られるイテレータについて、その使い方を考えても分かるように、 対象のデータ構造によって、イテレータが持つ機能には違いがあります。
例えば、vector に対するイテレータであれば「n個先の要素を指すように一気に進ませる」ことができます。 一方、set に対するイテレータでは、「1つ先の要素へ進ませる」ことはできますが、 「n個先」となると直接的には実現できず、「1つ先へ」をn回繰り返すしかありません。 この例は、添字を使ったランダムアクセスができる構造と、できない構造の違いから来ています。

結局、set でも「n個先の要素を指すように進ませる」ことはできている訳ですが、 その効率には大きな差があります。vector では「1個先」でも「1000個先」でも、その効率に違いがありませんが、 set では 1000倍違う訳です。

STL では、イテレータの機能性を、5つのカテゴリで表現しています。

入力イテレータ

入力イテレータは、1つ1つ先の要素へと進むことができ、その値を読み取る機能だけを持ちます。 このカテゴリのイテレータは、以下の演算が行えます。

演算 内容
* (間接参照) 指し示す先の要素への読み取り専用アクセス
-> 指し示す先の要素のメンバに対する読み取り専用アクセス
++ (前置インクリメント) 要素1つ分、先へ進み、新しい位置を返す
++ (後置インクリメント) 要素1つ分、先へ進み、前の位置を返す
== 2つのイテレータが等しいかどうかを返す
!= 2つのイテレータが等しくないかどうかを返す
コピーコンストラクタ イテレータをコピーする

このカテゴリのイテレータは、指し示す先を、手前側に戻す手段がありません。 そのため、各要素は1回だけしか参照することができません。 また、読み取り専用であり、要素を書き換えることもできません。

== と != に関しては、2つのイテレータが同じ場所を指しているとき、等しいとみなされます。

このカテゴリに属するイテレータの例としては、入力ストリームイテレータ(第31章参照)があります。

出力イテレータ

出力イテレータは、1つ1つ先の要素へと進むことができ、要素へ値を書き込む機能だけを持ちます。 このカテゴリのイテレータは、以下の演算が行えます。

演算 内容
* (間接参照) 指し示す先の要素への書き込み専用アクセス
++ (前置インクリメント) 要素1つ分、先へ進み、新しい位置を返す
++ (後置インクリメント) 要素1つ分、先へ進み、前の位置を返す
コピーコンストラクタ イテレータをコピーする

出力イテレータは、入力イテレータとは逆に、書き込み専用です。

出力イテレータには、== や != といった比較の演算が定義されていません。 そのため、末尾に達したかどうかを知る手段も無いですが、末尾を気にせずに書き込みを続けて構わないことになっています。 つまり、以下のコードは有効です。

while (true) {
	*it = 999;
	++it;
}

このカテゴリに属するイテレータの例としては、 出力ストリームイテレータ(第31章参照)や挿入イテレータ(第25章参照)があります。

前方イテレータ

前方イテレータは、入力イテレータと出力イテレータの両方の特徴を持ったものです。 つまり、1つ1つ先の要素へと進むことができ、指し示す先の要素の読み書きが行えます。 このカテゴリのイテレータは、以下の演算が行えます。

演算 内容
* (間接参照) 指し示す先の要素への読み書き両用アクセス
-> 指し示す先の要素のメンバに対する読み書き両用アクセス
++ (前置インクリメント) 要素1つ分、先へ進み、新しい位置を返す
++ (後置インクリメント) 要素1つ分、先へ進み、前の位置を返す
== 2つのイテレータが等しいかどうかを返す
!= 2つのイテレータが等しくないかどうかを返す
デフォルトコンストラクタ イテレータを生成する
コピーコンストラクタ イテレータをコピーする
代入 イテレータを代入する

出力イテレータの機能を備えていますが、少しだけ違いがあることに注意して下さい。 出力イテレータの場合、末尾を気にせずに書き込みを続けることができますが、 前方イテレータでは、末尾を超えるとエラーになります。 そのため、以下のように、終端のチェックを行うようにして下さい。

while (it != container.end()) {
	*it = 999;
	++it;
}

このような差異があるので、前方イテレータは、入力イテレータから派生しているとは言えますが、 出力イテレータから派生しているとは言えません。

実のところ、このカテゴリに属するイテレータの例はありませんが、 前方イテレータの機能を継承したカテゴリがあり、そちらに属するイテレータがあります。

双方向イテレータ

双方向イテレータは、前方イテレータの機能を継承しており、そこへ更に、1つ手前の要素へ戻る機能を追加しています。 このカテゴリのイテレータは、前方イテレータの機能に加えて、以下の機能を持ちます。

演算 内容
-- (前置デクリメント) 要素1つ分、手前へ戻し、新しい位置を返す
-- (後置デクリメント) 要素1つ分、手前へ戻し、前の位置を返す

このカテゴリに属するイテレータには、list、set/multiset、map/multimap のイテレータがあります。

ランダムアクセスイテレータ

ランダムアクセスイテレータは、双方向イテレータの機能を継承しており、そこへ更に、ランダムアクセス機能を追加しています。 このカテゴリのイテレータは、双方向イテレータの機能に加えて、以下の機能を持ちます。

演算 内容
[] n番目の要素にアクセスする
+ (加算) 要素n個分、先を指すイテレータを返す
- (減算) 要素n個分、手前を指すイテレータを返す
+= 要素n個分、先へ進む
-= 要素n個分、手前へ戻る
- (イテレータ同士の減算) 2つのイテレータの差(距離)を返す
< 左辺のイテレータの方が、右辺のイテレータより手前にあるかどうかを返す
<= 左辺のイテレータの方が、右辺のイテレータより後ろにないかどうかを返す
> 左辺のイテレータの方が、右辺のイテレータより後ろにあるかどうかを返す
>= 左辺のイテレータの方が、右辺のイテレータより手前にないかどうかを返す

このカテゴリに属するイテレータには、vector、deque、basic_string のイテレータがあります。 また、配列に対するイテレータ(ポインタ)も、ここに含まれます。

advance関数

std::advance関数を使うと、 イテレータを任意の要素数分だけ、先へ進めたり(その機能を持ったカテゴリのイテレータであれば)前に戻したりできます。
advance関数は、iterator という名前の標準ヘッダに含まれています。

advance関数は、第1引数にイテレータを指定し、第2引数に進めたい要素数を指定します。
第1引数に指定できるのは、入力イテレータカテゴリおよびそこから派生しているカテゴリに属するイテレータです。 なお、この引数は参照になっており、渡したイテレータ自体が変更されます。
第2引数には負数を指定できますが、実際に手前側に移動できるのは、 その機能を持っている双方向イテレータと、ランダムアクセスイテレータに限られます
戻り値はなく、第1引数に指定したイテレータ自体が変更されることで、結果を得ます。

#include <iostream>
#include <list>
#include <iterator>

int main()
{
	typedef std::list<int> IntList;

	const int table[] = {0, 1, 2, 3, 4};

	IntList lst(table, table + 5);

	IntList::const_iterator it = lst.begin();
	std::advance(it, 3);
	std::cout << *it << std::endl;
	std::advance(it, -1);
	std::cout << *it << std::endl;

	const int* p = table;
	std::advance(p, 3);
	std::cout << *p << std::endl;
	std::advance(p, -1);
	std::cout << *p << std::endl;
}

実行結果

3
2
3
2

advance関数は、イテレータがコンテナの末尾を超えるかどうかを判断できないので、 末尾を超えてしまうような移動は、未定義の動作になることに注意して下さい。 当然、先頭より更に手前側への移動も同様です

advance関数は、イテレータのカテゴリを判断して、それに応じた実装が使用されるようになっています。
例えば、第1引数に、ランダムアクセスイテレータ以外のイテレータを指定し、 第2引数に、1 より大きい値(または -1 より小さい値)を指定した場合、 ++演算子や --演算子を繰り返し実行することによって、指定した要素数分の移動を実現します。 そのため、効率面では大きく劣ることに注意して下さい。
advance関数を使うことで、イテレータカテゴリの違いを気にせず、移動という処理を汎用化できますが、 特別、性能がよくなる訳ではありません。

これを実現するために、特性という仕組みが利用されています。

C++11 (next関数、prev関数)

C++11 で、advance関数に代わる関数として、std::next関数std::prev関数が追加されました。 前者はイテレータを先の方へ進ませ、後者は手前へ戻します。 ただし、双方向イテレータやランダムアクセスイテレータの場合に、第2引数に負数を指定すると逆になります。
これらの関数は、iterator という名前の標準ヘッダに含まれます。

advance関数と違い、第1引数は参照ではなく、移動後のイテレータは戻り値で返されるようになっています。

it = std::next(it, 3);
it = std::prev(it, 1);

また、第2引数は、デフォルト値として 1 を持つようになっているので、 1要素分だけ進める(または戻す)という場合には、第2引数を省略できます。

it = std::next(it);
it = std::prev(it);

VisualC++ 2013/2015、clang 3.7 のいずれでも使用できます。

distance関数

std::distance関数を使うと、2つのイテレータ間の距離を調べることができます。
distance関数は、iterator という名前の標準ヘッダに含まれています。

distance関数には、2つのイテレータを指定しますが、ともに同じコンテナの要素を指す、 入力イテレータ(派生カテゴリでも良い)で無ければなりません
また、第1引数で指定したイテレータの方が、第2引数で指定したイテレータより手前側または同じ位置を指している必要があります。 この要件を満たしていない場合、未定義の動作になります。

#include <iostream>
#include <list>
#include <iterator>

int main()
{
	typedef std::list<int> IntList;

	const int table[] = {0, 1, 2, 3, 4};

	IntList lst(table, table + 5);

	IntList::const_iterator it = lst.begin();
	const IntList::const_iterator itEnd = lst.end();
	std::advance(it, 3);
	std::cout << std::distance(it, itEnd) << std::endl;

	const int* p = table;
	std::advance(p, 3);
	std::cout << std::distance(p, table + 5) << std::endl;
}

実行結果

2
2

distance関数は、イテレータのカテゴリを判断して、それに応じた実装が使用されるようになっています。
ランダムアクセスイテレータの場合は、単に「it2 - it1」とすることで距離を計算できるので非常に効率的ですが、 他のカテゴリのイテレータの場合は、it1 が it2 に出会うまで ++演算子を適用し続けるような実装になるので、 かなり重い計算になり得ます。

これを実現するために、特性という仕組みが利用されています。

iter_swap関数

std::iter_swap関数を使うと、2つのイテレータが指す先にある要素同士を交換できます。
iter_swap関数は、algorithm という名前の標準ヘッダに含まれています (この関数は iterator には含まれません)。

2つのイテレータは、前方イテレータカテゴリに属している必要があります。 それぞれが、別のコンテナを指すイテレータであっても構いませんが、要素同士は相互に代入できる型でなければなりません。

#include <iostream>
#include <list>
#include <algorithm>

int main()
{
	typedef std::list<int> IntList;

	int table[] = {0, 1, 2, 3, 4};

	IntList lst(table, table + 5);

	IntList::iterator it = lst.begin();
	const IntList::iterator itEnd = lst.end();
	std::advance(it, 3);
	std::iter_swap(lst.begin(), it);
	for (it = lst.begin(); it != itEnd; ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;

	int* p = table;
	std::advance(p, 3);
	std::iter_swap(table, p);
	for (p = table; p != table + 5; ++p) {
		std::cout << *p << " ";
	}
	std::cout << std::endl;
}

実行結果

3 1 2 0 4
3 1 2 0 4

イテレータの変換

iterator から const_iterator へは、暗黙的に型変換できますが、逆はできません。 無理やりキャストすることもできません。

「const は積極的に使うべきである」というのが C++ の基本であり、その考え方をイテレータにも適用すれば、 const_iterator が使えるのなら、iterator よりも優先して使うべきだと言えます。 しかし、STL の関数の中には、変更が必要でないのにも関わらず、引数の型が const_iterator ではなく iterator になっているものがあります。 そのため、const_iterator から iterator へ、簡単に変換できることが望ましいのです。

残念ながら、const_iterator から iterator へ変換する分かりやすい方法はありませんが、 advance関数distance関数を利用することで、目的を果たすことは可能です

#include <iostream>
#include <list>
#include <iterator>

int main()
{
	typedef std::list<int> IntList;

	const int table[] = {0, 1, 2, 3, 4};

	IntList lst(table, table + 5);

	// 4番目の要素を指す const_iterator を作る
	IntList::const_iterator cit = lst.begin();
	std::advance(cit, 3);

	IntList::iterator it = lst.begin();  // 先頭を指す iterator
	std::advance(it, std::distance<IntList::const_iterator>(it, cit));  // const_iterator を iterator に変換

	lst.insert(it, 9);

	const IntList::const_iterator citEnd = lst.end();
	for (cit = lst.begin(); cit != citEnd; ++cit) {
		std::cout << *cit << " ";
	}
	std::cout << std::endl;
}

実行結果

0 1 2 9 3 4

list の insertメンバ関数に渡すイテレータは、const_iterator ではなく iterator です。 このプログラムで言えば、it を渡すことはできますが、cit を渡すことはできません。

C++11 では、const_iterator に修正されているので、iterator に変換する必要はありません。 VisualC++ 2013/2015、clang 3.7 ではすでに修正されています。

const_iterator から iterator に変換するには、以下の手順を取ります。

  1. 目的の要素を指す const_iterator がある(作る)
  2. 先頭の要素を指す iterator を作る
  3. distance関数の第1引数に 2 で作った iterator を、第2引数に 1 の const_iterator を指定し、距離を得る
  4. 3 で得た距離を指定して advance関数を呼び出し、2 で作った iterator を進める

結果、iterator は、const_iterator と同じ位置を指すようになりますから、変換(というか複製が)出来たことになります。

少々厄介なことに、distance関数に渡す2つの引数が、それぞれ iterator と const_iterator になるため、 型が一致せず、テンプレート引数の型推測に失敗します。 そこで、明示的にテンプレート引数を指定する必要があります(このとき、当然 const_iterator の方を指定します)。

なお、advance関数も distance関数も、ランダムアクセスイテレータであれば効率的ですが、 他のカテゴリのイテレータの場合は、非効率な処理になることに注意が必要です。 そのため、そもそも const_iterator を使うことを諦めることも、有力な手段として検討するべきです。

C++11 (引数の型の見直し)

C++11 において、引数の型が見直され、const_iterator であるべき箇所は const_iterator に修正されています。 そのため、この項で取り上げたような問題は無くなっており、積極的に const_iterator を使えるようになりました。


練習問題

問題@ どの STLコンテナに対しても使えるように、すべての要素の値を標準出力へ書き出す、関数テンプレートを作成して下さい。


解答ページはこちら

参考リンク

更新履歴

'2016/10/15 clang の対応バージョンを 3.7 に更新。

'2016/5/7 「C++14 (非メンバ関数の cbegin、cend)」の項を追加。
幾つか、実行結果が抜けていたサンプルに、実行結果を付加。
この章の概要」に、C++11/14 の各項へのリンクを追加。

'2015/11/7 新規作成。



前の章へ

次の章へ

C++編のトップページへ

Programming Place Plus のトップページへ