<iterator>

iterator、日本語で反復子。 訳しても意味がよく分からないが、 要はポインタに代わって要素にアクセスするためのクラス(構造体)のことである。
ポインタが*で要素を参照出来るように、イテレータも*で参照出来る。
ポインタが++されると次の要素を指すように、イテレータも++されると次の要素を指す。
リストの場合*はポインタに++しても次の要素を指してくれないが、 イテレータならちゃんと次の要素を指してくれます。 さすがにリストでランダムアクセスは出来ませんが。

* listのイテレータはlistクラス内にBidirectional_iteratorから派生されて定義されています。
vectorはポインタをイテレータとしています。必ずそうなっているとは限りませんが。


基本的なイテレータ

型名

structo iteratorには各種型名が定義されています。

template <class Category, class T, class Distance = ptrdiff_t,
	  class Pointer = T*, class Reference = T&>
struct iterator {
	// イテレータの種類を表すタグ
	typedef Category	iterator_category;
	// イテレータが指す要素の型
	typedef T		value_type;
	// イテレータの差を表す型
	typedef Distance	difference_type;
	// イテレータが指す要素のポインタ型
	typedef Pointer		pointer;
	// イテレータが指す要素の参照型
	typedef Reference	reference;
};

例えばinput_iteratorは
input_iterator : public iterator<input_iterator_tag, T, Distance, T*, T&>
output_iteratorは
output_iterator : public iterator<output_iterator_tag, void, void, void, void>
といった具合。*1 イテレータを作成する場合にはstruct iteratorから派生するといいでしょう。

*1 必ずしもstruct iteratorから派生しているとは限りません。

struct iterator_traits

イテレータの特性。扱う型などをiterator_traitsに持ちます。 ポインタなどからそのような情報を得る必要がある場合にも、 struct iterator_traits<T*>;などを使用することで イテレータの特性を取得することが出来ます。

template<class Iterator>
struct iterator_triats {
	// イテレータの種類を表すカテゴリ
	typedef typename Iterator::iterator_category iterator_category;
	// イテレータが扱う要素の型
	typedef typename Iterator::value_type value_type;
	// イテレータ同士の差を表す型
	typedef typename Iterator::difference_type difference_type;
	// イテレータが扱う要素のポインタ型
	typedef typename Iterator::pointer pointer;
	// イテレータが扱う要素の参照型
	typedef typename Iterator::reference reference;
}

struct iterator_tag

イテレータの種類を判別するためのオブジェクト。 iterator_traits::iterator_categoryは通常iterator_tag型です。

  • input_iterator_tag;
    • forward_iterator_tag; // input_iterator_tagからの派生
      • bidirectional_iterator_tag; // 同様にforwardから
        • random_access_iterator_tag; // bidirectionalから
  • output_iterator_tag;

イテレータのカテゴリ

イテレータはその機能に応じて五つのカテゴリに分類されます。 これは共通アルゴリズムのテンプレート引数名で使われているイテレータの分類と同じものです。

InputIterator

入力のみが可能なイテレータ。 イテレータの要素の参照および++による前進のみが可能です。
一度過ぎた要素を2度走査することはできません。 入力ストリームイテレータなどはこれに分類されます。

メンバ

メンバ関数と関数のみ書きます。

// これでいいのかな?
struct input_iterator {
	input_iterator(const input_iterator& x);
	input_iterator& operator =(const input_iterator& x);
	// 参照はできますがその値への書き込みは無効です。
	reference operator *() const;
	pointer operator ->() const;
	input_iterator& operator ++();
	input_iterator operator ++(int);
};
bool operator ==(const input_iterator& x, const input_iterator& y);
bool operator !=(const input_iterator& x, const input_iterator& y);

OutputIterator

出力のみが可能なイテレータ。 イテレータの要素への代入および++による前進のみが可能です。
一度過ぎた要素を2度走査することはできません。 出力ストリームイテレータなどはこれに分類されます。

メンバ

メンバ関数と関数のみ書きます。

