STL スタイルのイテレータを実装し、よくある落とし穴を回避するにはどうすればよいでしょうか? 質問する

STL スタイルのイテレータを実装し、よくある落とし穴を回避するにはどうすればよいでしょうか? 質問する

STL スタイルのランダム アクセス イテレータを提供したいコレクションを作成しました。イテレータの実装例を探しましたが、見つかりませんでした。演算子の const オーバーロードが必要であることは知っています[]*イテレータが「STL スタイル」であるための要件は何ですか。また、回避すべきその他の落とし穴は何ですか (ある場合)。

追加コンテキスト: これはライブラリ用であり、本当に必要な場合を除いて、これへの依存関係を導入したくありません。同じコンパイラで C++03 と C++11 間のバイナリ互換性を提供できるように、独自のコレクションを作成します (したがって、おそらく壊れる STL はありません)。

ベストアンサー1

https://cplusplus.com/reference/iterator/C++11 標準の § 24.2.2 の仕様を詳しく説明した便利なチャートがあります。基本的に、イテレータには有効な操作を記述するタグがあり、タグには階層があります。以下は純粋にシンボル的なものであり、これらのクラスは実際には存在しません。

iterator {
    iterator(const iterator&);
    ~iterator();
    iterator& operator=(const iterator&);
    iterator& operator++(); //prefix increment
    reference operator*() const;
    friend void swap(iterator& lhs, iterator& rhs); //C++11 I think
};

input_iterator : public virtual iterator {
    iterator operator++(int); //postfix increment
    value_type operator*() const;
    pointer operator->() const;
    friend bool operator==(const iterator&, const iterator&);
    friend bool operator!=(const iterator&, const iterator&); 
};
//once an input iterator has been dereferenced, it is 
//undefined to dereference one before that.

output_iterator : public virtual iterator {
    reference operator*() const;
    iterator operator++(int); //postfix increment
};
//dereferences may only be on the left side of an assignment
//once an output iterator has been dereferenced, it is 
//undefined to dereference one before that.

forward_iterator : input_iterator, output_iterator {
    forward_iterator();
};
//multiple passes allowed

bidirectional_iterator : forward_iterator {
    iterator& operator--(); //prefix decrement
    iterator operator--(int); //postfix decrement
};

random_access_iterator : bidirectional_iterator {
    friend bool operator<(const iterator&, const iterator&);
    friend bool operator>(const iterator&, const iterator&);
    friend bool operator<=(const iterator&, const iterator&);
    friend bool operator>=(const iterator&, const iterator&);

    iterator& operator+=(size_type);
    friend iterator operator+(const iterator&, size_type);
    friend iterator operator+(size_type, const iterator&);
    iterator& operator-=(size_type);  
    friend iterator operator-(const iterator&, size_type);
    friend difference_type operator-(iterator, iterator);

    reference operator[](size_type) const;
};

contiguous_iterator : random_access_iterator { //C++17
}; //elements are stored contiguously in memory.

std::iterator_traits<youriterator>を特化するか、イテレータ自体に同じ typedef を配置するか、 (これらの typedef を持つ) から継承することができますstd::iterator。名前空間内の変更を避け、読みやすくするために、私は 2 番目のオプションを好みますstdが、ほとんどの人は から継承しますstd::iterator

struct std::iterator_traits<youriterator> {        
    typedef ???? difference_type; //almost always ptrdiff_t
    typedef ???? value_type; //almost always T
    typedef ???? reference; //almost always T& or const T&
    typedef ???? pointer; //almost always T* or const T*
    typedef ???? iterator_category;  //usually std::forward_iterator_tag or similar
};

iterator_category は、イテレータが満たす要件に応じて、、、、、のいずれかになることに注意してください。イテレータによっては、、、、も特化するように選択できますstd::input_iterator_tagが、これが必要になることはほとんどありません。非常にまれなケースでは、およびを特化する必要がある場合があります。std::output_iterator_tagstd::forward_iterator_tagstd::bidirectional_iterator_tagstd::random_access_iterator_tagstd::nextstd::prevstd::advancestd::distancestd::beginstd::end

コンテナにはおそらく も必要ですconst_iterator。これは、 に似た定数データへの (おそらく変更可能な) イテレータですiteratorが、 から暗黙的に構築可能でiterator、ユーザーがデータを変更できない必要があります。その内部ポインタは非定数データへのポインタであり、コードの重複を最小限に抑えるためにiteratorから継承するのが一般的です。const_iterator

私の投稿独自の STL コンテナの作成より完全なコンテナ/イテレータのプロトタイプを備えています。

おすすめ記事