イテレータ | Programming Place Plus Modern C++編【標準ライブラリ】 第9章

トップページModern C++編

Modern C++編は作りかけで、更新が停止しています。代わりに、C++14 をベースにして、その他の方針についても見直しを行った、新C++編を作成しています。
Modern C++編は削除される予定です。

この章の概要

この章の概要です。


概要

イテレータ(反復子)は、コンテナに含まれている各要素へのアクセスを行うためのオブジェクトです。一応、反復子という訳語がありますが、反復処理に特化しているわけではないので、あまり訳語に惑わされない方がいいように思います。

なお、コンテナは、std::vector や std::array のように、複数のデータの入れ物になるデータ構造のことです。

イテレータをイメージするにあたっては、ポインタをイメージすることが基本です。つまり、イテレータは、ある要素を指し示します。ただし、指し示せるものは、コンテナの要素(と末尾要素の1つ後ろ)に限られます。そして、*演算子や ->演算子を使って要素へアクセスしたり、++演算子や –演算子を使って、指し示す位置を移動したりできます。実際には、イテレータにも種類があって、行える操作に違いがあります(これはあとで取り上げます)。

ただし、イテレータ=ポインタというわけではなく、ポインタに近い方法で使えるように設計されているだけです。そのため、イテレータという型で扱うべきなのに、ポインタ型で扱うようなプログラムを書くことは間違っています。

イテレータを使うことで、コンテナの内部がどんな構造をしていても、同じ方法でアクセスを行うことができるという訳です。言い換えると、データ構造が何であっても構わないように、要素を操作する処理を抽象化する仕組みです。

標準ライブラリでは、イテレータとコンテナにさらに、STLアルゴリズム(第29章)と呼ばれる機能が加わることで、データ処理の仕組みが確立されています。コンテナが「データ」を、STLアルゴリズムが「処理」を表し、両者をイテレータが仲介するという構成を取ります。

この章では、イテレータそのものに関する話題だけを扱いますし、それだけでも便利に使えますが、STLアルゴリズムも使えるようになると、C++ でのプログラミングは大幅に楽になります。

たとえば、STLアルゴリズムにはソートやサーチの機能があります。これを使えば、コンテナの種類を問わずに、同じ方法でデータをソートしたり、サーチしたりできます。STLアルゴリズムを学習していない段階では、ソートやサーチのコードは自力で書かなければなりませんが、イテレータを使って、コンテナの種類の違いを吸収できます。

基本操作

イテレータには型があります。イテレータは、コンテナの種類の違いを吸収する仕組みではありますが、イテレータの型自体は、扱うコンテナの種類によって異なります。std::vector のイテレータは、std::vector<>::iterator型(第6章)ですし、std::array なら、std::array<>iterator型(第7章)です。配列なら、その要素のポインタ型です。

イテレータを使うには、まず、有効なイテレータを取得する必要があります。そのためには、std::begin関数std::end関数を使います。前者は、コンテナの先頭にある要素を指すイテレータを返し、後者は、コンテナの末尾要素の1つ後ろを指すイテレータを返します。これらの関数は、<iterator> という名前の標準ヘッダにあります。

なお、std::begin関数は、コンテナが空の場合には、std::end関数が返すイテレータと同じ結果を返します。

std::begin関数、std::end関数は、コンテナの種類を問わずに使えるように、関数テンプレートとして実装されています。多くのコンテナでは汎用的なバージョンが使用されますが、配列や std::initializer_list などの一部の型については、専用特化したバージョンがオーバーロードされています。とはいえ、この事実はあまり気にしなくてもよく、ともかく、コンテナの種類を問わずに使えるということを知っておけばいいでしょう。

std::vector や std::array といった標準ライブラリのコンテナ類には、メンバ関数版の begin関数や end関数があります。C++11 よりも前の C++ では、メンバ関数版しかなかったため、メンバ関数版を使ったプログラムを見かけることがあるかもしれません。C++11 以降では、非メンバ関数の std::begin、std::end を使った方が、配列にも対応でき、コードの共通化を図りやすくなります。

