イテレータ | Programming Place Plus　新C++編

このページの概要

このページでは、イテレータと呼ばれる仕組みについて取り上げます。イテレータを使うと、複数の要素が集まった構造に対するアクセスを、その構造が具体的に何であるかに関わらず、同じ方法、同じコードで行えるようになります。今のところ、std::vector と std::string でしか使いどころがないですが、今後、さまざまな構造が登場すると、この価値が明らかになります。このページではまず、イテレータの概要について取り上げ、より応用的な使い方は、この先のページで取り上げていきます。

以下は目次です。要点だけをさっと確認したい方は、「まとめ」をご覧ください。

• イテレータ（反復子）
• イテレータの機能
  • auto
• constイテレータ
• 逆イテレータ
  • const逆イテレータ
• まとめ
• 練習問題
• 参考リンク
• 更新履歴

イテレータ（反復子）

前のページで std::vector を解説し、複数の変数をひとまとめにした変数（配列）を実現できるようになりました。しかし、前のページで解説した内容は、std::vector の機能のごく一部に過ぎません。特に、std::vector は、要素を追加したり削除したりできます。現在の目標である蔵書リストのプログラムには、この機能が欠かせませんが、要素の追加と削除の方法の前に少し寄り道をして、イテレータ（反復子）(iterator) と呼ばれる機能を説明しておきます。やり方次第ですが、要素の追加や削除を行うときに、イテレータが必要になる場合があるためです。

イテレータとは、「配列のような複数の要素の集まり（データ構造 (data structure)）に対して、その中にある各要素にアクセスする処理」を抽象化するしくみです。難しいことをいっているようですが、実はすでに範囲for文（「std::vector」のページを参照）は、この抽象化というものをしています。

std::vector<int> v {0, 1, 2};
for (int e : v) {
    std::cout << e << "\n";
}

std::string s {"ABC"};
for (char e : s) {
    std::cout << e << "\n";
}

std::vector<int> と std::string の各要素の値を範囲for文を使って出力するコードです。２つの範囲for文は、型の違いこそありますが、コードのかたちはまったく同じになっています。つまり、範囲for文という仕組みを使って、「配列のような複数の要素の集まりに対して、その中にある各要素にアクセスする処理」を抽象化しています。コードが共通化されると言い換えてもらっても構いません。

イテレータの場合、同じことを次のように書きます（詳しい解説は後でします）。

std::vector<int> v {0, 1, 2};
for (std::vector<int>::iterator it {std::begin(v)}; it != std::end(v); ++it) {
    std::cout << *it << "\n";
}

std::string s {"ABC"};
for (std::string::iterator it {std::begin(s)}; it != std::end(s); ++it) {
    std::cout << *it << "\n";
}

かえって大変になったようですが、範囲for文のほうが後から加わった機能なため、簡潔に書けるようになったという流れがあります。その代わり範囲for文では、「先頭の要素から１つ１つ順番に末尾まで」というアクセスしかできません。なお、範囲for文で書いたコードは、コンパイラによって、イテレータを使ったコードに変換されます。つまり、範囲for文を使って書いたとしても、結局はイテレータを使っていることになります。

【上級】範囲for文で書いたコードがどのように変換されるかについては、明確な仕様があります。¹

イテレータを直接使ってコードを書くと、逆方向から辿ったり、いくつか要素を飛ばしながら辿ったりすることも可能になります。

イテレータの機能

ではさきほどのコードを解説します。std::string の方も考え方はまったく同じなので、ここでは std::vector だけを使って解説していきます。

まず、コンパイル、実行ができるプログラムを以下に示します。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v {0, 1, 2};

    for (std::vector<int>::iterator it {std::begin(v)}; it != std::end(v); ++it) {
        std::cout << *it << "\n";
    }
}

実行結果：

0
1
2

for文のところで、イテレータを変数として宣言しています。イテレータの型は、対象のデータ構造に応じて決まり、std::vector<int> なら、std::vector<int>::iterator ですし、std::string なら std::string::iterator です。これは非常に長ったらしいですが、簡潔に済ませる方法もあるので、後で取り上げます。

