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 を使った方が簡単でしょう。

VisualC++、Xcode は、いずれも対応しています。

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

VisualC++、Xcode は、いずれも対応しています。

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

make_reverse_iterator関数は、VisualC++ 2013 では対応しておらず、2015/2017 は対応しています。 Xcode では使用できます

挿入イテレータ

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

例えば、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章)。


練習問題

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

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

問題B 問題Aを改造して、文字を大文字に変換しながらコピーするようにして下さい。


解答ページはこちら

参考リンク

更新履歴

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

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

'2016/12/10 新規作成。



前の章へ

次の章へ

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

Programming Place Plus のトップページへ