配列以外に対する std::begin関数、std::end関数は、メンバ関数版の begin関数、end関数を呼び出すように実装されているので、していることに変わりはありません。

以下は、イテレータを使ったサンプルプログラムです。

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

int main()
{
    using DoubleArray = std::array<double, 3>;
    using IntVector = std::vector<int>;

    int table[] = {0, 1, 2};
    DoubleArray ary = {1.1, 2.2, 3.3};
    IntVector vec = {5, 10, 15};

    const int* itEndTable = std::end(table);
    for (int* itTable = std::begin(table); itTable != itEndTable; ++itTable) {
        std::cout << *itTable << std::endl;
    }

    const DoubleArray::iterator itEndArray = std::end(ary);
    for (DoubleArray::iterator itArray = std::begin(ary); itArray != itEndArray; ++itArray) {
        std::cout << *itArray << std::endl;
    }

    const IntVector::iterator itEndVec = std::end(vec);
    for (IntVector::iterator itVec = std::begin(vec); itVec != itEndVec; ++itVec) {
        std::cout << *itVec << std::endl;
    }
}

実行結果:

0
1
2
1.1
2.2
3.3
5
10
15

イテレータの型は、対象が配列ならポインタ、それ以外のコンテナなら「iterator」という名前のメンバ型です。

イテレータに対して、++演算子を適用することで、指し示す要素を1つ先へ進めます。また、*演算子で要素を参照できます。末尾に達したかどうかを判定するためには、末尾要素の1つ後ろを指すイテレータ(つまり、std::end関数が返したイテレータ)との比較を行えばよいです。

ループの終了判定の際に、「<」ではなく「!=」を使っていることに注意してください。後の項で取り上げますが、コンテナの種類によっては、イテレータの大小を比較できません。

std::vector や std::array、配列といった構造は、要素がメモリ上で連続的に並んでいることが保証されていますから、大小比較でも問題ありませんが、連結リストや木のような構造では、メモリ上での要素の配置はばらばらなので、大小比較ができません。

イテレータの目的は、コンテナの違いを吸収することにあるので、通常は「!=」を使った方が良いです。

ただし「!=」を使うと、何らかの間違いで、末尾要素を飛び越えたところへイテレータが進んでしまったときに、ループが続行してしまう問題が起こる可能性はあります。

処理を共通化する

前の項のコードを見ると、対象が配列でも std::array でも std::vector でも、同じ形をしていることが分かります。これはつまり、テンプレートを使って共通化が可能だということでもあります。たとえば、次のように関数化できます。

template <typename C>
void PrintContainer(C& c)
{
    const typename C::iterator itEnd = std::end(c);
    for (typename C::iterator it = std::begin(c); it != itEnd; ++it) {
        std::cout << *it << std::endl;
    }
}

イテレータの型名は「C::iteartor」のように表現できます。「C」がテンプレート仮引数の名前であるため、「C::iterator」全体を型名と認識させるためには、typename指定子の付加が必要です(【言語解説】第8章)。

これが理想的ではあるし、イテレータの価値はここにあるのですが、現実には配列という厄介者がいます。実際、この関数に配列を渡すと、コンパイルエラーになります。配列はクラスではないので、iterator というメンバ型がなく、「C::iterator」のように表記しても、そのようなものは見つからないためです。

そこで、配列への対応も必要なのであれば、配列バージョンをオーバーロードします。全体としては、次のようになります。

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

template <typename C>
void PrintContainer(C& c)
{
    const typename C::iterator itEnd = std::end(c);
    for (typename C::iterator it = std::begin(c); it != itEnd; ++it) {
        std::cout << *it << std::endl;
    }
}

template <typename T, std::size_t N>
void PrintContainer(T (&c)[N])
{
    T* const itEnd = std::end(c);
    for (T* it = std::begin(c); it != itEnd; ++it) {
        std::cout << *it << std::endl;
    }
}

int main()
{
    int table[] = {0, 1, 2};
    std::array<double, 3> ary = {1.1, 2.2, 3.3};
    std::vector<int> vec = {5, 10, 15};

    PrintContainer(table);
    PrintContainer(ary);
    PrintContainer(vec);
}