// これでいいのかな?
struct output_iterator {
	output_iterator(const output_iterator& x);
	// イテレータではなく、要素を代入出来ます。
	output_iterator& operator =(const T& value_type);
	// 参照では値を返しません。実際に何を返すかは不定だと思います。
	void operator *() const;	// とりあえず返り値voidと書いておく
	// ->は使えたとしても無効
//	pointer operator ->() const;
	output_iterator& operator ++();
	output_iterator& operator ++(int);
};
bool operator ==(const output_iterator& x, const output_iterator& y);
bool operator !=(const output_iterator& x, const output_iterator& y);

ForwardIterator

前進および入出力が可能なイテレータ。 イテレータの要素の参照、代入および++による前進のみが可能です。
また、2度以上走査することも可能です。
単方向リストがあればおそらくこれに分類されるでしょう。

メンバ

メンバ関数と関数のみ書きます。

// 何の変哲もないメンバばかり
struct forward_iterator {
	forward_iterator();
	forward_iterator(const forward_iterator& x);
	forward_iterator& operator =(const forward_iterator& x);
	// 参照も書き込みも可能です。
	const_reference operator *() const;
	pointer operator ->() const;
	forward_iterator& operator ++();
	forward_iterator operator ++(int);
};
bool operator ==(const forward_iterator& x, const forward_iterator& y);
bool operator !=(const forward_iterator& x, const forward_iterator& y);

BidirectionalIterator

双方向へ進むことができるイテレータ。 もちろん参照や代入も可能です。
list::iterator、set::iterator、map::iteratorなどはこれに分類されます。

メンバ

メンバ関数と関数のみ書きます。

// 何の変哲もないメンバばかり
struct bidirectional_iterator {
	bidirectional_iterator();
	bidirectional_iterator(const bidirectional_iterator& x);
	bidirectional_iterator& operator =(const bidirectional_iterator& x);
	const_reference operator *() const;
	pointer operator ->() const;
	bidirectional_iterator& operator ++();
	bidirectional_iterator operator ++(int);
	bidirectional_iterator& operator --();
	bidirectional_iterator operator --(int);
};
bool operator ==(const bidirectional_iterator& x, const bidirectional_iterator& y);
bool operator !=(const bidirectional_iterator& x, const bidirectional_iterator& y);

RamdomAccessIterator

ランダムアクセス可能なイテレータ。 ポインタに対して可能な操作が全て行えます。
vector::iterator、deque::iteratorなどはこれに分類されます。 ポインタもRandomAccessIteratorとして使用出来ます。

メンバ

メンバ関数と関数のみ書きます。

// なにか忘れてないといいけど
struct random_access_iterator {
	random_access_iterator();
	random_access_iterator(const random_access_iterator& x);
	random_access_iterator& operator =(const random_access_iterator& x);
	const_reference operator *() const;
	pointer operator ->() const;
	random_access_iterator& operator ++();
	random_access_iterator operator ++(int);
	random_access_iterator& operator --();
	random_access_iterator operator --(int);
	// イテレータ + 数字
	random_access_iterator operator +(difference_type n) const;
	// イテレータ += 数字
	random_access_iterator& operator +=(difference_type n);
	// イテレータ - 数字
	random_access_iterator operator -(difference_type n) const;
	// イテレータ -= 数字
	random_access_iterator& operator -=(difference_type n);
	reference operator [](difference_type n) const;
};
// イテレータ同士の引き算x - y
random_access_iterator::difference_type
    operator -(const random_access_iterator& x,
    	       const random_access_iterator& y);
// 数字 + イテレータ
random_access_iterator
    operator +(const difference_type n, const random_access_iterator& y);

bool operator ==(const random_access_iterator& x,
		 const random_access_iterator& y);
bool operator !=(const random_access_iterator& x,
		  const random_access_iterator& y);
// ランダムアクセスイテレータなら大小の比較も可能。
bool operator <(const random_access_iterator& x,
		 const random_access_iterator& y);
bool operator >(const random_access_iterator& x,
		 const random_access_iterator& y);
bool operator <=(const random_access_iterator& x,
		  const random_access_iterator& y);
bool operator >=(const random_access_iterator& x,
		  const random_access_iterator& y);

特殊なイテレータ

class back_insert_iterator
class front_insert_iterator

コンテナに要素を追加するための挿入反復子。 コンテナのメンバを使って要素を追加する出力イテレータです。 このイテレータが指す要素に対して要素の代入が行われる時にpush_back()やpush_front()でコンテナの最後尾に要素を挿入します。

テンプレート

