イテレータ

イテレータとは

コンテナ型(vectorクラスなど)の要素へのアクセスにはイテレータ(反復子)というものがたびたび登場します。
イテレータを一言で表すならば「ポインタのようなもの」です。

配列やarrayクラス、vectorクラスは、メモリ上に配置されるデータは「先頭の要素から順番に、最後まで隙間なく並べられる」ことが保証されています。
このようなデータへのアクセスはポインタだけでも可能です。

//メモリ上へは連続して配置される
int arr[]{ 1, 2, 3, 4, 5 };
int *pointer = arr;

//メモリ上では、arr[1]にはarr[0]の
//次の要素が格納されていることが保証されている
//なお、以下のふたつは全く同じ意味
std::cout << pointer[1] << std::endl;
std::cout << *(pointer + 1) << std::endl;

しかし、他のコンテナ型ではメモリのあちこちにデータが散らばって配置されることがあります。
ポインタ変数pointerに対するpointer[1]は「pointerのアドレスが示すメモリ位置のひとつ後ろの値」でしかなく、メモリ上のデータの連続性が保証されていない場合はそこにどんなデータがあるかはわかりません。
そのため、ポインタを用いて前後の要素にアクセスする方法は使えません。
このようなデータに対してポインタのように比較的簡単にデータにアクセスする方法を提供するのがイテレータです。

宣言と使用

イテレータは次のように使用を宣言します。
以下はvectorクラスでの例です。

std::vector<int> vec{ 1, 2, 3, 4, 5 };

//vecの先頭要素を示すイテレータ
std::vector<int>::iterator it1;
it1 = vec.begin();

//宣言と同時に初期化するなら以下でも良い
std::vector<int>::iterator it2 = vec.begin();

//vecの末尾要素の次を示すイテレータ
std::vector<int>::iterator it3 = vec.end();

vectorクラスのイテレータの型はstd::vector<データ型>::iterator型です。
「データ型」の部分はvectorクラスが管理するデータ型によって変わります。

std::vector<int> vec;

//以下は同じデータ型
std::vector<int>::iterator it1;
auto it2 = vec.begin();
decltype(vec)::iterator it3;

要素へのアクセス

先頭要素を指すイテレータを取得するにはbegin関数を使用します。
最後の要素の次の要素はend関数で取得できます。

要素へのアクセスは*演算子で行います。
[]でインデックスを指定してアクセスすることもできます。
次の要素へは++演算子、前の要素へは--演算子で移動できます。
つまりポインタと同じ操作が可能です。

#include <iostream>
#include <string>
#include <vector>

int main()
{
    std::vector<int> vec{ 1, 2, 3, 4, 5 };
    std::vector<int>::iterator it = vec.begin();

    //itが指す要素を表示
    std::cout << *it << std::endl;
    //1

    //要素番号を指定してアクセス
    std::cout << it[3] << std::endl;
    //4
    
    //次の要素に移動
    it++;
    std::cout << *it << std::endl;
    //2

    //手前の要素に移動
    it--;
    std::cout << *it << std::endl;
    //1

    //3つ後ろの要素に移動
    it += 3;
    std::cout << *it << std::endl;
    //4

    it++;
    if (it == vec.end()) {
        std::cout << "終端" << std::endl;
    }
    else {
        std::cout << *it << std::endl;
    }
    //5

    it++;
    if (it == vec.end()) {
        std::cout << "終端" << std::endl;
    }
    else {
        std::cout << *it << std::endl;
    }
    //終端
 
    std::cin.get();
}

注意点として、end関数は末尾要素ではなく末尾要素の次の要素へのアクセスです。
これはコンテナの終端を示すためのもので、この要素自体は存在しないので、そのままアクセス(値の読み書き)することは未定義動作です。

class C
{
public:
	int x;
	int y;

	C(int a, int b) : x(a), y(b) {};

};

int main()
{
	std::vector<C> vec{
		{ 1, 2 },
		{ 3, 4 }
	};

	std::vector<C>::iterator it = vec.begin();
	std::cout << it->x << " " << (*it).y << std::endl;
}

1 2

constイテレータ

イテレータを通して値の書き換えを行わない場合はconstイテレータを使用することができます。
(C++11以降)
constイテレータはcbegin関数、cend関数で取得できます。
vectorクラスのconstイテレータはstd::vector<データ型>::const_iterator型です。

std::vector<int> vec{ 1, 2, 3 };

//通常のイテレータ
std::vector<int>::iterator it = vec.begin();
//値の書き換え可
*it = 9;

//constイテレータ
std::vector<int>::const_iterator cit = vec.cbegin();
//値の書き換え不可
//*cit = 9;

なお、コンテナクラス自体をconst宣言した場合、begin関数やend関数はstd::vector<データ型>::const_iterator型を返すようになります。

std::vector<int> vec1{ 1, 2, 3 };