実行結果:

0
1
2
1.1
2.2
3.3
5
10
15

これで、配列、std::array、std::vector のいずれを使っても、PrintContainer関数を呼ぶだけで、要素の値を出力することが可能になりました。配列の扱いは厄介ですが、STLアルゴリズムに用意されている処理であれば、こういった点も対応済みです。また、自力でプログラムを書く場合には、そもそも配列に対応するかどうかを検討してみてもいいかもしれません。直接、配列を使わず、std::array を使っていれば、std::array<>::iterator が使えるので、専用バージョンを用意する手間はありません。

ところで、PrintContainer関数がしていることは、範囲for文(【言語解説】第3章)で記述できます。

template <typename C>
void PrintContainer(C& c)
{
    for (typename C::reference r : c) {
        std::cout << r << std::endl;
    }
}

template <typename T, std::size_t N>
void PrintContainer(T (&c)[N])
{
    for (T& r : c) {
        std::cout << r << std::endl;
    }
}

実際、範囲for文は、イテレータの仕組みによって実現されています。特によくありがちなコンテナ操作、つまり、先頭から末尾に向かって要素へアクセスするという操作を、for文の簡潔な構造で使えるようにしているのです。この辺りの話題は、【言語解説】第16章で取り上げています。

constイテレータ

前の項で、コンテナの要素の値を出力する PrintContainer関数テンプレートを作成しました。ところで、この関数が行う処理では、イテレータが指している要素の値を変更することがありません。イテレータがポインタのような使い方ができるのであれば、constポインタのように、指し示す先の値を変更しないイテレータもあるのでしょうか。

constポインタに対応する constイテレータがあります。やはり、扱うコンテナの種類によって型が異なり、std::vector は、std::vector<>::const_iterator型(第6章)ですし、std::array なら、std::array<>const_iterator型(第7章)です。配列なら、その要素の constポインタ型です。

constイテレータも、std::begin関数、std::end関数で取得できます。実引数に指定したコンテナが const付きのオブジェクトであれば、constイテレータで返却されます。

あるいは、std::vector や std::array などの標準ライブラリのコンテナの場合、cbeginメンバ関数cendメンバ関数を持っており、これらを使うこともできます。こちらは必ず constイテレータを返します。ただ、配列にはメンバ関数がありませんから、テンプレートを使ってコードを共通化するような用途には向きません。

PrintContainer関数テンプレートのサンプルプログラムを、constイテレータを使うように書き換えてみます。

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

template <typename C>
void PrintContainer(const C& c)
{
    const typename C::const_iterator itEnd = std::end(c);
    for (typename C::const_iterator it = std::begin(c); it != itEnd; ++it) {
        std::cout << *it << std::endl;
    }
}

template <typename T, std::size_t N>
void PrintContainer(const T (&c)[N])
{
    const T* const itEnd = std::end(c);
    for (const T* it = std::begin(c); it != itEnd; ++it) {
        std::cout << *it << std::endl;
    }
}

int main()
{
    int table[] = {0, 1, 2};
    std::array<double, 3> ary = {1.1, 2.2, 3.3};
    std::vector<int> vec = {5, 10, 15};

    PrintContainer(table);
    PrintContainer(ary);
    PrintContainer(vec);
}

実行結果:

0
1
2
1.1
2.2
3.3
5
10
15

なお、イテレータから constイテレータへは暗黙的に変換できます。これは、int* の変数を const int* の変数に代入できることと同じです。

反対に、constイテレータを、非const のイテレータに変換できません。これは、const int* の変数を int* の変数に代入できないことと同じです。ただし、const_cast(【言語解説】第9章)を使えば変換できるポインタのケースと違い、イテレータの場合は const_cast を使っても変換できる保証はありません。


イテレータのカテゴリ

イテレータはコンテナの種類の違いを気にせず、要素へのアクセスを行えるということでしたが、現実的には、コンテナの機能的な違いに影響を受けてしまうことがあります。

たとえば、配列や std::vector、std::array のようなコンテナは、「n個先の要素まで移動」が容易に行えそうです。実際、+=演算子を使ってイテレータを移動させることは可能です。これは、要素が連続的に並んでいるから、単純なインデックスの加算で移動できるからです。

しかし、リスト構造だとか木構造だとかといった構造であったら、+=演算子の適用は難しいでしょう。意味的には ++演算子を繰り返し実行すれば良いのですが、配列類への適用と違って、効率的とは言えません。

このように、コンテナ側の機能の差によって、イテレータの操作は影響を受けてしまうので、標準ライブラリでは、イテレータをいくつかのカテゴリに分類して、使える機能と使えない機能を定義しています。カテゴリは、以下の5つです。

出力イテレータ

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

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

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

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

出力イテレータの例としては、出力ストリームイテレータ(第17章)や挿入イテレータ(第18章)があります。

入力イテレータ

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

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

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

== と != に関しては、2つのイテレータが同じ場所を指しているとき、等しいとみなされます。なお、比較する2つのイテレータは、同じコンテナの要素を指していなければなりません。そうでない場合の動作は未定義です。

入力イテレータの例としては、入力ストリームイテレータ(第17章)があります。

前方イテレータ

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

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

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

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

このような差異があるので、前方イテレータは、入力イテレータの特徴を引き継いでいるとはいえますが、出力イテレータから引き継いでいるとは言えません。

前方イテレータの例としては、std::forward_list(第19章)、unordered_set や unordered_multiset(第24章)、unordered_map や unordered_multimap (第25章)があります。

双方向イテレータ

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

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

双方向イテレータには、std::list(第20章)、std::set や std::multiset(第22章)、std::map や std::multimap(第23章) のイテレータがあります。

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

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

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

このカテゴリで初めて、< などの大小比較を行う演算子が登場していることに注目してください。「基本操作」の項で述べたように、ループの終了判定で「!=」を使うのは、対象のコンテナを指すイテレータが、ランダムアクセスイテレータでない場合には「<」が使えないからです。

ランダムアクセスイテレータには、std::vector(第6章)、std::array(第7章)、std::deque(第21章)、std::basic_string(第10章)のイテレータがあります。また、配列に対するイテレータ(ポインタ)も、ここに含まれます。

出力イテレータだけは独立した存在ですが、他のカテゴリは、能力を引き継ぐ形で定義されています。入力イテレータがもっとも低機能で、“入力 < 前方 < 双方向 < ランダムアクセス” という関係になっています。

標準ライブラリの関数ではよく、「この関数に渡すイテレータは、前方イテレータでなければならない」といった条件が課せられていることがあります。この場合、前方イテレータの能力を持っていなければならないということなので、前方イテレータ、双方向イテレータやランダムアクセスイテレータ(および隣接イテレータ)であれば要件を満たします。

イテレータの特性

前の項で、イテレータのカテゴリについて取り上げました。これが、実際のプログラムでどのように関係してくるのでしょうか。

まず、各カテゴリに対応した構造体が定義されています。

namespace std {
    struct input_iterator_tag {};
    struct output_iterator_tag {};
    struct forward_iterator_tag : public input_iterator_tag {};
    struct bidirectional_iterator_tag : public forward_iterator_tag {};
    struct random_access_iterator_tag : public bidirectional_iterator_tag {};
}

上から順に、入力イテレータ、出力イテレータ、前方イテレータ、双方向イテレータ、ランダムアクセスイテレータに対応しています。それぞれ、名前の後ろが「iterator_tag」で統一されており、まとめて、イテレータタグと呼ぶことがあります。

後ろの3つに関しては、「: public ~」という記述があります。これは、クラスの能力を引き継がせるための構文です(この構文の詳細は、【言語解説】第35章で説明します)。実際のところ、どのイテレータタグもメンバが無く、空になっているので、何らかの実装を引き継ぐというわけではありません。カテゴリの分類に合わせる形で定義してあるということです。

イテレータタグをうまく活用するには、もう1つ、特性(traits)という仕組みが必要です。イテレータの特性は、std::iterator_traits というクラステンプレートによって、以下のように定義されています。

namespace std {
    template <class Iterator>
    struct iterator_traits {
        using difference_type = typename Iterator::difference_type;
        using value_type = typename Iterator::value_type;
        using pointer = typename Iterator::pointer;
        using reference = typename Iterator::reference;
        using iterator_category = typename Iterator::iterator_category;
    };

    // イテレータが単なるポインタの場合の特殊化
    template <class T>
    struct iterator_traits<T*> {
        using difference_type = ptrdiff_t;
        using value_type = T;
        using pointer = T*;
        using reference = T&;
        using iterator_category = random_access_iterator_tag;
    };
}

std::iterator_traitsクラステンプレートのテンプレート仮引数は、イテレータ(constイテレータも含む)の型名です。たとえば、std::vector<int>::iterator などが入ります。

std::iterator_traits は、5つのメンバ型を定義しており、イテレータの性質が表現されています。

メンバ型名 意味
difference_type イテレータ同士の距離を表す型。
value_type イテレータが指す要素の型。
pointer イテレータが指す要素のポインタ型。
reference イテレータが指す要素の参照型。
iterator_category イテレータのカテゴリを表すイテレータタグ。

先ほどのコード内のコメントに「特殊化」とありますが、これは、テンプレート仮引数に特定の型が当てはめられた場合にだけ、特別な実装を使わせる機能です。詳細は【言語解説】第29章で説明します。ここでは、配列に対するイテレータのように、ポインタで表現される場合にだけ使われる特別な実装があるということだけ理解してください。


さて、イテレータのカテゴリ分け、イテレータタグ、イテレータの特性といったように、いくつかの概念を続けて紹介してきました。最後の問題は、これらがどう使われて、どういう利点を生むのかという点です。

コンテナの要素に対して何らかの処理を行うことを考えたとき、その処理をできるだけ汎用的に使えるようにしたいでしょう。実装が異なるコンテナの要素へのアクセスは、イテレータによって吸収できます。

その鍵となるアイディアは、イテレータを、対象のコンテナの特徴に応じて、カテゴリ分けしてあるということです。さらに、イテレータのカテゴリ分けに沿う形で、イテレータタグが定義されていることにより、イテレータのカテゴリは型によって区別できます。

そして、各コンテナのイテレータ(たとえば、std::vector<int>::iterator)が、どのイテレータタグに対応しているのかは、std::iterator_traits<>::iterator_category が知っています。

これだけの仕組みがそろっていたら、あとは、関数オーバーロードを使って、イテレータタグごとの関数を作ればよいのです。オーバーロードなら、関数名は同じですから、処理を呼び出す側からしてみれば、同じ使い方で結果を得られます。

この一連の考え方を具体化した例が、標準ライブラリにありますので、次の項で取り上げます。この具体化例を理解して、マネをすれば、我々もイテレータの恩恵を最大限に受けられます。

std::advance関数

std::advance関数は、イテレータを任意の要素数分だけ移動させる関数です。使用するには、<iterator> という標準ヘッダをインクルードします。

namespace std {
    template <class InputIt, class Distance>
    void advance(InputIt& it, Distance n);
}

第1テンプレート仮引数の名称が InputIt となっています。もちろん、単なるパラメータ名なので、これ自体に強制力はありませんが、これは、入力イテレータでなければならないことを暗示しています。標準ライブラリでイテレータが使われる場面では、このように名前付けによって、求めているイテレータカテゴリを表現していることがあるので、注意して見るようにしましょう。

第1引数にイテレータを、第2引数に移動させる距離を指定します。距離には負数を指定することもでき、手前側へ移動させることを意味していますが、そのためには、イテレータのカテゴリが、双方向イテレータでなければなりません。そうでない場合に第2引数を負数にすると、未定義の動作になります。

この関数は、やや癖のある仕様になっています。 第1引数は参照になっていて、移動は、渡したイテレータそのものを変更することで行われます。戻り値は何も返しません。

また、移動先に有効な要素があるかどうかについては感知しないため、イテレータが、先頭要素よりも手前側、末尾要素よりも後ろ側に行ってしまわないように注意しなければなりません。

