先頭へ戻る

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

Programming Place Plus トップページ新C++編

先頭へ戻る

このページの概要

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

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



イテレータ(反復子)

前のページで 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文を使って出力するコードです。2つの範囲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文では、「先頭の要素から1つ1つ順番に末尾まで」というアクセスしかできません。なお、範囲for文で書いたコードは、コンパイラによって、イテレータを使ったコードに変換されます。つまり、範囲for文を使って書いたとしても、結局はイテレータを使っていることになります。

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

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

イテレータの機能

ではさきほどのコードを解説します。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 です。これは非常に長ったらしいですが、簡潔に済ませる方法もあるので、後で取り上げます

イテレータ型の変数に格納される値は、対象のデータ構造の中にある1つの要素を指し示しているのだという情報です。要素そのものではないことに注意してください。これは参照型の変数の考え方に似ています(参照型については「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)の動作は保証されません2

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

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

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

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

auto

イテレータの型名はとても長く、いちいち書くのが面倒です。これまでのページでも constexpr変数の宣言でよく使っていましたが、auto を用いると簡潔に書けます。

#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

型名を auto にして宣言された変数は、初期化子の内容に応じて、コンパイラがコンパイル時に型を自動的に決定します。このような動作を型推論 (type inference) と呼びます。

このコードでは、初期化子が = std::begin(v) なので、std::begin関数が返す値の型になります。std::begin関数が返す値は 、std::vector<int> のイテレータですから、型は std::vector<int>::iterator です。ちなみにここで、auto it {std::begin(v)} のようにリスト初期化の構文を使うと、型推論の結果が変わってしまい、うまくいきません。

【上級】auto a {std::begin(v)};auto a = {std::begin(v)}; のように、auto と {} の組み合わせでは、std::initializer_list<std::vector<int>::iterator> に推論されます(ただし、C++17 で仕様変更)。

【上級】【C++17】auto a {std::begin(v)}; のように、{} の内側の要素が1つの場合で、かつ = を使わない場合、その要素の型に推論されるようにルールが変更されました。したがって、変数a は std::vector<int>::iterator になります。= を使った場合は以前のままで、auto a = {std::begin(v)}; は std::initializer_list<std::vector<int>::iterator> に推論されます。

型が初期化子によって決まるということは、auto を使うのならば、初期化子から型が判断可能でなければならないということです。そのため、auto n; とか auto n {}; のような宣言はできません。これは、変数を未初期化のまま宣言してしまう過ちを防ぐ効果があるともいえます。

なお、次の変数宣言では、std::string型に型推論されません。

auto s = "Hello";

コンパイルは可能ですが、これは別の型になっています。std::string に関する機能が使えませんが、これでも文字列としては機能します。

【上級】auto s = "Hello"; の型推論の結果は const char* です。文字列リテラルの型は const char の配列型で、それがポインタに変換されるためです。std::string に型推論させたければ、auto s = "Hello"s; のように sサフィックスを用いる方法があります。ただし、この方法を使うには、事前に using namespace std::literals::string_literals;(あるいは using namespace std; だけでもいい)という記述が必要です。3

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関数に変わっています。この2つの関数は 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::reverse4 を使って、範囲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 イテレータ(つまり、データ構造の先頭の要素の手前を指す逆イテレータ)を返します。ややこしいですが、単に逆方向に辿るようになったというだけのことなので、機械的に、

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

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

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

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

 01234
 ^    ^
 b    e

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

 01234
^    ^
re   rb

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

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

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

const逆イテレータ

逆イテレータの constイテレータ版もあります。

#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

型名の reverse_iterator の部分を const_reverse_iterator に置き換えます(auto でも構いません)。std::rbegin関数は std::crbegin関数に、std::rend関数は std::crend関数に置き換えます。


まとめ


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


参考リンク


練習問題

問題の難易度について。

★は、すべての方が取り組める入門レベルの問題です。
★★は、自力でプログラミングができるようなるために、入門者の方であっても取り組んでほしい問題です。
★★★は、本格的にプログラマーを目指す人のための問題です。

問題1 (確認★)

次の各変数の型は何になりますか?(v は std::vector<int> の変数とします)。

  1. auto x = 0;
  2. auto x = 0.0;
  3. auto x = 3.5 + 10;
  4. auto x = std::begin(v);
  5. auto x = std::cbegin(v);
  6. auto x = std::rbegin(v);
  7. auto x = std::crbegin(v);
  8. auto x = v;

解答・解説

問題2 (基本★)

標準入力から整数を5つ入力させ、std::vector に格納するプログラムを作成してください。

この問題は、「std::vector」のページの練習問題でも出題しました。今回は、イテレータを用いるようにしてみてください。

解答・解説

問題3 (基本★★)

std::vector の内容を constイテレータを使った方法で出力する for文を書き、何番目の要素であるかをあらわす連番もセットで出力されるようにしてください。

たとえば、次のようなイメージです。

0: 5
1: 8
2: 3
3: 10
4: 6

解答・解説

問題4 (基本★★)

標準入力から文字列を5つ入力させ、std::vector に格納したあと、入力された順番とは逆の順番で出力するプログラムを作成してください。

この問題は、「std::vector」のページの練習問題でも出題しました。今回は、イテレータを用いるようにしてみてください。

解答・解説

問題5 (応用★★★)

問題4のプログラムを改造して、文字列それぞれについても逆順(“Hello” なら “olleH”)に出力するようにしてください。

解答・解説


解答・解説ページの先頭



更新履歴




はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー