C++ イテレータ入門

ここでは C++ の STL などで使われているイテレータというものについて簡単に説明します

その前に

新人さんは仕事でのコードで独自のコンテナやイテレータを書いてはいけません
それぞれのプロジェクトでは必ず使ってよいとされているコンテナなどは予め決まっています
既にあるものを使うようにしてください
既にあるものでは足りないからどうしても新しいものを書きたい。というときはまず先輩や上長に相談するようにしてください

特にウェブで見つけてきたようなものを勝手に仕事のコードに紛れ込ませるようなことは絶対にやってはいけません

基礎知識

イテレータとは

イテレータ(iterator)とはコンテナの要素へのアクセスを抽象化したものです
STL などではポインタを理想として実装されています

ポインタの７つの特徴

値を読み出せる

value = *p;

値を書き込める

*p = value;

直後の要素に移動できる

++p;

直前の要素に移動できる

--p;

任意の要素に移動できる

p += n;
p -= n;

距離を得られる・大小を比較できる

d = p2 - p1;
if( p1 < p2 ){
}

等しいかどうかを確認できる

if( p1 == p2 ){
	...
}
if( p1 != p2 ){
	...
}

イテレータの５つの特徴

input_iterator_tag

このイテレータは「値を読み出せる」「直後の要素に移動できる」「等しいかどうかを確認できる」という特徴を持ちます

value = *p;
++p;

例えば std::copy の入力引数はこの特徴を持つイテレータであることが期待されます

output_iterator_tag

このイテレータは「値を書き込める」「直後の要素に移動できる」「等しいかどうかを確認できる」という特徴を持ちます

*p = value;
++p;

例えば std::copy の出力引数はこの特徴を持つイテレータであることが期待されます

forward_iterator_tag

このイテレータは「値を読み出せる」「値を書き込める」「直後の要素に移動できる」「等しいかどうかを確認できる」という特徴を持ちます

value = *p;
*p = value;
++p;

例えば単方向リストのイテレータはこの特徴を持つイテレータでしょう

bidirectional_iterator_tag

このイテレータは「値を読み出せる」「値を書き込める」「直後の要素に移動できる」「直前の要素に移動できる」「等しいかどうかを確認できる」という特徴を持ちます

value = *p;
*p = value;
++p;
--p;

例えば std::list や std::map のイテレータはこの特徴を持ちます

random_access_iterator_tag

このイテレータはポインタの持つ７つの特徴を全て備えています
このイテレータは「値を読み出せる」「値を書き込める」「直後の要素に移動できる」「直前の要素に移動できる」「任意の要素に移動できる」「距離を得られる・大小を比較できる」「等しいかどうかを確認できる」という特徴を持ちます

value = *p;
*p = value;
++p;
--p;
p += n;
p -= n;

例えば std::string や std::vector のイテレータはこの特徴を持ちます

コンテナのイテレータ

iterator

コンテナの先頭から順に辿れる読み書き可能なイテレータです

const_iterator

コンテナの先頭から順に辿れる読み込み専用のイテレータです

reverse_iterator

コンテナの末尾から逆順に辿れる読み書き可能なイテレータです

const_reverse_iterator

コンテナの末尾から逆順に辿れる読み込み専用のイテレータです

その他のイテレータ

back_insert_iterator

コンテナの末尾に push_back するためだけにあるイテレータです
値の書き込みだけが可能です
移動はしません

例：コンテナ s の全要素をコンテナ d に push_back します

std::copy( s.begin(), s.end(), std::back_inserter( d ));

front_insert_iterator

コンテナの先頭に push_front するためだけにあるイテレータです
値の書き込みだけが可能です
移動はしません

例：コンテナ s の全要素をコンテナ d に push_front します

std::copy( s.begin(), s.end(), std::front_inserter( d ));

上の例では s の全要素を d の先頭に insert するので s の内容の逆順がコピーされます
s の内容をそのままコピーしたいという場合には reverse_const_iterator を渡します

std::copy( s.rbegin(), s.rend(), std::front_inserter( d ));

insert_iterator

コンテナの特定の位置に insert するためだけにあるイテレータです
値の書き込みだけが可能です
移動はしません

例：コンテナ s の全要素をコンテナ d の p の位置に insert します

std::copy( s.begin(), s.end(), std::inserter( d, p ));

上の例では s の全要素を指定位置に insert するので s の内容の逆順がコピーされます
s の内容をそのままコピーしたいという場合には reverse_const_iterator を渡します

std::copy( s.rbegin(), s.rend(), std::inserter( d, p ));

イテレータを使ってみる

distance を実装してみる

二つのイテレータの差分を得る std::distance と同じ機能を実装してみましょう

input_iterator_tag の場合