// コンテナを指定します。
template <class Container>

メンバ関数

front_insert_iteratorの場合も同じです。

// コンストラクタ
explicit back_insert_iterator(Container& x);
// 代入演算子。コンテナに要素を追加します。
back_insert_iterator<Container>&
    operator =(const typename Container::value_type& value);
// 出力イテレータなので要素の参照はできない。
// 自分自身(*this)を返すので上の関数で代入は可能だが。
back_insert_iterator<Container>& operator *();
// インクリメントしても何もしないで自身を返すだけ。
back_insert_iterator<Container>& operator ++();
back_insert_iterator<Container>& operator ++(int);

ヘルパ関数

コンテナを渡すだけでback_insert_iteratorを生成できるヘルパ関数です。

template <class Container>
back_insert_ierator<Container> back_inserter(Container& x);
template <class Container>
front_insert_ierator<Container> front_inserter(Container& x);

insert_iterator

コンテナに要素を追加するための挿入反復子。 コンテナのメンバを使って要素を追加する出力イテレータです。 このイテレータが指す要素に対して要素の代入が行われる時にinsert()でコンテナの任意の位置に要素を挿入します。

template <class Container>
// コンストラクタではコンテナと挿入位置を示すイテレータが渡されます。
insert_iterator(Container& x, typename Container::iterator i);
// 代入演算子。代入の際にコンテナのinsertが呼ばれて要素が挿入されます。
insert_iterator<Container>&
    operator =(const typename Container::value_type& value);
// 出力イテレータなので要素の参照はできない。
// 自分自身(*this)を返すので上の関数で代入は可能だが。
inesrt_iterator<Container>& operator *();
// インクリメントしても何もしないで自身を返すだけ。
inesrt_iterator<Container>& operator ++();
inesrt_iterator<Container>& operator ++(int);

ヘルパ関数

コンテナを渡すだけでinsert_iteratorを生成できるヘルパ関数です。

template <class Container, class Iterator>
insert_ierator<Container> inserter(Container& x, Iterator i);

reverse_bidirectional_iterator

逆双方向反復子?標準では用意されていないようです。 普通のイテレータを++で後ろへ、--で前へ進む逆行イテレータにするイテレータです。

template <class BidirectionalIterator, class T,
	  class Reference, class Distance>
// コンストラクタ
reverse_bidirectional_iterator();
explicit reverse_bidirectional_iterator(BidirectionalIterator x);
// 元のイテレータを返す。
BidirectionalIterator base() const;
// 参照
reference operaot *() const;
// ->は使えるとは限らない
pointer operator ->() const;
// 一つ進める(後ろに戻る)
self& operator ++();	// 前値式
self operator ++(int);		// 後値式
// 一つ戻す(前に進める)
self& operator --();	// 前値式
self operator --(int);		// 後値式

非メンバ

template <class BidirectionalIterator, class T, class Reference,
	  class Distance>
bool operator ==(const reverse_bidirectional_iterator< /* 省略 */ > &x,
		 const reverse_bidirectional_iterator< /* 省略 */ > &y);

reverse_iterator

逆行反復子。++で後ろに、--で前に進みます。 普通のランダムアクセスイテレータを逆行イテレータとして使うために使用します。

テンプレート

// 元のイテレータを指定。
template <class Iterator>

メンバ関数

// コンストラクタ
reverse_iterator();
// iteratorがRandomAccessiteratorの場合もあります。このへんは後で両方書きます。
explicit reverse_iterator(iterator_type x);
reverse_iterator(const reverse_iterator& x);
// メンバテンプレート版
template <class Iter>
reverse_iterator(const reverse_iterator<iter> &x);
// 元のイテレータを返す
iterator_type base() const;
// 参照
reference operator *() const;
// ->は使えるとは限らない
pointer operator ->() const;
// 進む方向が逆であることを除けば普通のランダムアクセスイテレータと同じ
self& operatpr ++();
self operatpr ++(int);
self& operatpr --();
self operatpr --(int);
self operator +(difference_type n) const;
self& operator +=(difference_type n);
self operator -(difference_type n) const;
self& operator -=(difference_type n);
reference operator [](difference_type n) const;

非メンバ

template <class Iterator>
bool operator ==(const reverse_iterator<Iterator>& x,
		 const reverse_iterator<Iterator>& y);
