技術文章>STL

イテレータを実装しよう
Nobuhide Tsuda
18-May-2009

イテレータ

イテレータ(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;
}

イテレータの実装は自由

前節のテンプレート関数定義を見ると分かるように、各種アルゴリズムは直接的にはイテレータの機能のみを利用し、 コンテナのデータ構造については感知しない。
したがって、イテレータとして要求されるインタフェースを備えていれば、イテレータの実装は自由である。
イテレータオブジェクトがデータ群またはそれ相当のものを内臓していたり、 イテレータオブジェクトが他のイテレータオブジェクトを参照していてもよい。

自前のクラスにイテレータを実装しよう

利点:

イテレータ実装方法

  1. 必要なメソッドを実装する:
    • コンストラクタ、デストラクタ
    • operator*()  // 参照外し(dereference)
    • operator++()  // イテレータを進める
    • operator!=()  // 比較演算子
    • .....
  2. 特性(traits)を指定する:
      std::iterator を public 継承し、カテゴリとデータタイプ等を指定する

実装例1: (データ内臓型)乱数生成器

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";

実装例2:行単位イテレータ
文字単位イテレータから(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 を利用する

まとめ

自前のクラスにイテレータを実装することで、インタフェースを標準化し、 柔軟性・再利用性を高めよう!
アダプタ・イテレータを実装することで、仮想的なデータ構造を構築することも可能だ。