std::vector<int>::iterator it1 = vec1.begin();				//通常のイテレータ
std::vector<int>::const_iterator it2 = vec1.begin();		//constイテレータ
const std::vector<int>::iterator it3 = vec1.begin();		//イテレータをconst
const std::vector<int>::const_iterator it4 = vec1.begin();	//constイテレータをconst

*it1 = 9;
it1++;

//*it2 = 9;	//要素の書き換え不可
it2++;

*it3 = 9;
//it3++;		//イテレータ演算不可

//*it4 = 9;	//要素の書き換え不可	
//it4++;		//イテレータ演算不可

const std::vector<int> vec2{ 1, 2, 3 };

//const外しになるのでコンパイルエラー
//std::vector<int>::iterator cit = vec2.begin();

//const_iterator型を使う
std::vector<int>::const_iterator cit = vec2.begin();

逆イテレータ

イテレータは要素の先頭はbegin関数で、要素の末尾はend関数でアクセスします。
この前後を逆にアクセスするイテレータを逆イテレータといいます。

逆イテレータはrbegin関数とrend関数で取得します。
rbegin関数は末尾要素、rend関数は先頭要素の手前の要素へのアクセスです。
これらはstd::コンテナクラス<データ型>::reverse_iterator型を返します。

std::vector<int> vec{ 1, 2, 3, 4, 5 };

//逆イテレータ
std::vector<int>::reverse_iterator rit = vec.rbegin();

while (rit != vec.rend()) {
	std::cout << *rit << " ";
	rit++;
}

5 4 3 2 1

crbegin、crend関数

crbegin関数、crend関数は、const版の逆イテレータを取得します。
要素を書き換えられない以外はrbegin関数、rend関数と同じです。
const逆イテレータはstd::コンテナクラス<データ型>::const_reverse_iterator型です。

ポインタとは異なる点

要素アクセス方法の制限

コンテナ型によっては、移動方法が制御されているイテレータが存在します。
例えば移動方向が制限されているクラスでは、要素の位置を進めること(it++)はできても戻ること(it--)はできないものがあります。
ランダムアクセスができないコンテナ型では、it[3]や、it + 3といった方法で要素にアクセスすることはできません。
つまりit++やit--で要素を順番にたどって行く移動方法しか許されていません。

これらの違いは、それぞれのコンテナ型の特徴に起因します。
不便に思えるような実装も、特定の用途では配列やvectorなどよりも便利に扱える場合があります。

いままで紹介したarrayクラス、vectorクラス、stringクラスはこのような制限はなく、全ての方法での移動が可能です。
他のコンテナ型についてはSTLコンテナの項で説明しています。

異なるコンテナクラスのデータの互換性

扱うデータ型が同じでも、コンテナクラスが異なる場合はそのイテレータ同士は別のデータ型です。
int型を管理するarrayクラスのイテレータとint型を管理するvectorクラスのイテレータはそのままでは互換性はありません。
イテレータが指す要素の中身自体は同じデータ型なので互いに代入等はできます。

//これは「std::vector<int>::iterator」型
std::vector<int>::iterator itVec;

//これは「std::list<int>::iterator」型
std::list<int>::iterator itList;

扱うデータ型が同じ場合、以下のようにすることで互いの要素を変換することが出来ます。

std::array<int, 5> arr{ 1, 2, 3, 4, 5 };

//コンストラクタにイテレータの範囲を指定することで
//その範囲を要素とする新しいvectorインスタンスを生成できる
std::vector<int> vec(arr.begin(), arr.end());

上記のコードは、arrayクラスの先頭要素から末尾要素(の次の要素)を範囲指定しています。
これにより、arrが持つすべての要素を新しいvectorクラスにコピーしています。
コンストラクタで指定する以外にも、vectorクラスならassign関数で同様のことができます。

データが連続していないクラスの検証コード

以下はメモリ上にデータが連続して配置されないコンテナクラスの検証コードです。
listクラスはまだ説明していませんが、メモリ上のデータ配置に連続性がないクラスです。

#include <iostream>
#include <vector>
#include <list>

int main()
{
    std::vector<int> vec{ 55, 3, 97, -21, 6 };
    std::list<int> lst{ 55, 3, 97, -21, 6 };

    std::vector<int>::iterator itVec = vec.begin();
    std::list<int>::iterator itLst = lst.begin();

    //vectorの各要素のアドレスを表示
    std::cout << "vector" << std::endl;
    while (itVec != vec.end())
    {
        std::cout << &(*itVec) << std::endl;
        itVec++;
    }

    //listの各要素のアドレスを表示
    std::cout << "\nlist" << std::endl;
    while (itLst != lst.end())
    {
        std::cout << &(*itLst) << std::endl;
        itLst++;
    }

    std::cin.get();
}

vector
00EDB618
00EDB61C
00EDB620
00EDB624
00EDB628

list
00EE1048
00EE1080
00EE1068
00EE10B8
00EE1058

※実行結果は実行毎に異なります。

vectorクラスはアドレスが4ずつ(int型ひとつ分)増えていることが確認できますが、listクラスはそういった規則性はありません。