このイテレータは「値を読み出せる」「直後の要素に移動できる」「等しいかどうかを確認できる」という特徴を持つのでした
「距離を得られる」という特徴は持ちませんから直接距離を得ることはできません
要素を順番に辿ってその間の要素数を数えることで距離を得ます

template<typename input_iterator_type_, typename difference_type_> inline void	distance( input_iterator_type_	first_, input_iterator_type_ last_, difference_type_&	result, input_iterator_tag ){
	while( first_ != last_ ){
		++result;
		++first_;
	}
}

forward_iterator_tag の場合

input_iterator_tag の場合と同じです

template<typename forward_iterator_type_, typename difference_type_> inline void	distance( forward_iterator_type_	first_, forward_iterator_type_	last_, difference_type_&	result, forward_iterator_tag ){
	while( first_ != last_ ){
		++result;
		++first_;
	}
}

bidirectional_iterator_tag の場合

input_iterator_tag の場合と同じです

template<typename bidirectional_iterator_type_,	typename difference_type_> inline void	distance( bidirectional_iterator_type_	first_, bidirectional_iterator_type_	last_, difference_type_&	result, bidirectional_iterator_tag ){
	while( first_ != last_ ){
		++result;
		++first_;
	}
}

random_access_iterator_tag の場合

このイテレータは「距離を得られる」という特徴を持つので直接距離を得られます

template<typename random_access_iterator_type_, typename difference_type_> inline void	distance( random_access_iterator_type_	first_, random_access_iterator_type_	last_, difference_type_&	result, random_access_iterator_tag ){
	result = last_ - first_;
}

呼び分ける

それぞれの場合の実装はできました
しかし実際に使うときにいちいちイテレータのタイプを指定したりはしませんから、指定したイテレータからその特徴を得てそれぞれのための実装を呼び分ける何らかの仕組みが必要になります

テンプレートで指定された型による場合分けをしたい場合にはそこを別のテンプレートに追い出すのでした

ここでは iterator_traits というテンプレートがあることにして次のように書いてみます

template<typename iterator_type_> inline typename iterator_traits<iterator_type_>::difference_type	distance( iterator_type_	first_, iterator_type_	last_ ){
	typename iterator_traits<iterator_type_>::difference_type	result = typename iterator_traits<iterator_type_>::difference_type();
	distance( first_, last_, result, iterator_traits<iterator_type_>::iterator_category());
	return	result;
}

iterator_traits は結果のための型 difference_type とイテレータのタイプのための型 iterator_category を持つこととします
iterator_category() というのは関数を呼び出しているのではなく iterator_category 型のインスタンスをデフォルト初期化しているという指定です

advance を実装してみる

イテレータの指す位置を指定した要素分移動させる std::advance と同じ機能を実装してみましょう

input_iterator_tag の場合

このイテレータは「値を読み出せる」「直後の要素に移動できる」「等しいかどうかを確認できる」という特徴を持つのでした
「任意の要素に移動できる」という特徴は持ちませんから移動することはできません
要素を順番に辿って指定の要素数分だけ移動します

template<typename input_iterator_type_, typename difference_type_> inline void	advance( input_iterator_type_&	p, difference_type_	offset_, input_iterator_tag ){
	while( offset_ > 0 ){
		++p;
		--offset_;
	}
}

forward_iterator_tag の場合

input_iterator_tag の場合と同じです

template<typename forward_iterator_type_, typename difference_type_> inline void	advance( forward_iterator_type_&	p, difference_type_	offset_, forward_iterator_tag ){
	while( offset_ > 0 ){
		++p;
		--offset_;
	}
}

bidirectional_iterator_tag の場合

順方向への移動は input_iterator_tag の場合と同じです
このイテレータは逆順にも移動することができるので負の距離を指定されたときも移動することができます

template<typename bidirectional_iterator_type_, typename difference_type_> inline void	advance( bidirectional_iterator_type_&	p, difference_type_	offset_, bidirectional_iterator_tag ){
	if( offset_ > 0 ){
		do{
			++p;
		}while( --offset_ > 0 );
	}
	else if( offset_ < 0 ){
		do{
			--p;
		}while( ++offset_ < 0 );
	}
}

input_iterator_tag の場合と forward_iterator_tag の場合には負の距離を指定しても逆順には移動できません
負の距離を指定されたときのために assert があってもいいかもしれません

random_access_iterator_tag の場合

このイテレータは「任意の要素に移動できる」という特徴を持つので直接移動できます

template<typename random_access_iterator_type_,	typename difference_type_> inline void	advance( random_access_iterator_type_&	p, difference_type_	offset_, random_access_iterator_tag ){
	p += offset_;
}

呼び分ける