次のプログラムは使用例です。

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

int main()
{
    using IntVector = std::vector<int>;

    const IntVector v = {0, 1, 2, 3, 4};
    IntVector::const_iterator it = std::begin(v);
    std::advance(it, 3);
    std::cout << *it << std::endl;
    std::advance(it, -1);
    std::cout << *it << std::endl;

    const int table[] = {5, 6, 7, 8, 9};
    const int* p = std::begin(table);
    std::advance(p, 3);
    std::cout << *p << std::endl;
    std::advance(p, -1);
    std::cout << *p << std::endl;
}

実行結果:

3
2
8
7

ところで、移動距離として大きい数を指定した場合、ランダムアクセスイテレータであれば「+n」とか「-n」のように一気に移動できますが、他のカテゴリのイテレータではそうはいきません。「+1」や「-1」の移動を n回行うように実装せざるを得ません。だからといって、後者の実装に合わせてしまうと、ランダムアクセスイテレータは無意味に性能を落とすことになります。

ここで、イテレータの特性を活用できます。std::advance関数は、イテレータの特性を使って、渡されたイテレータのカテゴリを判断し、適切な実装を使うように作られています。以下で具体的なコードを示しますが、いつものように、このとおりに実装されているということではなく、このような考え方で実装されているはずだということです。

まず、advance関数自体は、次のように実装できます。

namespace std {
    template <class InputIt, class Distance>
    void advance(InputIt& it, Distance n)
    {
        advance_impl(it, n, iterator_traits<InputIt>::iterator_category());
    }
}

イテレータの特性」の項で見たとおり、std::iterator_traits<>::iterator_category に、イテレータタグの型名があるのでした。、これを利用すれば、advance関数に渡されたイテレータに対応するイテレータタグの型名を得られます。

advance_impl関数は、イテレータタグの種類ごとにオーバーロードします。ランダムアクセスイテレータなら「+n」「-n」のような効率的な実装を使い、双方向イテレータなら「+1」「-1」を n回行う実装を使い、入力イテレータなら「+1」を n回行う実装を使うようにします。

namespace std {

    // ランダムアクセスイテレータの場合
    template <class Iterator, class Distance>
    void advance_impl(Iterator& it, Distance n, random_access_iterator_tag)
    {
        it += n;
    }

    // 双方向イテレータの場合
    template <class Iterator, class Distance>
    void advance_impl(Iterator& it, Distance n, bidirectional_iterator_tag)
    {
        if (n > 0) {
            while (n--) { ++p; }
        }
        else if (n < 0) {
            while (n++) { --p; }
        }
    }

    // 入力イテレータの場合
    template <class Iterator, class Distance>
    void advance_impl(Iterator& it, Distance n, input_iterator_tag)
    {
        assert(n >= 0);
        if (n > 0) {
            while (n--) { ++p; }
        }
    }
}

前方イテレータの場合が抜けているようですが、前方イテレータは入力イテレータを引き継いでいるので、入力イテレータの場合の実装が使われます。

このような仕組みによって、イテレータのカテゴリごとに処理を切り替えられます。そして、この仕組みがあるおかげで、コンテナの特徴の違いは吸収され、配列でもリスト構造でも木構造でも関係なく、同じ使い方ができます。

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

std::next関数std::prev関数は、std::advance関数と同様に、イテレータを移動させる関数です。std::next関数は、イテレータを任意の要素数分だけ後方へ移動させ、std::prev関数は手前側へ移動させます。いずれも、使用するには、<iterator> という標準ヘッダをインクルードします。

namespace std {
    template <class ForwardIt>
    ForwardIt next(ForwardIt it, typename std::iterator_traits<ForwardIt>::difference_type n = 1);

    template <class BidirIt>
    BidirIt prev(BidirIt it, typename std::iterator_traits<BidirIt>::difference_type n = 1);
}

イテレータのカテゴリとしては、std::next関数の方は入力イテレータ、std::prev関数の方は双方向イテレータを要求しています。

いずれの関数でも、第1引数にイテレータを渡し、第2引数に移動させる距離(要素数)を渡します。第2引数にはデフォルト実引数として 1 が設定されています。