イテレータ型の変数に格納される値は、対象のデータ構造の中にある１つの要素を指し示しているのだという情報です。要素そのものではないことに注意してください。これは参照型の変数の考え方に似ています（参照型については「std::vector」のページを参照）。要素そのものではないので、要素にアクセスしたいときには、*it のように * を使って明確にしなければなりません。* を使って、イテレータを介して要素をアクセスすることを、デリファレンス (dereference)（参照外し、間接参照などとも）と呼びます。

n = *it;      // イテレータit が指し示す要素の値を、変数n に代入
*it = 100;    // イテレータit が指し示す要素に 100 を代入

n = it;       // イテレータそのものをコピーしている
it = 100;     // 間違い

イテレータの初期化子は、{std::begin(v)} としています。std::begin(v) は、標準ライブラリに含まれている std::begin関数を使うコードです。std::begin関数は、() の内側で指定したデータ構造の先頭の要素を指し示すイテレータを作ってくれます。

for文の条件式は、it != std::end(v) です。std::end(v) は、std::end関数を使っています。std::end関数は、対象のデータ構造の末尾の要素の “さらに後ろ” を指し示すイテレータを作ります。また、!= を使っているように、イテレータどうしを比較することができます。!= なので、両者が異なる要素を指し示している場合に true になります。

std::end関数が返すイテレータが、末尾の要素の「さらに後ろ」を指すという部分は注目すべきです。このような仕様であるから、for文の条件式を it != std::end(v) とすることによって、末尾の要素までアクセスする for文が書けます。もし、末尾の要素そのものを指すイテレータが返される仕様であったとしたら、末尾の要素に達したところで条件式が false になりますから、末尾の要素に対する処理を行わないまま for文を終了してしまいます。

このような、末尾の要素の「さらに後ろ」を指すイテレータを、past-the-end イテレータと呼ぶことがあります。past-the-end イテレータは、実際には要素を指し示していないので、デリファレンス（*it）の動作は保証されません²。

なお、対象のデータ構造に要素がない場合に、std::begin関数や std::end関数を使うと、どちらも同じ past-the-end イテレータが取得されます。そのため、要素がない場合を特別扱いする必要はなく、サンプルプログラムの for文の書き方のままで問題ありません（for文の１回目の条件判定が false になるため、for文の内側に入らない）。

【C++98/03 経験者】以前は v.begin() とか v.end() のように、メンバ関数として宣言された begin関数、end関数を使いましたが、C++11 から、非メンバ関数版の begin関数、end関数が追加されました。非メンバ関数版は、生の配列に対しても適用できるという利点があり、テンプレートを書くときにコードを切り分けずに済むようになります。

++it は、イテレータが指し示す先を１つ後ろの要素へと進めます。想像どおり、--it なら手前側に１つ戻ってきますし、it += 3 のようにして、一気に３つ進めるといったこともできます。もちろん、要素がないところにまで飛び出していってしまうことは、範囲外アクセスを招く危険な行為です。

対象のデータ構造によっては、手前に戻したり、一度に複数動かしたりはできない場合があります。std::vector や std::string では可能です。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v {0, 1, 2};

    for (auto it = std::begin(v); it != std::end(v); ++it) {
        std::cout << *it << "\n";
    }
}

0
1
2

int n {10};
auto a1 = n;    // n だけでは、意図が n の値をコピーしたかったのか、n の別名を作りたかったのか判断できない。
                // auto はつねに、参照型ではないと判断するため、a1 は int型になる。

int& rn {n};
auto a2 = rn;   // rn は明らかに int& だが、やはり auto は参照型とは判断せず、a2 は int型になる。

auto& a3 = rn;  // 必要なら auto の方に & を付ければ、参照型にできる。
                // a3 は int&型になる。

auto s = "Hello";

constイテレータ

イテレータを使い、*it = 100; のようにして、要素を書き換えることをしないのであれば、それを明確に示すと、より良いコードになります。そのためには constイテレータ（const反復子）(const iterator) を用います。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v {0, 1, 2};

    for (std::vector<int>::const_iterator it {std::cbegin(v)}; it != std::cend(v); ++it) {
        std::cout << *it << "\n";
    }
}

実行結果：

0
1
2