bool operator <(const reverse_iterator<Iterator>& x,
		const reverse_iterator<Iterator>& y);
typename reverse_iterator<Iterator>::difference_type
    operator -(const reverse_iterator<Iterator>& x,
	       const reverse_iterator<Iterator>& y);
reverse_iterator<Iterator>
    operator +(reverse_iterator<Iterator>::difference_type n,
	       const reverse_iterator<Iterator>& x);

istream_iterator

入力ストリームから読み込みを行うイテレータ。

テンプレート

// イテレータが扱う型と差を表す型。
// charTやtraitsはストリームと同じものを、Distanceはとくに気にする必要はありません。
template <class T, class charT = char, class traits = char_traits<charT>,
	  class Distance = ptrdiff_t>
// SGI_STLではこう
template <class T, class Distance = ptrdiff_t>

メンバ関数

// コンストラクタ
istream_iterator();
// ストリームをイテレータに
istream_iterator(istream& s);
// コピーコンストラクタ
istream_iterator(const istream_iterator& x);
~istream_iterator();
// ストリームから読んだ値を返す
const_reference operator *() const;
// ->は使えるとは限らない。
const_pointer operator ->() const;
// ストリームから次の要素を読む
istream_iterator<T, charT, traits, Distance>& operator ++();
istream_iterator<T, charT, traits, Distance> operator ++(int);

非メンバ

template <class T, charT, traits, class Distance>
bool operator ==(const istream_iterator<T, charT, traits, Distance>& x,
		 const istream_iterator<T, charT, traits, Distance>& y);

ostream_iterator

出力ストリームに対して出力を行う出力イテレータ。

テンプレート

// Tはイテレータが扱う要素。charTやtraitsはストリームと同じです。
template<class T, class charT = char, class traits = char_traits<charT> >

メンバ関数

// コンストラクタ
ostream_iterator(ostream& s);
ostream_iterator(ostream& s, const charT* delimiter);
// コピーコンストラクタ
ostream_iterator(const ostream_iterator<T, charT, traits>& x);
// デストラクタ
~ostream_iterator();
// このイテレータに対する代入は出力ストリームへの出力となる。
ostream_iterator<T, charT, traits>& operator =(const T& value);
// 以下のメンバはいずれも自分自身(*this)を返すだけで何もしない。
// ostream_iteratorはoperator=()での代入時に次の要素を出力する
ostream_iterator<T, charT, traits>& operator *();
ostream_iterator<T, charT, traits>& operator ++();
ostream_iterator<T, charT, traits>& operator ++(int);

イテレータ関連の関数

iterator_category()

イテレータの種類(カテゴリ)を返す。

template <class Iterator>
typename iterator_traits<Iterator>::iterator_category
    iterator_category(const Iterator &);
// 部分特殊化バージョンのテンプレートが使えない場合は返り値の型は
// 単に*_iterator_tagが返る。

distance()

イテレータ同士の距離を求める

// firstとlastの距離を返す。
template <class InputIterator>
iterator_traits<InputIterator>::difference_type
    distance(InputIterator first, InputIterator last);

// 部分特殊化バージョンのテンプレートが使えない場合
// nにfirstからlastまでの距離を返す。
// InputIteratorがRandomAccessIteratorならそのままメモリ上の距離を
// それ以外はfirstからlastまで幾つの要素があるかを返す。
template <class InputIterator, class Distance>
void distance(InputIterator first, InputIterator last, distance& n);

advance()

イテレータを進める

// iをn進めます。
template <class InputIterator, class Distance>
void advance(InputIterator& i, Distance n);

何故、イテレータを使うのか

例えば、vectorはポインタを進めれば自然と次の要素をさすが、 リストなどは次の要素を指すポインタを参照する必要がある。
そこで、コンテナの要素を辿る際のインターフェースを統一し、 コンテナの種類に依存することなく同様の方法で要素にアクセス出来るようにしたわけですね。

何に使うのか

<algorithm>ではほとんどの関数がiteratorを引数としています。
ですから、どんなコンテナを使用していようと(一部制限*あり)一つの関数で 全てのコンテナに対応出来るわけです。
こんな説明でいいのかな?

* ランダムアクセス出来なきゃならないこともあるし、双方向にアクセスできなきゃならないこともある。


Comments