独自のイテレータを実装する - C++ プログラミング
PROGRAM
独自のイテレータを実装する
C++ の STL (Standard Template Library) では、std::for_each 関数 や std::fill 関数、std::vecotor<> クラス や、std::unordered_map クラス など、さまざまな場面で "イテレータ" という考え方が登場します。
イテレータというのは、ある値の保存場所を示すもので、通常の C 配列操作と互換性のあるクラスです。
std::vector<> や std::unordered_map<> では、それらが保持する値を順次取得するためのイテレータがあらかじめ用意されていますが、そのようなイテレータを自分で作って、独自のクラスで使用することもできるようになっています。
そこで今回は、イテレータを自分のクラスに実装する方法について見て行きます。
イテレータの種類と実装内容
イテレータの種類
自作のクラスにイテレータを実装する場合は、それを扱うためのイテレータクラスを作成する必要があります。
このとき独自のイテレータクラスは、<iterator> ヘッダーに定義されている std::iterator<> クラスから派生したクラスとして作成する必要があるのですが、このとき、この独自のイテレータクラスがどのような振る舞いをサポートしているかを指定する必要があります。
イテレータの振る舞いは、次の種類から選択できます。
| イテレータの種類 | 読取 | 書込 | 進む | 戻る | 幾つか進む 幾つか戻る |
比較 等号 |
比較 不等号 |
概要 |
|---|---|---|---|---|---|---|---|---|
| 関連する実装 （他も必要な場合は各欄に追記） |
*a a->m |
*a | ++a a++ |
--a a-- |
a+n, +=n a-n, -=n |
a==b a!=b |
a>b a<b a>=b a<=b |
|
| std:: input_iterator_tag |
提供 | - | 提供 | - | - | 提供 | - | 読み取り専用のイテレータです。取得した値に書き込む機能は提供しません。 |
| std:: output_iterator_tag |
- | 提供 | 提供 | - | - | - | - | 書き込み専用のイテレータです。値を取得する機能は提供しません。 |
| std:: forward_iterator_tag |
提供 | 提供 a->m |
提供 | - | - | 提供 | - | 読み書きを提供するイテレータです。先頭から終わりまで順次ひとつずつ取得して自由に処理させるための一般的なイテレータです。 |
| std:: bidirectional_iterator_tag |
提供 | 提供 a->m |
提供 |
提供 | - | 提供 | - | 読み書きを提供するイテレータです。好きな位置から自由に前後にひとつずつ移動する機能を提供することで、逆順取得なども行えるようにします。 |
| std:: random_access_iterator_tag |
提供 a[n] |
提供 a[n] |
提供 | 提供 | 提供 | 提供 | 提供 | 読み書きを提供するイテレータです。好きな位置から自由に前後に好きな量だけ移動する機能を提供することで、ソートなどの高度な操作も行えるようにします。 |
この表で記した機能は少なくとも提供すべき機能なので、必要以上の機能や、これ以外の機能を実装することもできます。
また、これらのイテレータのどれにもコピーコンストラクタが必要になります。
コピーの負荷が気になる場合はムーブコンストラクタを実装してもいいと思いますが、単純なイテレータであれば扱うクラスをポインタで受け取るようにすれば、ムーブコンストラクタを考慮するほどのものにはならないことが多そうです。
イテレータの実装内容
さて、これらの実装機能について、実際にどのような実装を行えばいいかを整理してみます。
| 機能 | 実装 | 実装の定義例 | 実装内容 |
|---|---|---|---|
| 読取 書込 |
*a | const T& operator*() const; T& operator*(); |
間接演算子を使って、イテレータが指す場所の参照を取得できるようにします。 |
| 読取 書込 |
a->m | const T& operator->() const; T& operator->(); |
イテレータで扱う値がクラスの場合はメンバ選択演算子を使って、イテレータが指す場所のクラスのメンバを直接呼び出せるようにします。 |
| 読取 書込 |
a[n] | const T& operator[](int n) const; T& operator[](int n); |
添え字演算子を使って、イテレータが指す場所から任意の位置の参照を取得できるようにします。 |
| 進む（前置） | ++a | iterator& operator++(); | イテレータの位置を次の位置に進めます。戻り値はイテレータ自身への参照を返します。 |
| 進む（後置） | a++ | iterator operator++(int); | イテレータの位置を次の位置に進めます。戻り値は、イテレータを進める前の位置を示したイテレータのコピーを返します。引数の int は仕様上のダミーです。 |
| 戻る（前置） | --a | iterator& operator--(); | イテレータの位置を前の位置に戻します。戻り値はイテレータ自身への参照を返します。 |
| 戻る（後置） | a-- | iterator operator--(int); | イテレータの位置を前の位置に戻します。戻り値は、イテレータを戻す前の位置を示したイテレータのコピーを返します。引数の int は仕様上のダミーです。 |
| 幾つか進む | +=n | iterator& operator+=(size_t n); | イテレータの位置を、引数で指定した数だけ進めます。戻り値はイテレータ自身への参照を返します。 |
| 幾つか進む | a+n | iterator operator+(size_t n); | イテレータの位置を、引数で指定した数だけ進めたイテレータを返します。自分自身の位置は変化しません。 |
| 幾つか戻る | -=n | iterator& operator-=(size_t n) | イテレータの位置を、引数で指定した数だけ戻します。戻り値はイテレータ自身への参照を返します。 |
| 幾つか戻る | a-n | iterator operator-(size_t n); | イテレータの位置を、引数で指定した数だけ戻したイテレータを返します。自分自身の位置は変化しません。 |
| 比較・等号 | a==b a!=b |
bool operator==(const iterator& it) const; bool operator!=(const iterator& it) const; |
自分自身と指定されたイテレータとが一致するか (==) や一致しないか (!=) を判定します。 |
| 比較・不等号 | a>b a<b a>=b a<=b |
bool operator>(const iterator& it) const; bool operator<(const iterator& it) const; bool operator>=(const iterator& it) const; bool operator<=(const iterator& it) const; |
自分自身指す位置が指定されたイテレータと比べて、先か (>)、手前か (<)、同じか先か (>=)、同じか手前か (<=) を判定します。 |
これらの機能を実装したイテレータを定義して、それを begin 関数と end 関数とで適切な値を揃えて返すことで、イテレータに対応したクラスを作ることができます。
イテレータの実装例
イテレータ実装の雰囲気を掴むために、具体的な例を挙げてみます。
具体例とは言っても、ここで作成するイテレータは話を簡単にするために、メンバ変数に保持している 1 つの int しか返さないイテレータという実用的には意味のない実装になっていますが、参考にはなると思います。
作成するクラス
今回作成するクラスは、次の二つです。
| CMyClass | serial という int 型の値を保持するクラスです。 |
|---|---|
| CMyClassIterator | CMyClass が持つ serial の値を取得するイテレータです。イテレータの種類は std::forward_iterator_tag にします。 |
イテレータは本来、複数の値を順序立てて取得するための仕組みなので、今回のように 1 つの値しか返さないものを作ることはまずないですが、練習のためにこのようなイテレータを作成します。
クラスのプロトタイプ宣言
CMyClass のプロトタイプ宣言
まず、値を扱う CMyClass の実装について見ていきます。
基本的には、メンバ変数 m_serial で値を持ち、その値を serial() メンバ関数を使って取得できるようにします。
ただし今回はイテレータを扱うため、次の箇所でイテレータ用の特別な実装をしています。
- CMyClassIterator を CMyClass のローカルクラス CMyClass::iterator として使えるようにします。
- イテレータが private メンバに自由にアクセスできるように、CMyClassIterator を firend 指定します。
- 開始位置を示したイテレータを取得するメンバ関数 begin を実装します。
- 終了位置を示したイテレータを取得するメンバ関数 end を実装します。
これらを踏まえて、ヘッダーファイルは次のような記載になりました。
// CMyClass の定義中に CMyClassIterator が登場するので、それがクラスであることだけを明示しておきます。
class CMyClassIterator;
// CMyClass のプロトタイプ宣言です。
class CMyClass
{
// CMyClassIterator が private メンバにアクセスできるように friend 指定します。
friend CMyClassIterator;
// イテレータに関する実装です。
public:
// CMyClassIterator をローカルクラス CMyClass::iterator として使えるようにします。
typedef CMyClassIterator iterator;
// 開始位置を示すイテレータを取得するメンバ関数です。
CMyClass::iterator begin();
// 終了位置を示すイテレータを取得するメンバ関数です。
CMyClass::iterator end();
// イテレータ以外の通常の実装です。
private:
int m_serial;
public:
CMyClass();
CMyClass(const CMyClass& myClass);
int serial() const;
};
CMyClassIterator のプロトタイプ宣言
CMyClassIterator クラスもそれほど難しいことはありませんが、イテレータを実装する上でちょっと特殊なところもあるので、その辺りに注意しながら定義します。
イテレータクラスの定義は、次の箇所に気を付けながら行います。
- <iterator> ヘッダーをインクルードします。
- イテレータクラスは std::iterator<> クラスから派生します。このとき、イテレータの種類を示すタグと、扱う値のデータ型を指定します。
- イテレータが勝手に作られることがないように、ディフォルトコンストラクタと初期化コンストラクタを private にします。
- CMyClass がイテレータを作成できるように、CMyClass を friend に指定します。
- 最低限、タグで指定した種類のイテレータがサポートすべき機能を実装します。
今回は、前方に移動しながら読み書きができるイテレータを作成しようと思うので、イテレータの種類は std::forward_iterator_tag を指定することにします。
イテレータで表現する位置は、今回は、何番目の情報かを m_index で持たせてみます。最後の情報を示す場合は m_index に SIZE_MAX を設定します。
CMyClassIterator では順番だけを記憶して、実際の値はイテレータ構築時に CMyClass のポインタを渡しておいて、そこから取り出すようにします。
これらを踏まえてイテレータクラスを定義すると、次のようになりました。
// std::iterator<> が定義された <iterator> ヘッダーをインクルードします。
#include <iterator>
// CMyClassIterator の定義中に CMyClass が登場するので、それがクラスであることだけを明示しておきます。
class CMyClass;
// CMyClassIterator のプロトタイプ宣言です。
// std::iterator<> を std::forward_iterator_tag を指定して継承します。扱う値の型は int とします。
class CMyClassIterator : public std::iterator<std::forward_iterator_tag, int>
{
// CMyClass が private なコンストラクタを呼び出せるように friend 指定します。
friend CMyClass;
// 値の場所を示すメンバ変数と、取り扱う CMyClass へのポインタを private に格納します。
private:
size_t m_index;
CMyClass* m_myClass;
// イテレータを構築するコンストラクタは private に持たせ、外部で勝手に作れないようにします。
private:
CMyClassIterator();
CMyClassIterator(CMyClass* myClass, int index);
// イテレータのコピーコンストラクタは public から呼び出せるようにします。
public:
CMyClassIterator(const CMyClassIterator& iterator);
// フォワードイテレータで必要な実装です。
public:
CMyClassIterator& operator++();
CMyClassIterator operator++(int);
int& operator*();
bool operator==(const CMyClassIterator& iterator);
bool operator!=(const CMyClassIterator& iterator);
};
クラスの実装
プロトタイプ宣言ができたら、後はクラスの実装を状況に合わせて書くだけになりますけど、雰囲気だけでも掴めるように、先ほど定義したメンバについて、補足を交えつつ実装してみます。
ただ、今回は CMyClass にある唯一のメンバ変数 m_index をひとつだけ返すイテレータになっているので、実際に実装するときには値の位置を管理する辺りでもう少し複雑な実装になってくると思います。
CMyClassIterator の実装
まずはイテレータを実現する CMyClassIterator の実装について見て行きます。
コンストラクタの実装
コンストラクタは CMyClass がイテレータを作るときに使うコンストラクタを private に、プログラムが取得したイテレータをコピーするときに使うコピーコンストラクタを public に、それぞれすみ分けて定義しましたけど、実装方法は普段と特には変わりません。
// 既定のコンストラクタでは、今回は末端に相当するイテレータを作成します。
CMyClassIterator::CMyClassIterator()
{
m_myClass = nullptr;
m_index = SIZE_MAX;
}
// このコンストラクタでは、扱うインスタンスと最初の位置情報を受け取ってイテレータを作成します。
CMyClassIterator::CMyClassIterator(CMyClass* myClass, int index)
{
m_myClass = myClass;
// 注：このサンプルが奇妙ですが、要は範囲外の値が渡された場合に末端を示す値に置き換えています。
m_index = (index == 0 ? index : SIZE_MAX);
}
// コピーコンストラクタでは、引数で受け取ったイテレータが保持している値を複製します。
CMyClassIterator::CMyClassIterator(const CMyClassIterator& iterator)
{
m_myClass = iterator.m_myClass;
m_index = iterator.m_index;
}
このとき、位置情報を受け取る今回の場合は最初の位置（m_serial）か末端かしか状態がないので、位置情報が 0 以外で渡されたときには SIZE_MAX に置き換えています。
間接演算子の実装
今回は読み書き可能なフォワードイテレータを作成しているので、間接演算子では値のコピーではなく m_index への参照を返すようにしています。
ただし、末端を表すイテレータの場合（m_index == SIZE_MAX の場合）は m_index を書き換えられては困るので、static 宣言したダミーの変数への参照を返すようにしてみています。
int& CMyClassIterator::operator*()
{
// 末端だったとき用に返すダミーの変数です。
static int dummy;
// CMyClass で friend に指定されているので、CMyClass の private メンバ変数に直接アクセスできます。
return (m_index != SIZE_MAX ? m_myClass->m_serial : dummy);
}
加算演算子の実装
イテレータの加算演算では、イテレータが次の位置を示すように内部情報を書き換えてあげます。
今回の場合は最初の位置（m_serial）か末端かしか状態がないので、イテレータの m_index が 0 以上になったタイミングでその値を SIZE_MAX に置き換えています。
// 前置演算子 ++a では、自分自身の参照を戻り値として返します。
CMyClassIterator& CMyClassIterator::operator++();
{
m_index++;
if (m_index > 0) m_index = SIZE_MAX;
return *this;
}
// 後置演算 a++ では、値を加える前の状態をコピーしておいてそれを戻り値とします。
CMyClassIterator CMyClassIterator::operator++(int)
{
CMyClassIterator result = *this;
m_index++;
if (m_index > 0) m_index = SIZE_MAX;
return result;
}
比較演算子の実装
今回のフォワードイテレータでは、比較演算子として、位置情報が等しいか (==) と等しくないか (!=) の 2 つの演算を実装します。
比較内容は、イテレータが同じ位置を示しているかということになるので、今回の場合はまず第一に m_index が同じ値かどうかを判定します。また、同じ CMyClass から取得したイテレータであることも重要なので、それら両方を比較して判定しています。
// 扱っているクラスと位置情報のどちらかまたは両方が一致していなかを調べています。
bool CMyClassIterator::operator!=(const CMyClassIterator& iterator)
{
return this->m_myClass != iterator.m_myClass || this->m_index != iterator.m_index;
}
// 演算子 "==" の判定は、演算子 "!=" の否定を取ります。
bool CMyClassIterator::operator==(const CMyClassIterator& iterator);
{
return !(*this != iterator);
}
今回の例では、演算子 "!=" を使いまわして、演算子 "==" を実装しています。
イテレータを使ったプログラムの場合はなにかと "!=" で判定することが多いので、片方を使いまわして実装する場合はこのように "!=" を使いまわした方が効率がいいかもしれません。
CMyClass の実装
CMyClass の実装については、ここではイテレータに関するところだけ抜き出して見て行くことにします。
イテレータに関する部分としては、今回の例ではまず、CMyClassIterator を CMyClass のローカルクラスとして再定義しているところがあります。
// CMyClassIterator を CMyClass::iterator として再定義しています。
typedef CMyClassIterator iterator;
これは必ずしも必要なものではないですけど、これを記述しておくことで CMyClassIterator を CMyClass::iterator というように「どのクラスのイテレータ」かが目で見てすぐに判るようになるし、CMyClass のイテレータを使いたいときにも「このクラスの iterator」という書き方ができるので、使うときに迷うことが少なくなります。
std::vector<> や std::unordered_map<> などの標準クラスでもこのような実装になっていたので、今回の例ではそれに倣ってこのように定義してみました。
このローカルクラスの定義は、ヘッダーにこの定義が記されていれば大丈夫で、実装で何か特別なことを書く必要はありません。
あとはこの、定義したローカルクラスのイテレータを使って、最初の位置を返す begin 関数と、末端の位置を返す end 関数のそれぞれを実装していきます。
// begin 関数では、最初の位置を示すイテレータを作って返します。
CMyClass::iterator CMyClass::begin()
{
return CMyClassIterator(this, 0);
}
// end 関数では、末端位置（最後の要素の次の位置）を示すイテレータを返します。
CMyClass::iterator CMyClass::end()
{
return CMyClassIterator();
}
ここで呼び出している CMyClassIterator のコンストラクタは private で定義されていますが、CMyClassIterator の定義のところで CMyClass を friend として宣言しているので、CMyClass から呼び出すことが可能です。
ところで end 関数で返す末端の位置を示すイテレータは何かといろいろな場面で使います。
今回の end 関数の場合は、end 関数が呼ばれる度に毎回、ディフォルトコンストラクタとコピーコンストラクタが呼び出されます。
ポインタやいくつかの値をコピーする程度なら大した心配もいらないですけど、もしイテレータを作る上で大きなメモリを操作したり時間がかかる処理をしたりする場合には、あらかじめどこかに定義しておいて、スマートポインタ などを使ってイテレータ間で共用するなどの気遣いをした方がいいこともあるかもしれません。
そのような心配がある場合は、ムーブコンストラクタ を実装するだけでも、かなり負担が違ってくると思います。
実装したイテレータを使用する
このように実装したイテレータは、他の 標準的なイテレータ と同じように使えます。
例えば CMyClass のインスタンスのイテレータを取得して、最初から最後までを順次取得したい場合は、次のようなプログラムで実現できるようになりました。
CMyClass myClass;
// このように、自作クラスでもイテレータを使って順次処理を行えます。
for (CMyClass::iterator iterator = myClass.begin(); iterator != myClass.end(); ++iterator)
{
}
イテレータをサポートすると、std::for_each 関数や std::fill 関数、std::sort 関数など、STL の <algorithm> で定義されている様々な関数に渡せる値になるので、応用の幅がぐっと広がります。
その他のイテレータ
イテレータは、ひとつのクラスにいくつ実装しても問題ないので、必要に応じていろんな種類のイテレータを併設できます。
よくあるのが、内容を書き換えることのできない読み取り専用イテレータを用意して、const 指定の begin 関数や cbegin という関数を新設して取得できるようにしたり、逆順に整列されたリバースイテレータを用意して rbegin 関数で取得できるようにしたりなどです。
このようなとき、読み取り専用イテレータやリバースイテレータは、通常のイテレータとは実装方法も変わってくることが多いため、新しく例えば CMyClassReadonlyIterator クラスや CMyClassReverseIterator クラスなどを実装して、それを CMyClass::const_iterator や CMyClass::reverse_iterator として使えるように実装したりします。
[ もどる ]