型の名前が、std::vector<int>::iterator から std::vector<int>::const_iterator に変わりました（std::string なら std::string::const_iterator）。また、使用している関数も、std::cbegin関数と std::cend関数に変わっています。この２つの関数は constイテレータを返すので、auto を使っても constイテレータ型に推論されます。

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

前述のとおり、constイテレータは *it = 100; のような、要素の書き換えが禁じられますが、それ以外の動作に変化はありません。

for (auto it = std::cbegin(v); it != std::cend(v); ++it) {
    *it = 100;  // エラー
}

「値を書き換えるつもりはない」とか「この変数は書き換えてはならない」のだということを、コメントではなくコードとして示すのは良いことです。使えるときには、通常のイテレータよりも、constイテレータを優先すると良いです。

【C++98/03 経験者】constイテレータを使おうにも、標準ライブラリの関数の中には、通常のイテレータしか受け付けてくれないものがあって困ることがありましたが、C++11 以降はきちんと constイテレータを受け付けるように対応されています。また、cbegin関数や cend関数が追加されたので、作りやすくもなっています。constイテレータを諦める理由はありません。

なお、イテレータと constイテレータは、== などを使って相互に比較可能です。また、イテレータから constイテレータへは暗黙的に型変換できますが、constイテレータからイテレータには変換できません。

auto itEnd = std::cend(v);
if (std::begin(v) == itEnd) {  // OK. イテレータと constイテレータの比較
}

itEnd = std::begin(v);  // OK. イテレータを constイテレータに代入

std::vector<int>::iterator it = std::cend(v);  // エラー。constイテレータからイテレータには変換できない

逆イテレータ

要素を末尾の側から先頭に向かってアクセスしたいときがあります。これは範囲for文では書けませんし、イテレータを直接使っても、実はうまく書けません。

for (auto it = std::end(v); it != std::begin(v); --it) {
    std::cout << *it << "\n";
}

【C++20】std::views::reverse⁴ を使って、範囲for文で書けるようになりました。

std::end関数で得られるイテレータは「末尾の要素の “さらに後ろ”」を指し示すものであるため、auto it = std::end(v) としてしまうと、指し示す要素がない状態で *it を実行してしまいます（-1 する手もありますが、要素がないときに危険です）。また、for文の条件式を it != std::begin(v) としてしまうと、先頭の要素に達した瞬間に for文を終えてしまうため、先頭の要素の値が出力されません。

そこで、逆イテレータ（逆反復子） (reverse iterator) を使います。逆イテレータは、対象のデータ構造を逆方向に辿るためのイテレータです。逆イテレータにとっての「先頭」は、実際にはデータ構造の「末尾」であり、逆イテレータにとっての「後ろの要素」とは、実際のデータ構造では「手前の要素（先頭に近い側の要素）」ということになります。

次のサンプルプログラムは、データ構造の末尾の要素から順に、手前へ向かって、各要素の値を出力します。

#include <iostream>
#include <iterator>
#include <vector>

int main()
{
    std::vector<int> v {0, 1, 2};

    for (std::vector<int>::reverse_iterator it {std::rbegin(v)}; it != std::rend(v); ++it) {
        std::cout << *it << "\n";
    }
}

実行結果：

2
1
0

逆イテレータを使うときには、#include <iterator> が必要です。

std::vector<int> に対する逆イテレータの型は std::vector<int>::reverse_iterator です（std::string なら、std::string_reverse_iterator）。auto を使って、auto it = std::rbegin(it) でも構いません。

std::rbegin関数は、最初の要素を指す逆イテレータを返します。逆イテレータにとっての最初の要素なので、データ構造の末尾の要素を指しています。std::rend関数は、逆イテレータにとっての past-the-end イテレータ（つまり、データ構造の先頭の要素の手前を指す逆イテレータ）を返します。ややこしいですが、単に逆方向に辿るようになったというだけのことなので、機械的に、

• 型名の iterator の部分を、reverse_iterator に置き換え（あるいは auto を使う）
• std::begin関数を std::rbegin関数に置き換え
• std::end関数を std::rend関数に置き換え

とすればいいだけです。++it のところは変更する必要はありません。逆イテレータにとっての「後ろ」とは、データ構造にとっては「手前（先頭に近い側）」だからです。