それぞれの場合の実装はできました
しかしこちらも実際に使うときにいちいちイテレータのタイプを指定したりはしませんから、やはり指定したイテレータからその特徴を得てそれぞれのための実装を呼び分ける何らかの仕組みが必要になります

テンプレートで指定された型による場合分けをしたい場合にはそこを別のテンプレートに追い出すのでした

ここでも iterator_traits というテンプレートがあることにして次のように書いてみます

template<typename iterator_type_, typename difference_type_> inline void	advance( iterator_type_&	p, difference_type_	offset_ ){
	advance( p, offset_, iterator_traits<iterator_type_>::iterator_category());
}

こちらも iterator_traits は結果のための型 difference_type とイテレータのタイプのための型 iterator_category を持ちます
iterator_category() というのは関数を呼び出しているのではなく iterator_category 型のインスタンスをデフォルト初期化しているという指定です

iterator_traits

上記の例ではイテレータの特徴を得る部分を iterator_traits というテンプレートに分離しました
これをどのように実装すべきでしょうか

次のように個別のイテレータに対して特殊化するというような実装でも構わないのですが、そうすると既知のイテレータすべてに特殊化する必要がありますし、また未知のイテレータが出てきたときにはそれ用の対応を追加する必要が出てきますし、ちょっと現実的ではありません

template<typename iterator_type_> struct iterator_traits {
	typedef input_iterator_tag iterator_category;
	typedef ptrdiff_t difference_type;
	...
};
template<> struct iterator_traits<イテレータの型> {
	typedef forward_iterator_tag iterator_category;
	typedef ptrdiff_t difference_type;
	...
};

そこで次のようにイテレータ自身の持つ情報を使うようにします
こうすると簡単ですね

template<typename iterator_type_> struct iterator_traits {
	typedef typename iterator_type_::iterator_category iterator_category;
	typedef typename iterator_type_::difference_type difference_type;
	...
};

自分でイテレータを実装する

イテレータは必ず何らかのコンテナの子クラスになりますから、その実装もそれぞれのコンテナの実装に依存するのですが
だいたいは下記のような感じになります

コンテナ

