C++編【標準ライブラリ】 第26章 逆イテレータと挿入イテレータ

先頭へ戻る

この章の概要

この章の概要です。


イテレータアダプタ

イテレータアダプタ(反復子アダプタ)と呼ばれる機能を使うと、イテレータの挙動を変更できます。

イテレータアダプタには、逆イテレータ(逆反復子)挿入イテレータ(挿入反復子、挿入子)ストリームイテレータ(ストリーム反復子)があります。

本章では、逆イテレータ挿入イテレータについて解説します。ストリームイテレータについては、第31章で解説します。

C++11 にはさらに、ムーブイテレータ(ムーブ反復子)があります。

なお、イテレータアダプタを使用するには、<iterator> という標準ヘッダのインクルードが必要です

逆イテレータ

逆イテレータ(逆反復子)は、イテレータを後方や前方に移動する操作を書き換えて、逆方向に移動させるようにするイテレータアダプタです。

STLコンテナから通常のイテレータを取得する際に、begin や end というメンバ関数を使ったように、逆イテレータを取得するには、rbeginメンバ関数rendメンバ関数を使います。これらの関数が返す型は、各STLコンテナで定義される reverse_iterator型や、const_reverse_iterator型です(例えば、std::vector<int>::reverse_iterator)。

次のサンプルプログラムは、std::list を、逆イテレータを使って逆順にたどる例です。

#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_reverse_iterator itEnd = lst.rend();
    for (IntList::const_reverse_iterator it = lst.rbegin(); it != itEnd; ++it) {
        std::cout << *it << std::endl;
    }
}

実行結果

4
3
2
1
0

逆イテレータにとっての「先頭」は、対象のコンテナの末尾要素の1つ後ろであり、「末尾」は、対象のコンテナの先頭要素です。この仕様は、C++ の配列は、-1番目の位置を参照することを未定義の動作としていることに起因しています。

逆イテレータに対する ++演算子や +=演算子は、対象のコンテナの先頭の方へ移動し、--演算子や -=演算子は、対象のコンテナの末尾の方へ移動します。これは、std::advance関数(第14章)でも同様です。

イテレータアダプタは、STLアルゴリズムと組み合わせられます。例えば、上記のサンプルプログラムで、標準出力へ出力している部分を、std::for_each関数(第18章)を使って書き換えると、次のようになります。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

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

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

    IntList lst(table, table + 5);

    std::for_each(lst.rbegin(), lst.rend(), Println);
}

実行結果

4
3
2
1
0

イテレータを逆イテレータに変換する

reverse_iteartor や const_reverse_iterator のコンストラクタは、iterator や const_iterator を受け取ることができるようになっており、同じ要素を指す逆イテレータを生成できます。

C++14 では、make_reverse_iterator関数というヘルパ関数が追加されています。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

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

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

    IntVector lst(table, table + 5);

    IntVector::const_iterator it = lst.begin();
    IntVector::const_iterator itEnd = lst.end();

    IntVector::const_reverse_iterator rit(itEnd);
    IntVector::const_reverse_iterator ritEnd(it);

    std::for_each(rit, ritEnd, Println);
}

実行結果

4
3
2
1
0

逆イテレータをイテレータに変換する

逆イテレータをイテレータに変換するには、逆イテレータが持つ baseメンバ関数を呼び出します。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

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

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

    IntVector lst(table, table + 5);

    IntVector::const_reverse_iterator rit = lst.rbegin();
    IntVector::const_reverse_iterator ritEnd = lst.rend();

    IntVector::const_iterator it = ritEnd.base();
    IntVector::const_iterator itEnd = rit.base();

    std::for_each(it, itEnd, Println);
}

実行結果

0
1
2
3
4

C++11 (非メンバ関数の rbegin、rend)

C++11 には、非メンバ関数版の rbegin関数rend関数が追加されています。これらの関数は、<iterator> という名前の標準ヘッダに含まれます。なお、C++11 の時点では、非メンバ関数版の crbegin関数、crend関数はなく、C++14 で追加されています

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

#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>
#include <numeric>

int main()
{
    std::list<int> lst(5);
    std::iota(std::begin(lst), std::end(lst), 0);

    std::for_each(std::rbegin(lst), std::rend(lst), [](int elem){std::cout << elem << std::endl; });
}

実行結果

4
3
2
1
0

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

#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>
#include <numeric>

int main()
{
    int table[5];
    std::iota(std::begin(table), std::end(table), 0);

    std::for_each(std::rbegin(table), std::rend(table), [](int elem){std::cout << elem << std::endl; });
}

実行結果

4
3
2
1
0

この場合、std::rbegin関数、std::rend関数が返す型は、std::reverse_iterator<>型です。テンプレート実引数は、対象の配列の要素の型になります。ただし、変数で受け取るのなら、auto を使った方が簡単でしょう。

C++14 (非メンバ関数の crbegin、crend)

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

#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>
#include <numeric>

int main()
{
    int table[5];
    std::iota(std::begin(table), std::end(table), 0);

    std::for_each(std::crbegin(table), std::crend(table), [](int elem){std::cout << elem << std::endl; });
}

実行結果

4
3
2
1
0

C++14 (make_reverse_iterator関数)

C++14 では、イテレータから逆イテレータを生成するヘルパ関数として、make_reverse_iterator関数が追加されています。この関数は、引数でイテレータを受け取り、戻り値で逆イテレータを返します。

#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>
#include <numeric>

int main()
{
    std::list<int> lst(5);
    std::iota(std::begin(lst), std::end(lst), 0);

    std::for_each(
        std::make_reverse_iterator(std::cend(lst)),
        std::make_reverse_iterator(std::cbegin(lst)),
        [](int elem){std::cout << elem << std::endl; }
    );
}

