STLのコンテナを操作するための共通の手段としてiteratorというものがある。とても便利なこのiteratorを自分で実装したことはあるだろうか。iteratorの要件は規格書に書いてあるので、それさえ満たせばどんなイテレータもiteratorを名乗っていいことになる。
この記事ではごく簡単なイテレータもどきの実装を通してイテレータに必要なメソッドや演算子の実装方法を紹介する。また、おまけとして、一番使う頻度が高くなりそうな他のイテレータをそのまま利用する方法も紹介する。
自分のクラスにイテレータがあると何が良いのか
algorithmヘッダのことを知っているだろうか。あそこにある関数はほとんどすべてイテレータを引数に取る。逆に言えばイテレータさえ準備できればalgorithmヘッダの関数を自分で書いたクラスに適用できるということだ。std::findやstd::partitionのような便利関数を使って大学の課題をスラスラ終わらせることができるだろう。
範囲for文もイテレータを使う構文の一つだ。
std::initializer_list<int> il{1, 2, 3}; for(auto i : il) { std::cout << i << ' '; }
簡単な構文でリストの中身を走査できる範囲for文はC++11で導入された。これを知ってしまえばもうC-likeな冗長なfor文には戻れないはずだ。範囲for文はシンタックスシュガーだ。N4810の8.5.4ではfor (for-range-declaration : for-range-initializer)statementは以下と同等であると定義されている*1。
{
auto&& range = for-range-initializer;
auto begin = begin-expr; // range.begin()やstd::begin(range)など
auto end = end-expr; // range.end()やstd::end(range)など
for ( ;begin!=end; ++begin) {
for-range-declaration= *begin;
statement
}
}
イテレータもどき
簡単に実装できるのはLegacyInputputIteratorだ。この要件は規格書ドラフトのN4810の23.3.5.3に記述されている。規格書での表記はCpp17InputIteratorだが、つまりC++20より前の古いイテレータの要件だ *2。ここではcppreferenceの表記に合わせてLegacyInputIteratorという表記を用いる。
この章では二つの整数mとnの間を反復するイテレータを持つクラスstepを実装してイテレータの実装方法の概要を説明する。下に示すような文を用いて整数を取り出すことが目的だ。
for(auto i : step(m, n)) { std::cout << i << ' '; }
イテレータを実装する前にクラスstepについて考えよう。クラスstepはmからnまでを反復するイテレータを提供するだけのクラスだ。保持すべき値はmとn (ただし分かりやすさのために名前はfirstとlastになる)。用意すべきメソッドは、イテレータを取得するためのbegin()とend()だ。簡単だな。
template<class Int> class step{ Int first_; Int last_; public: step(Int first, Int last) : first_{ first } , last_{ last } {} class iterator; iterator begin() const noexcept; iterator end() const noexcept; };
今はまだiteratorがどのようなものになるかは分からない。これから考える。
firstとlastが等しくない限り、iteratorはbegin()とend()が異なるものでなくてはならない。例えば、stepのコンストラクタに、0uとstd::numeric_limits<unsigned int>::max()が渡された時でも正しく動く必要がある。end()はlast_ + 1の値を指すiteratorを返すだけでは正しく動かない。iteratorは自分が指す値に加え、last_のコピー、そして無効値を表現するための特殊な状態を持つ必要がある。
template<class Int> class step{ Int first_; Int last_; public: step(Int first, Int last) : first_{ first } , last_{ last } {} class iterator { Int value_; Int last_; bool is_valid_; public: using value_type = Int; using reference = const Int&; using pointer = const Int*; using iterator_category = std::input_iterator_tag; iterator(Int value, Int last) : value_(value) , last_(last) , is_valid_(true) {} iterator() : is_valid_(false) {} // この演算子は前置インクリメント iterator& operator++() { is_valid_ = value_++ != last_; return *this; } // この演算子は後置インクリメント iterator operator++(int) { auto cp = *this; ++(*this); return cp; } reference operator*() const noexcept { return value_; } pointer operator->() const noexcept { return &value_; } friend bool operator==(const iterator& a, const iterator& b) noexcept { return (!a.is_valid_ && !b.is_valid_) || (a.is_valid_ && b.is_valid_ && a.value_ == b.value_); } friend bool operator!=(const iterator& a, const iterator& b) noexcept { return !(a == b); } }; iterator begin() const noexcept { return iterator{first_, last_}; } iterator end() const noexcept { return iterator{}; } };
たったこれだけでLegacyInputIterator実装完了だ。範囲for文で好きな回数ループできるようになった。例えば10回ループしたいならfor(auto i : step(1, 10)) {}と書く。なんども言うが、イテレータに対してどのような式が有効でなくてはならないかは規格書で定められている。何を実装すればいいのかわからなくなったときは規格書を参照してほしい。規格書が難しければ日本語に訳されているcppreferenceがよい。
イテレータに必要な機能は理解できただろうか。しかし、それらはiterator_categoryによって若干異なってくる。他のカテゴリーのイテレータを作るときは都度規格書を参照してほしい。
他のクラスのイテレータをそのまま使う (おまけ)
例えばSTLの何かのコンテナを保持しているクラスで、そのコンテナの各要素に対して外部からアクセスしたいとき自分でイテレータを作るのは馬鹿げている。
class container { std::vector<int> v_; public: container() : v_ (10, 1) {} using iterator = std::vector<int>::iterator; iterator begin() { return v_.begin(); } iterator end() { return v_.end(); } };