【C++98/03 経験者】以前は v.rbegin() とか v.rend() のように、メンバ関数として宣言された rbegin関数、rend関数を使いましたが、C++11 から、非メンバ関数版の rbegin関数、rend関数が追加されました。非メンバ関数版は、生の配列に対しても適用できるという利点があり、テンプレートを書くときにコードを切り分けずに済むようになります。

ところで、「逆」であるということだけを漠然と捉えると勘違いしやすいですが、std::begin関数と std::rend関数が返すイテレータが指し示している要素は異なりますし、std::end関数と std::rbegin関数が返すイテレータが指し示している要素も異なります（要素数が１個以下のときは除く）。

値が 0,1,2,3,4 の５つの要素が格納された配列があるとして、begin関数と end関数が返すイテレータが指すのはこの位置です（b が begin、e が end）。

 01234
 ^    ^
 b    e

一方、rbegin関数と rend関数が返すイテレータが指すのはこの位置です（rb が rbegin、re が rend）。

 01234
^    ^
re   rb

４つの関数が返すイテレータは、それぞれ異なる要素を指すことが分かります。

イテレータと逆イテレータは別の型ですし、相互に比較したり代入したりすることもできません。

【上級】std::vector<int>::reverse_iterator rit(it);⁵ や std::vector<int>::iterator it(rit.base());⁶ のようにすることで、相互に変換することは可能ですが、指し示す要素が１つずれるため注意が必要です。イテレータを逆イテレータに変換した場合は１つ手前（先頭に近い側）にずれますし、逆イテレータをイテレータに変換した場合は１つ後ろにずれます。そのため、たとえば std::begin関数で得たイテレータを逆イテレータに変換すると、先頭のさらに手前を指します。

#include <iostream>
#include <iterator>
#include <vector>

int main()
{
    std::vector<int> v {0, 1, 2};

    for (std::vector<int>::const_reverse_iterator it {std::crbegin(v)}; it != std::crend(v); ++it) {
        std::cout << *it << "\n";

        // *it = 100; のような書き換えはエラーになる
    }
}

2
1
0

まとめ

• イテレータは、配列のような複数の要素の集まり（データ構造）に対して、その中にある各要素にアクセスする処理を抽象化する仕組みである
• イテレータは１つの要素を指し示している
• イテレータの型は、対象のデータ構造によって異なる（std::vector<int>::iterator や std::string::iterator のように）
  • イテレータの型名は長くなりがちだが、auto を使うと簡潔に書ける（auto it = std::begin(v); のように）
• イテレータは、std::begin関数や std::end関数を使って取得できる
  • std::begin関数は、対象のデータ構造の先頭の要素を指し示すイテレータを返す
  • std::end関数は、対象のデータ構造の末尾の要素のさらに後ろを指し示すイテレータ（past-the-end イテレータ）を返す
• イテレータに、* という演算子を使うことで、指し示す先の要素をアクセスできる
• イテレータは、++、+=、--、-= といった演算子を使って、指し示す要素を変更できる
• イテレータを使って要素を書き換えることがない場合、constイテレータを使うと良い
  • constイテレータの型は、std::vector<int>::const_iterator など
  • constイテレータを取得するには、std::cbegin関数や std::cend関数を用いる
  • イテレータは constイテレータに暗黙的に変換できるが、constイテレータからイテレータへは変換できない
  • イテレータと constイテレータを比較することはできる
• 逆方向に要素をたどる場合は、逆イテレータを用いる
  • 逆イテレータの型は、std::vector<int>::reverse_iterator など
  • 逆イテレータを取得するには、std::rbegin関数や std::rend関数を用いる
• 逆イテレータの constイテレータ版もある
  • const逆イテレータの型は、std::vector<int>::const_reverse_iterator など
  • const逆イテレータは、std::crbegin関数や std::crend関数によって取得できる

新C++編の【本編】の各ページには、末尾に練習問題があります。ページ内で学んだ知識を確認する簡単な問題から、これまでに学んだ知識を組み合わせなければならない問題、あるいは更なる自力での調査や模索が必要になるような高難易度な問題をいくつか掲載しています。