実行結果

4
3
2
1
0


挿入イテレータ

挿入イテレータ(挿入反復子、挿入子)は、イテレータを通じて行う代入操作を、 値の上書きではなく、挿入に変換するイテレータアダプタです。

例えば、copy関数(第20章)を使うとき、範囲の指定に、通常のイテレータを使う場合には、コピー先に十分な領域があることを保証しなければなりません。これは、各要素のコピー操作が、値の上書きによって実現されているため、そもそもコピー先に領域が無ければ成り立たないためです。

挿入イテレータを使うと、各要素のコピー操作が、挿入によって実現されるようになるため、コピー先に自動的に要素が作られていきます。この実例は、「末尾挿入イテレータ」の項で取り上げます。

挿入イテレータには、値を挿入する位置に応じて、以下の3つの種類があります。

末尾挿入イテレータ

末尾挿入イテレータ(末尾挿入反復子)は、対象のコンテナの末尾に要素を挿入します。以下のサンプルプログラムは、copy関数を使って、挿入を行う例です。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<int> v;
    v.push_back(0);
    v.push_back(1);
    v.push_back(2);

    std::vector<int> v2;
    std::copy(v.begin(), v.end(), std::back_inserter(v2));

    std::for_each(v2.begin(), v2.end(), Println);
}

実行結果

0
1
2

std::back_inserter関数は、末尾挿入イテレータを生成する関数です。引数に指定したイテレータが指すコンテナに対応した末尾挿入イテレータを生成して返します。末尾挿入イテレータは、次のようにも生成できます。

std::back_insert_iterator<std::vector<int> > it(v2);

std::back_insert_iterator は、末尾挿入イテレータを実現するクラステンプレートで、std::back_inserter関数の戻り値も、この型です。テンプレート仮引数に指定する型は、対象のコンテナの型なので、まともに書くと上記のように長くなってしまい面倒です。普通は、std::back_inserter関数を使った方が簡単でしょう。

末尾挿入イテレータを通じて行う代入処理は、対象コンテナの push_backメンバ関数の呼び出しに変換されます。そのため、push_backメンバ関数を持たない相手には使用できません。

先頭挿入イテレータ

先頭挿入イテレータ(先頭挿入反復子)は、対象のコンテナの先頭に要素を挿入します。

先頭に挿入するので、以下のように copy関数に使用した場合、結果は逆順になります。

#include <iostream>
#include <deque>
#include <iterator>
#include <algorithm>

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::deque<int> d;
    d.push_back(0);
    d.push_back(1);
    d.push_back(2);

    std::deque<int> d2;
    std::copy(d.begin(), d.end(), std::front_inserter(d2));

    std::for_each(d2.begin(), d2.end(), Println);
}

実行結果

2
1
0

std::front_inserter関数は、先頭挿入イテレータを生成する関数です。引数に指定したイテレータが指すコンテナに対応した先頭挿入イテレータを生成して返します。先頭挿入イテレータは、次のようにも生成できます。

std::front_insert_iterator<std::deque<int> > it(d2);

std::front_insert_iterator は、先頭挿入イテレータを実現するクラステンプレートで、std::front_inserter関数の戻り値も、この型です。

先頭挿入イテレータを通じて行う代入処理は、対象コンテナの push_frontメンバ関数の呼び出しに変換されます。そのため、push_frontメンバ関数を持たない相手には使用できません。

汎用挿入イテレータ

汎用挿入イテレータ(汎用挿入反復子)は、対象のコンテナの指定した位置に要素を挿入します。そのため、末尾挿入イテレータや先頭挿入イテレータと違い、生成時に位置の指定も必要になります。

#include <iostream>
#include <list>
#include <vector>
#include <iterator>
#include <algorithm>

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::list<int> lst;
    lst.push_back(0);
    lst.push_back(1);
    lst.push_back(2);

    std::vector<int> v;
    v.push_back(9);
    v.push_back(9);
    v.push_back(9);

    std::copy(lst.begin(), lst.end(), std::inserter(v, v.begin() + 1));

    std::for_each(v.begin(), v.end(), Println);
}

実行結果

9
0
1
2
9
9

std::inserter関数は、汎用挿入イテレータを生成する関数です。引数に指定したイテレータが指すコンテナの、指定位置に対応した汎用挿入イテレータを生成して返します。汎用挿入イテレータは、次のようにも生成できます。

std::insert_iterator<std::vector<int> > it(v, v.begin());

std::insert_iterator は、汎用挿入イテレータを実現するクラステンプレートで、 std::inserter関数の戻り値も、この型です。

汎用挿入イテレータを通じて行う代入処理は、対象コンテナの insertメンバ関数の呼び出しに変換されます。そのため、insertメンバ関数を持たない相手には使用できません(すべての STLコンテナは insertメンバ関数を持っています。第4章)。


練習問題

問題① 逆イテレータを使って、通常と逆順のソートが行えることを確認してください。

問題② std::string に対して末尾挿入イテレータを使って、文字を末尾へコピーするプログラムを作成してください。

問題③ 問題②を改造して、文字を大文字に変換しながらコピーするようにしてください。


解答ページはこちら

参考リンク



更新履歴

'2018/4/5 VisualStudio 2013 の対応終了。

'2018/4/2 「VisualC++」という表現を「VisualStudio」に統一。

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

'2017/7/30 clang 3.7 (Xcode 7.3) を、Xcode 8.3.3 に置き換え。

'2017/3/25 VisualC++ 2017 に対応。

'2016/12/10 新規作成。



前の章へ (第25章 STL の関数オブジェクト)

次の章へ (第27章 標準入出力ストリーム)

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

Programming Place Plus のトップページへ


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