イテレータ
イテレータ（iterator）は C++ STL（Standard Template Library）の中核を成す概念のひとつで、ポインタの機能を抽象化したものである。
参照外し（dereference）、インクリメント・デクリメント、比較などのポインタ同等の機能を持つ。
STLの各コンテナには、それ専用のイテレータクラスが定義されており、 イテレータオブジェクトの生成はコンテナの begin(), end() メソッドなどで行う。
コンテナの最大要素を取得する例：
vector<int> cntn;
..... // cntn にデータを格納する処理
int val = MIN_INT;
for(vector<int>::iterator itr = cntn.begin(); itr != cntn.end(); ++itr)
val = max(val, *itr);
イテレータは、下図の様に、各種アルゴリズムと各種コンテナの仲介を行う。
各アルゴリズムはイテレータを介してコンテナのデータにアクセスするので、コンテナの構造等を知る必要がない。
先の例をテンプレート関数化したもの：
template<typename Iterator, typename T>
T get_max_value(Iterator first, Iterator last, T val)
{
while( first != last ) {
val = max(val, *first);
++first;
}
return val;
}
イテレータの実装は自由
前節のテンプレート関数定義を見ると分かるように、各種アルゴリズムは直接的にはイテレータの機能のみを利用し、
コンテナのデータ構造については感知しない。
したがって、イテレータとして要求されるインタフェースを備えていれば、イテレータの実装は自由である。
イテレータオブジェクトがデータ群またはそれ相当のものを内臓していたり、
イテレータオブジェクトが他のイテレータオブジェクトを参照していてもよい。
自前のクラスにイテレータを実装しよう
利点：
- Myクラスに対して直接的に、豊富なアルゴリズムが利用可能になる
- インタフェースが標準化され、プログラムの柔軟性やMyクラスの再利用性が高まる
イテレータ実装方法
- 必要なメソッドを実装する：
- コンストラクタ、デストラクタ
- operator*() // 参照外し（dereference）
- operator++() // イテレータを進める
- operator!=() // 比較演算子
- .....
- 特性（traits）を指定する：
std::iterator を public 継承し、カテゴリとデータタイプ等を指定する
実装例１： （データ内臓型）乱数生成器
template< typename T>
class CTestIterator : public std::iterator<std::forward_iterator_tag, T>
{
int m_counter; // イテレータを区別するためのカウンタ
T m_value; // 生成した乱数の値 [0, 100)
public:
CTestIterator(int counter = 0) : m_counter(counter), m_value(0) { gen_rand(); };
public:
T operator*() const { return m_value; }
CTestIterator &operator++() { gen_rand(); ++m_counter; return *this; }
bool operator!=(const CTestIterator &x) const { return m_counter != x.m_counter; }
public:
int get_counter() const { return m_counter; };
protected:
void gen_rand() { m_value = static_cast<T>(rand() % 100); }
};
上記イテレータの使用例：
CTestIterator<int> first(0);
CTestIterator<int> last(1000); // 1000回試行
CTestIterator<int> itr = std::find(first, last, 7); // 7が出るまで繰り返す
if( itr != last )
cout << "val = " << static_cast<int>(*itr) << " counter = " << itr.get_counter() << endl;
else
cout << "not found.\n";
実装例２：行単位イテレータ
文字単位イテレータから（CRLF/CR/LF区切りの）行単位イテレータを生成
class const_line_iterator : public std::iterator<std::forward_iterator_tag, std::string>
{
typedef vector<char>::const_iterator char_iterator;
char_iterator m_begin; // 行先頭へのイテレータ
char_iterator m_next; // 行末の次の文字
char_iterator m_end; // 行全体の末尾の次
public:
const_line_iterator(char_iterator itr, char_iterator end) : m_begin(itr), m_end(end) { set_next(); }
public:
/*const*/ string operator*() const { return string(m_begin, m_next); }
const_line_iterator &operator++()
{
if( m_begin != m_end ) {
m_begin = m_next;
set_next();
}
return *this;
}
bool operator==(const const_line_iterator &x) const { return m_begin == x.m_begin; }
bool operator!=(const const_line_iterator &x) const { return m_begin != x.m_begin; }
protected:
void set_next()
{
char ch = '\0'; // ひとつ前の文字
for(m_next = m_begin; ; ) {
if( m_next == m_end || ch == '\n' ) return;
if( ch == '\r' ) {
if( *m_next == '\n' ) ++m_next;
return;
}
ch = *m_next;
++m_next;
}
}
};
上記イテレータの使用例：
// 各行の内容を行番号付きで表示
void printLine(const vector<char> &v)
{
int lineNum = 0;
const_line_iterator itr(v.begin(), v.end());
const_line_iterator iend(v.end(), v.end());
for( ;itr != iend; ++itr )
cout << ++lineNum << ": " << (*itr).c_str() << "\n";
}
// 最大行長を返す
int getMaxSize(const vector<char> &v)
{
size_t maxSize = 0;
const_line_iterator itr(v.begin(), v.end());
const_line_iterator iend(v.end(), v.end());
for( ;itr != iend; ++itr )
maxSize = max(maxSize, (*itr).size());
return maxSize;
}
// std::find() を用いて指定文字列の行を検索
void main()
{
vector<int> v;
..... // v にデータを格納する処理
const_line_iterator first(v.begin(), v.end());
const_line_iterator last(v.end(), v.end());
const_line_iterator itr = std::find(first, last, string("12345\r\n"));
}
その他の実装方法：
boost::iterator_facade を利用する
まとめ
自前のクラスにイテレータを実装することで、インタフェースを標準化し、
柔軟性・再利用性を高めよう！
アダプタ・イテレータを実装することで、仮想的なデータ構造を構築することも可能だ。