反復子を自分で作ってみる

ども・・・・・・・・・・・・和佐田雅史です。
今回はイテレータについてです。

イテレータと言うのは反復子の事で、listやmapコンテナをfor文でポインタによる参照( のようなもの )を行いたい時に使います。

std::list< T >::iterator it = List.begin();

と言う感じですね。
しかし、自分でコンテナを作った時にiteratorはどう作ればよいでしょうか？

基本的には定義したコンテナクラスの中にローカルクラスとして定義するのが一般的です。

template< class T > class Freelist
{
// 実装

// ローカルクラスとして定義
class iterator : public std::iterator<.....>
};

ですが一々コンテナを作る時に定義するのははっきり言ってめんどくさいのでtemplateで作っておくと便利です。

//============================================
// コンテナ作成時の反復子
//
//
//
//============================================

#ifndef _ITERATOR_HPP_
#define _ITERATOR_HPP_

#include <iterator>

namespace Alumina
{

// friendの為の仮定義
template< typename Type , typename value_type > class iterator;
template< typename Type , typename value_type > class const_iterator;

//=============================================
// 通常iterator
//
//
//=============================================
template< typename Type , typename value_type > class iterator : public std::iterator<std::bidirectional_iterator_tag, value_type, void>
{
public:
 iterator() : _ptr(0) {}

 iterator(Type* ptr) : _ptr(ptr){}

 // ジェネリック要素へのアクセス
 Type& operator*() const {return *_ptr;}
 Type* operator->() const {return _ptr;}

 // 真偽判定
 bool operator==(const iterator& rhs) const {return _ptr == rhs._ptr;}
 bool operator!=(const iterator& rhs) const {return _ptr != rhs._ptr;}

//=============================================
//
// 演算子によるポインタ演算
//
//=============================================
 iterator& operator++() {_ptr = _ptr->_next; return *this;}
 iterator& operator--() {_ptr = _ptr->_prev; return *this;}
 iterator operator++(int i) { iterator temp = *this; ++*this; return temp; }
 iterator operator--(int i) { iterator temp = *this; --*this; return temp; }

protected:

 // メンバ
 Type* _ptr;

 friend class Type;
 friend class const_iterator;
};

//===============================================
// const_iterator
//
//
//===============================================
template< typename Type , typename value_type > class const_iterator : public std::iterator<std::bidirectional_iterator_tag, value_type, void>
{
public:
 const_iterator() : _ptr(0){}
 const_iterator(const iterator& it) : _ptr(it._ptr) {}
 const_iterator(const Type* ptr) : _ptr(ptr) {}

 const Type& operator*() const {return *_ptr;}
 const Type* operator->() const {return _ptr;}

 bool operator==(const const_iterator& rhs) const {return _ptr == rhs._ptr;}
 bool operator!=(const const_iterator& rhs) const {return _ptr != rhs._ptr;}

 //=============================================
 //
 // 演算子によるポインタ演算
 //
 //=============================================
 
 const_iterator& operator++() {_ptr = _ptr->_next; return *this;}
 const_iterator& operator--() {_ptr = _ptr->_prev; return *this;}
 const_iterator operator++(int i) { const_iterator temp = *this; ++*this; return temp; }
 const_iterator operator--(int i) { const_iterator temp = *this; --*this; return temp; }

protected:
 const Type* _ptr;

 friend class Type;
};

}
#endif

長くなりましたが、使用例を以下に示します。

// LISTNODE 型を管理するリストコンテナ
template < typename LISTNODE , template< class > class Interfase = ListType > class FreeList
{
public:

 // 実装インターフェース設定
 typedef Interfase< LISTNODE > LIST;

 // それに伴った反復子を定義
 typedef Alumina::iterator< LIST , LIST > iterator;
 typedef Alumina::const_iterator< LIST , LIST > const_iterator;

.........................

};

このように定義するだけでiteratorが使えるようになります。
便利ですね。

それではお疲れ様でした。