イテレータ使用時の注意点

arrayクラスを除き、コンテナ型は値の削除や追加が自由に行えます。
これは便利な反面、気を付けないとバグのあるコードを書いてしまいます。

vectorクラスでは、途中の要素を削除した場合は後ろのデータは前にずらされます。

この時、その「後ろのデータ」や、「今削除した要素」を指しているイテレータは使用できなくなります。
データの移動により、正しい位置情報ではなくなっているためです。

//間違いコード

std::vector<int> vec{ 1, 2, 3, 4, 5 };
std::vector<int>::iterator it = vec.begin();

++it;
vec.erase(it);

//ここでエラー
std::cout << *it << std::endl;

また、insert関数やpush_back関数などで要素を増やしたとき、確保していたメモリ領域が足りなくなると別の領域にメモリを確保し、そこを新しい管理領域とします。
つまりアドレスが変わるので、それ以前に保存していたイテレータも無効になります。

insert関数やerase関数など、要素のアドレスが変わるような関数はイテレータを戻り値にするものがあります。
その戻り値を新しいイテレータとして使用すればエラーを防ぐことができます。

std::vector<int> vec{ 1, 2, 3, 4, 5 };
std::vector<int>::iterator it = vec.begin();

++it;
//戻り値をイテレータに代入
it = vec.erase(it);

//正常に表示可能
std::cout << *it << std::endl;

ループ文を利用して、vectorから条件に合う要素を削除する場合は以下のようにします。

std::vector<int> vec1{ 1, 2, 3, 4, 5 };
std::vector<int>::iterator it1 = vec1.begin();

//値が偶数の要素を削除
while (it1 != vec1.end())
{
	if (*it1 % 2 == 0)
		it1 = vec1.erase(it1);
	else
		++it1;
}

//for文で書く場合
std::vector<int> vec2{ 1, 2, 3, 4, 5 };
//再初期化式(括弧内のみっつ目の式)で
//イテレータをインクリメントしないこと
for (std::vector<int>::iterator it2 = vec2.begin(); it2 != vec2.end();)
{
	if (*it2 % 2 == 0)
		it2 = vec2.erase(it2);
	else
		++it2;
}

他のコンテナクラスでもデータの追加/削除を行うと、それまで保存していたイテレータが無効になることがあります。
詳しくはSTLコンテナ#イテレータの無効化の項で改めて説明します。

イテレータの移動関数

arrayクラスやvectorクラスのイテレータは、ポインタと同じように+演算子や[]演算子でイテレータの位置を自由に移動(ランダムアクセス)することができます。
しかし、これらの演算子でイテレータを移動できないコンテナクラスもあります。
その場合は++演算子などでひとつずつ要素をたどっていくのですが、これを簡単に記述する方法が提供されています。

なお、これらの関数はコンテナクラスがサポートする移動のみが可能です。
例えばforward_listクラスは前方向への移動のみ可能なクラスなので、これらの関数でも逆方向への移動はできません。

std::advance関数

イテレータを任意の数移動するにはstd::advance関数を使用します。

#include <list>

int main()
{
	std::list<int> lst = { 1, 2, 3, 4, 5 };
	std::list<int>::iterator it = lst.begin();

	//listクラスはランダムアクセスができない
	//以下はコンパイルエラー
	//int n = it[3];

	//イテレータを3つ進める
	std::advance(it, 3);
	int n = *it;
	//4

	//イテレータを2つ戻す
	std::advance(it, -2);
	n = *it;
	//2
}

std::next関数、std::prev関数

std::advance関数はイテレータを書き換えますが、std::next関数、std::prev関数は移動後のイテレータのコピーを取得します。
つまり元のイテレータは書き換わりません。
これらの関数はC++11から使用できます。

#include <list>

int main()
{
    std::list<int> lst = { 1, 2, 3, 4, 5 };

    std::list<int>::iterator it = lst.begin();

    //itを1つ進めたコピーを得る
    std::list<int>::iterator it2 = std::next(it);
    int n = *it2;
    //2

    //itを3つ進めたコピーを得る
    std::list<int>::iterator it3 = std::next(it, 3);
    n = *it3;
    //4

    //元のイテレータはそのまま
    n = *it;
    //1
}

std::distance関数

ふたつのイテレータの距離はstd::distance関数で調べることができます。

#include <list>

int main()
{
    std::list<int> lst = { 1, 2, 3, 4, 5 };

    std::list<int>::iterator it1 = lst.begin();
    std::list<int>::iterator it2 = lst.end();

	it1++;
	it2--;

    std::size_t dist = std::distance(it1, it2);
    //3
}

この関数は要素数を取得するsize関数が提供されていないforward_listクラスで、要素数を取得するためにも使用されます。

#include <forward_list>

int main()
{
	std::forward_list<int> flist{ 1, 2, 3, 4, 5 };

	//forward_listにはsizeメンバ関数がない
	//flist.size();

	std::size_t size = std::distance(flist.begin(), flist.end());
	//5
}