|
（このコンテンツはメールマガジンの STL & iostream 入門に手を加えたものです。「 STL と iostream が使えるかのチェック」等はメールマガジンの方のページをご覧ください）
|
|
イテレーター ( #14 ) |
|
これまでのアルゴリズムの使用例では、ずっと「配列を指すポインタ」を使用していました。今回からはこの点について見ていきます。
実はこのアルゴリズムに渡す「操作する対象」は、ポインタとは限らないのです。アルゴリズムに渡す「操作対象」の正式名称は「イテレーター」と言います。 イテレーターを具体的に表現すれば「 ++, *, != のみっつの演算子が機能する型の変数」となります。例えば std::fill() は
template
< class type_ForwardIter
, class type_Value >
void fill
( type_ForwardIter p_Begin // イテレーター１。
, type_ForwardIter p_End // イテレーター２。
, const type_Value &p_rValue )
{
for( ; p_pBegin != p_pEnd; ++p_pBegin )
*p_pBegin = p_rValue;
}
となっています。まず、イテレーターの型はテンプレート引数で表されているので、基本的にはどんな型でも渡すことができます。イテレーター変数の p_pBegin と p_pEnd には「 ++, *, != 」のみっつの演算子が使用されています。これらの演算子が使用できれば、イテレーターとして使用できるということです。 イテレーターになれるもののひとつは、当然ポインタです。これは、これまでの使用例を見ていれば分かるでしょう。 もうひとつ、イテレーターになれるものがあります。それはクラスです。クラスの「演算子のオーバーロード」を使うことで「 ++, *, != 」のみっつの演算子が機能するようにすることができます。つまり、次のようなクラスです。
////////////////////////////////////////////////////////////////
class CIteratorSample
: public std::iterator< std::input_iterator_tag, int >
{
public:
const int &operator *(); // *
CIteratorSample &operator ++(); // ++
bool operator !=( const CIteratorSample &p_cRh ) const; // !=
};
/////////////////////////////
このみっつのメンバ関数を備えたクラスなら、これまでポインタを使用していた部分に、代わりにこのクラスを使用できるのです。 ちなみに std::iterator は、 #10 で紹介した std::unary_function のような「イテレーターを作るときに継承元としなければならないクラス」です。これについては後ほど紹介します。 このへんてこイテレータークラス、試しに実装して使ってみましょう。
////////////////////////////////////////////////////////////////
// CIteratorSample の使用例。
#define __STL_HAS_NAMESPACES // gcc ではこれが必要でした。
#include <stdio.h>
#include <algorithm>
class CIteratorSample
: public std::iterator< std::input_iterator_tag, int >
{
int m_i;
public:
CIteratorSample()
: m_i( 0 )
{}
const int &operator *()
{
return m_i;
}
CIteratorSample &operator ++()
{
++m_i;
return *this;
}
bool operator !=( const CIteratorSample &p_cRh ) const
{
if( m_i == 3 )
return false;
return true;
}
};
// 使用例。
void Use_CIteratorSample()
{
CIteratorSample cIter
= std::find
( CIteratorSample()
, CIteratorSample()
, 2 );
printf( "%d\n", *cIter );
}
// 結果
2
/////////////////////////////
まぁ特に意味のない実装例＆使用例ですが、とりあえずこういったクラスならイテレーターとして使用できることは分かったと思います。 |
|
イテレータータグ ( #15 ) |
|
アルゴリズムのリファレンスを読むと、イテレーターとして受け取る引数の型が InputIterator とか ForwardIterator とか書かれていると思います。これらは「イテレーターの種類」を示しています。
イテレーターには５つの種類があります。 InputIterator OutputIterator ForwardIterator BidirectionalIterator RandomAccessIterator の５つです。 InputIterator: 読み取り専用イテレーター。アルゴリズムはこのイテレーターには書き込みません。ポインタで言うなら const 型へのポインタです。 std::find() などの検索系や std::copy() の「コピー元」のイテレーターがこれにあたります。 OutputIterator: 書き込み専用イテレーター。アルゴリズムはこのイテレーターを通してデータを書き込みます。ポインタは非 const 型へのポインタでなければなりません。クラスの場合、 * 演算子は非 const 型への参照を返す必要があります。 std::copy() の「コピー先」のイテレーターがこれに当たります。 ForwardIterator: InputIterator と OutputIterator の両方、つまり読み取りと書き込みの両方が行われます。実際には次の BidirectionalIterator の「一方向」版として、一般的なイテレーターという意味で使われていることの方が多いようです。 BidirectionalIterator: 双方向イテレーターです。 ForwardIterator にデクリメント演算子 -- の機能を持たせたものを渡す必要があります。つまりイテレーターは前後に走査されることになります。ポインタはもちろん使えます。クラスは -- 演算子を持っていないと使えません。 std::reverse() のように「後ろから」が必要なアルゴリズムがこのイテレーターを求めます。 RandomAccessIterator: BidirectionalIterator に「要素位置の和と差」の演算ができることが求められるイテレーターです。つまりポインタの「アドレスの足し算引き算」のことです。クラスを渡すときには + と - の演算子を装備している必要があります。 std::sort() のように様々な位置の要素へとアクセスするするアルゴリズムが必要とします。 この５つイテレーターの区分は、ふたつの意味を持っています。 ひとつは「アルゴリズムがイテレーターに対してどういった処理をするのか」という意味。 BidirectionalIterator を受け取るのなら「 -- 演算子を使いますよ」という意味ですし、 InputIterator を受け取るのなら「書き込まないので const 型へのポインタもいいですよ」という意味になります。 もうひとつは「イテレーターが持っている機能」という意味。イテレータークラスが -- 演算子を持っていればそのクラスは BidirectionalIterator と言えますし、 const 型へのポインタは OutputIterator ではない、と言えます。 実際の意味としては前者の方が強いと思います。ですが、ライブラリの機能としては後者の方が強いものがあります。 イテレーターには「イテレータータグ」という、イテレーターの５つの種類を示すクラスが存在します。 input_iterator_tag output_iterator_tag forward_iterator_tag bidirectional_iterator_tag random_access_iterator_tag と、どれもただ最後に tag を付けただけの名称になっています。これらはイテレーターがどの種類かを示します。 前回紹介したイテレータークラスのサンプルは、
class CIteratorSample
: public std::iterator< std::input_iterator_tag, int >
と std::iterator のテンプレート引数にこのイテレータータグを渡しています。これを渡すことで、自分のクラスが「どのイテレーターに当たるのか」を示すことができます。
////////////////////////////////////////////////////////////////
// イテレータータグ の使用例。
#define __STL_HAS_NAMESPACES // gcc ではこれが必要でした。
#include <stdio.h>
#include <algorithm>
// 前回の CIteratorSample をここに書いてください。
void IteratorTagFunc( std::input_iterator_tag p_cTag )
{
printf( "input_iterator_tag\n" );
}
void IteratorTagFunc( std::output_iterator_tag p_cTag )
{
printf( "output_iterator_tag\n" );
}
void Use_iterator_tag()
{
IteratorTagFunc
( std::iterator_traits<CIteratorSample>::iterator_category() );
}
// 結果
input_iterator_tag
/////////////////////////////
関数 IteratorTagFunc() は、イテレータータグを引数に受け取ります。このタグの種類でオーバーロードしています。この関数に「 CIteratorSample のイテレーターの種類」を渡します。この種類を取り出すときには std::iterator_traits というクラステンプレートを通して std::iterator_traits::iterator_category という型メンバから取り出します。この型は std::iterator の第１テンプレート引数と同じものです。 CIteratorSample は std::input_iterator_tag を渡していたので、これと同じ型になります。 結果、オーバーロードは std::input_iterator_tag を引数に持つ方が選択されます。 以上のようにして、イテレーターの種類を「コンパイラが」見分けられるようになっています。これと同様の機能がアルゴリズムにも備わっていて、イテレーターの種類に合わせて実際に処理する関数を選択したり、使えないイテレーターが渡されたときにコンパイルエラーを発生させることができるのです。 |
|
イテレーターの作り方 ( #16 ) |
|
イテレータークラスは STL にはあまり用意されていませんので、実際にはその多くを自分で作る必要があります。その辺は関数オブジェクトと同様ですね。アルゴリズムという「仲介者」を用意してその回りをプログラマーが作る、というのが STL のスタイルだと思ってください。
さて、今回はイテレータークラスの作り方を見てみましょう。いきなり複雑なものを作っても難しいので「ポインタの操作を仲介するイテレータークラス」を作ります。つまりポインタのラッパーですね。
////////////////////////////////////////////////////////////////
// イテレータークラスの作成例。
#define __STL_HAS_NAMESPACES // gcc ではこれが必要でした。
#include <stdio.h>
#include <algorithm>
class CIntPointerIterator
: public std::iterator< std::output_iterator_tag, int >
{
int *m_piData;
public:
CIntPointerIterator( int *p_piData )
: m_piData( p_piData )
{}
CIntPointerIterator &operator ++()
{
++m_piData;
return *this;
}
int &operator *()
{
return *m_piData;
}
bool operator !=( const CIntPointerIterator &p_rcRh )
{
return m_piData != p_rcRh.m_piData;
}
};
// 使用例。
void Use_CIntPointerIterator()
{
int iSourceAry[] = { 3, 5, 1, 6, 3, 1 };
int iAry[6];
std::copy
( iSourceAry, iSourceAry + 6
, CIntPointerIterator( iAry ) );
for( int *pi = iAry; pi != iAry + 6; ++pi )
printf( "%d, ", *pi );
}
// 結果
3, 5, 1, 6, 3, 1,
/////////////////////////////
今回はコピーに使うのでアウトプットイテレーターにしました。なので継承元の std::iterator のテンプレート引数には std::output_iterator_tag を渡します。 メンバ変数はひとつ、操作対象のポインタです。ここでは int にしていますが、皆さんが作るときにはテンプレート化したほうがいいでしょう。 コンストラクタでは操作対象となるポインタを受け取って、メンバ変数に格納します。このポインタは非 const 型へのものなので、 const 型へのポインタは受け取れません。こうすることで「アウトプットイテレーター」だということを示します。 また、ここではこのコンストラクタひとつしか作っていませんが、安全性を考えれば private なデフォルトコンストラクタを作った方がいいかもしれません。 そのあとは、各演算子のオーバーロードです。 ++ 演算子はポインタをひとつ進めて、自クラスへの参照を返します。これは this ポインタを通して返します。 * 演算子は、ポインタが指し示す値への参照を返します。インプットイテレーターは、この関数の const 版を作る必要があります。インプットイテレーターは const 、アウトプットイテレーターは非 const ということですね。 != 演算子はポインタが一致するかどうか比較します。普通、このような比較演算子はグローバル関数として作るのが普通ですが、イテレーターの場合テンプレート引数の関係で「イテレータークラスどうしの比較」がほとんどなのでメンバ関数でも機能するはずです。 また、 ++ や != で「自クラス型への参照」が使われています。自クラスはクラス名が変わると書き換えなくてはならないので、「自クラス型」をtypedef した型メンバを使用した方がいいかもしれません。 |
 |
|
以上がアウトプットイテレーターに必要な演算子です。ランダムアクセスイテレーターの場合には、これに -- 、 + 、 - が必要になります。この例ならポインタの演算をそのまま使えばいいので、特に難しいことはないでしょう。
イテレータークラスを作るコツは、まず演算子を装備させて、その演算子の実装で「ポインタならどう振る舞うか」を考えるとうまく作れると思います。そのためにもまずポインタそのものを操作する、この例を試してみてください。 |
|
イテレーターの汎用性 ( #17 ) |
イテレーターは「ポインタのように振る舞うクラス」です。つまり複数の要素を持ち、それにアクセスする、そういった機能を持ったクラスであればイテレーターにすることができて、膨大な種類を持つアルゴリズムに使うことができるのです。コンピューターには配列のように操作したいものがたくさんあります。ディレクトリ内のファイル、ダイアログコントロール、データベースなど、これらは特定の関数やクラスを使用して操作します。その操作をイテレータークラスで囲むことで、これまで専用の操作用関数を用意していたのが、すべてアルゴリズムに取って代えることができるのです。また、これらの操作は OS ごとに違うのが普通ですが、それらをイテレーターで吸収し、操作はすべての OS で使える STL アルゴリズムで行うことで、ポータビリティが格段に増すことでしょう。 イテレータークラスの作成例を見てみましょう。 iostream のクラスは、性質上繰り返し使用することが多いと思います。 iostream のクラスを使うイテレーターを作ってみます。 実は、 std::istream_iterator と std::ostream_iterator というストリームクラス用イテレーターがすでに用意されていますが、今回はこの簡易版を作って、イテレーターの作成例として見ていくことにしましょう（もちろん皆さんが実際に使う場合には std::istream_iterator と std:::stream_iterator を使いましょう）。
////////////////////////////////////////////////////////////////
// イテレータークラスの作成例。
#define __STL_HAS_NAMESPACES // gcc ではこれが必要でした。
#include <stdio.h>
#include <algorithm>
#include <strstream>
class Cistrstream_iteratorMini
: public std::iterator< std::input_iterator_tag, int >
{
std::istrstream *m_pcIStrm; // 使用するストリームクラス。
int m_iData;
public:
Cistrstream_iteratorMini()
: m_pcIStrm( 0 )
{}
Cistrstream_iteratorMini( std::istrstream &p_rcIStrm )
: m_pcIStrm( &p_rcIStrm )
{
operator ++();
}
Cistrstream_iteratorMini &operator ++()
{
if( m_pcIStrm != 0 )
*m_pcIStrm >> m_iData;
if( m_pcIStrm->fail() )
m_pcIStrm = 0;
return *this;
}
const int &operator *() const
{
return m_iData;
}
bool operator !=( const Cistrstream_iteratorMini &p_rcRh )
{
return m_pcIStrm != p_rcRh.m_pcIStrm;
}
};
// 使用例。
void Use_Cistrstream_iteratorMini()
{
char chSource[] = "100 200 300";
std::istrstream cIStrm( chSource );
int iAry[3];
std::copy
( Cistrstream_iteratorMini( cIStrm )
, Cistrstream_iteratorMini()
, iAry );
for( int *pi = iAry; pi != iAry + 3; ++pi )
printf( "%d, ", *pi );
}
// 結果
100, 200, 300,
/////////////////////////////
イテレータークラス Cistream_iteratorMini は、 std::istrstream を受け取って、イテレーター化します。 データを読み取るための Cistrstream_iteratorMini イテレーターは、 std::istrstream 型変数を受け取りそれをポインタとして格納します。 「ストッパー」となる Cistrstream_iteratorMini イテレーターは、 何も渡さずに初期化します。そうすると、内部ポインタを 0 で初期化します。 アルゴリズム std::copy() 内部では、イテレーターに ++ 演算子を使用します。これにより Cistrstream_iteratorMini::operator ++() が呼び出され、文字配列から整数値としてデータを取り出します。 取り出したデータは Cistrstream_iteratorMini::operator *() で取り出され、 iAry の各要素へとコピーされます。 コピーしたあと、イテレーターが「ストッパー」イテレーターと一致しているか調べるため Cistrstream_iteratorMini::operator !=() が呼ばれます。この中では std::istrstream を指すポインタが同じかどうか調べられます。ストッパーは 0 なので、操作されている側のポインタが 0 になるまで操作が続けられることになります。 Cistrstream_iteratorMini::operator ++() は、データを取りだしたときに「整数値以外のデータ」や「最後まで読み取った」でないかチェックします。これらに当てはまる場合に、自らが持つ std::istrstream を指すポインタを 0 にします。 これによって、ストッパーとイテレーターが一致して、 std::fill() は処理を終了します。 Cistrstream_iteratorMini は、イテレータークラスとして機能しつつ、std::istrstream をうまく操作しています。このようなイテレータークラスひとつあれば、アルゴリズムに使用することができるのです。 |