移動後のイテレータは戻り値で返却され、第1引数に渡したイテレータは変化しません。この辺りは、std::advance関数とは異なり、自然な使い方になっています。

2つの関数は、次のように、std::advance関数を呼び出す形で実装されます。

namespace std {
    template <class ForwardIt>
    ForwardIt next(ForwardIt it, typename std::iterator_traits<ForwardIt>::difference_type n = 1)
    {
        std::advance(it, n);
        return it;
    }

    template <class BidirIt>
    BidirIt prev(BidirIt it, typename std::iterator_traits<BidirIt>::difference_type n = 1)
    {
        std::advance(it, -n);
        return it;
    }
}

このことから分かるように、std::prev関数の第2引数に指定した距離は、-演算子により正負を反転させて std::advance関数に渡されるので、std::prev関数を使うときには、普通は正の数を渡します

こういったシンプルな実装なので、std::advance関数の特徴もそのままです。たとえば、イテレータのカテゴリに応じた最適な実装が使用されます。一方で、イテレータが、先頭要素よりも手前側、末尾要素よりも後ろ側に行ってしまった場合の危険な振る舞いも変わっていないので、注意が必要です。

次のプログラムは使用例です。

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

int main()
{
    using IntVector = std::vector<int>;

    const IntVector v = {0, 1, 2, 3, 4};
    IntVector::const_iterator it = std::begin(v);

    it = std::next(it, 2);
    std::cout << *it << std::endl;
    it = std::next(it);
    std::cout << *it << std::endl;
    it = std::prev(it, 2);
    std::cout << *it << std::endl;
    it = std::prev(it);
    std::cout << *it << std::endl;
}

実行結果:

2
3
1
0

std::distance関数

std::distance関数は、2つのイテレータがどれだけ離れた位置を指しているかを知らべる関数です。使用するには、<iterator> という標準ヘッダをインクルードします。

namespace std {
    template <class InputIt>
    typename std::iterator_traits<InputIt>::difference_type distance(InputIt first, InputIt last);
}

引数はともにイテレータで、イテレータのカテゴリとしては、入力イテレータを要求しています。両者の距離(要素数)が戻り値で返却されます。

距離を調べる際、イテレータのカテゴリがランダムアクセスイテレータの場合には、単に「last - first」に相当する計算を行います。そのため、first の方が後ろ側の要素を指すようなイテレータを指定した場合は、負の数が返されます。

ランダムアクセスイテレータ以外のカテゴリのイテレータの場合には、first から順にインクリメントを繰り返して、last に到達するまでカウントを行います。そのため、こちらは必ず正の数で返されます。

このような実装であるため、ランダムアクセスイテレータでない場合は、first が指す位置から last が指す位置に到達可能でなければならず、ランダムアクセスイテレータの場合は、first が指す位置から last が指す位置、あるいは last が指す位置から first が指す位置に到達可能でなければなりません。
これらの要件を満たしていないイテレータを渡した場合の動作は未定義です。

次のプログラムは使用例です。

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

int main()
{
    using IntVector = std::vector<int>;

    const IntVector v = {0, 1, 2, 3, 4};
    IntVector::const_iterator it1 = std::begin(v);
    IntVector::const_iterator it2 = std::next(it1, 3);

    std::cout << std::distance(it1, it2) << std::endl;
}

実行結果:

3

コンテナアクセスのための補助関数

標準ヘッダ <iterator> には、イテレータの仕組みを使って実装された補助関数がいくつかあります。これらの関数は、コンテナ(配列や std::initializer_list を含む)に対して使用できます。


練習問題

問題① std::end関数が、末尾要素の「1つ後ろ」を指すイテレータを返すのはなぜでしょうか?

問題② std::distance関数はどのように実装されているか、想像して自作してみてください。


解答ページはこちら

参考リンク


更新履歴

’2018/1/5 コンパイラの対応状況について、対応している場合は明記しない方針にした。

’2017/12/21 新規作成。



前の章へ (第8章 initializer_list)

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

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポストフォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る