template<typename value_type_,...> struct sample_container {
	// 差分の型
	typedef ptrdiff_t	difference_type;
	// サイズの型
	typedef size_t	size_type;
	// 要素の型
	typedef value_type_	value_type;
	// 要素を指すポインタ
	typedef value_type*	pointer;
	// 要素を指すconstなポインタ
	typedef const value_type*	const_pointer;
	// 要素の非const参照
	typedef value_type&	reference;
	// 要素のconst参照
	typedef const value_type&	const_reference;
	// constなイテレータ
	struct const_iterator;
	// const_iteratorは privateメンバにアクセスしてもよい
	friend struct const_iterator;
	// constな逆順イテレータ
	typedef reverse_iterator<const_iterator>	const_reverse_iterator;
	// イテレータ
	struct iterator;
	// iteratorは privateメンバにアクセスしてもよい
	friend struct iterator;
	// 逆順イテレータ
	typedef reverse_iterator<iterator>	reverse_iterator;
	.
	.
	.

イテレータの定義

	.
	.
	.
	struct const_iterator : public iterator<random_access_iterator_tag,value_type,difference_type,const_pointer,const_reference> {
		// 要素を指すポインタ
		const_pointer	m_base;
		// デフォルトコンストラクタ。どこも指していない		
		const_iterator():
		m_base()
		{
		}
		// 要素を指定してのコンストラクタ。暗黙の変換に使われてしまうことに注意
		const_iterator( const_pointer	_base ):
		m_base(_base)
		{
		}
		// コピーコンストラクタ
		const_iterator( const const_iterator&	rhs ):
		m_base(rhs.m_base)
		{
		}
		// コピー代入演算子
		const_iterator&	operator=( const const_iterator&	rhs ){
			if( this != &rhs ){
				m_base = rhs.m_base;
			}
			return	*this;
		}
		// 要素のconst参照を返すこと
		const_reference operator*() const {
			return	*m_base;
		}
		// 要素を指すポインタを返すこと
		const_pointer	operator->() const {
			return	&**this;
		}
		// 次の要素へ。前置
		const_iterator&	operator++(){
			++m_base;
			return	*this;
		}
		// 次の要素へ。後置
		const_iterator	operator++(int){
			const_iterator	this_ = *this;
			++*this;
			return	this_;
		}
		// 直前の要素へ。前置
		const_iterator&	operator--(){
			--m_base;
			return	*this;
		}
		// 直前の要素へ。後置
		const_iterator	operator--(int){
			const_iterator	this_ = *this;
			--*this;
			return	this_;
		}
		// 任意の要素へ
		const_iterator&	operator+=( difference_type	n ){
			m_base += n;
			return	*this;
		}
		// 任意の要素へ
		const_iterator	operator+( difference_type	n ) const {
			const_iterator	this_ = *this;
			return	( this_ += n );
		}
		// 任意の要素へ
		const_iterator&	operator-=( difference_type	n ){
			return	( *this += -n );
		}
		// 任意の要素へ
		const_iterator	operator-( difference_type	n ) const {
			const_iterator	this_ = *this;
			return	( this_ -= n );
		}
		// 差分
		difference_type	operator-( const const_iterator&	rhs ) const {
			return	static_cast<difference_type>( m_base - rhs.m_base );
		}
		// 任意の要素を得る
		const_reference	operator[]( difference_type	n ) const {
			return	*( *this + n );
		}
		// 任意の要素へ
		friend const_iterator	operator+( difference_type	n, const const_iterator&	rhs ){
			return	( rhs + n );
		}
		// 同じ要素か？
		bool	operator==( const const_iterator&	rhs ) const {
			return	( m_base == rhs.m_base );
		}
		// 異なる要素か？
		bool	operator!=( const const_iterator&	rhs ) const {
			return	!( *this == rhs );
		}
		// 自分の方が前の要素か？
		bool	operator<( const const_iterator&	rhs ) const {
			return	( m_base < rhs.m_base );
		}
		// 自分の方が後の要素か？
		bool	operator>( const const_iterator&	rhs ) const {
			return	( rhs < *this );
		}
		// 自分と同じ要素か、あるいは自分より前の要素か
		bool	operator<=( const const_iterator&	rhs ) const {
			return	!( rhs < *this );
		}
		// 自分と同じ要素か、あるいは自分より後の要素か
		bool operator>=( const const_iterator& rhs ) const {
			return	!( *this < rhs );
		}
	};
	struct iterator : public const_iterator {
		typedef value_type*	pointer;
		typedef value_type& reference;
		
		iterator():
		const_iterator()
		{
		}
		iterator( pointer _base ):
		const_iterator(_base)
		{
		}
		iterator( const iterator&	rhs ):
		const_iterator(rhs)
		{
		}
		iterator&	operator=( const iterator&	rhs ){
			const_iterator::operator=( rhs );
			return	*this;
		}
		reference	operator*(){
			return	const_cast<reference>(const_iterator::operator*());
		}
		pointer	operator->(){
			return	&**this;
		}
		iterator&	operator++(){
			const_iterator::operator++();
			return	*this;
		}
		iterator	operator++(int){
			iterator	this_ = *this;
			++*this;
			return	this_;
		}
		iterator&	operator--(){
			const_iterator::operator--();
			return	*this;
		}
		iterator	operator--(int){
			iterator	this_ = *this;
			--*this;
			return	this_;
		}
		iterator&	operator+=( difference_type	n ){
			const_iterator::operator+=( n );
			return	*this;
		}
		iterator	operator+( difference_type	n ) const {
			iterator	this_ = *this;
			return	( this_ += n );
		}
		iterator&	operator-=( difference_type	n ){
			return	( *this += -n );
		}
		iterator	operator-( difference_type	n ) const {
			iterator	this_ = *this;
			return	( this_ -= n );
		}
		difference_type	operator-( const const_iterator&	rhs ) const {
			return	static_cast<const_iterator>(*this) - rhs;
		}
		reference	operator[]( difference_type	n ){
			return	*( *this + n );
		}
		friend iterator	operator+( difference_type	n, const iterator&	rhs ){
			return	( rhs + n );
		}
	};
	.
	.
	.

イテレータを返すメソッド

	.
	.
	.
	// 最初の要素を指すconstなイテレータを得る
	const_iterator	begin() const {
		return	const_iterator( m_data );
	}
	// 最初の要素を指すイテレータを得る
	iterator	begin(){
		return	iterator( m_data );
	}
	// コンテナ内を指さないconstなイテレータを得る
	const_iterator	end() const {
		return	const_iterator( m_data + m_size );
	}
	// コンテナ内を指さないイテレータを得る
	iterator	end(){
		return	iterator( m_data + m_size );
	}
	// 最後の要素を指すconstな逆順イテレータを得る
	const_reverse_iterator	rbegin() const {
		return	const_reverse_iterator( end());
	}
	// 最後の要素を指す逆順イテレータを得る
	reverse_iterator	rbegin(){
		return	reverse_iterator( end());
	}
	// コンテナ内を指さないconstな逆順イテレータを得る
	const_reverse_iterator	rend() const {
		return	const_reverse_iterator( begin());
	}
	// コンテナ内を指さない逆順イテレータを得る
	reverse_iterator	rend(){
		return	reverse_iterator( begin());
	}
	.
	.
	.