イテレータ自作ガイド

イテレータを自作するのは面倒臭い！！
しかも調べても何を実装すればいいのかいまいちわからない！！
そんなときに見る備忘録的なメモ的なｻﾑｼﾝｸﾞ。
情報量が多くて変なミスしてるかも。
間違い等気づいた点がございましたらコメント頂けたら嬉しいです。

まるが付いているのは左に同じという意味です。
何もないのは実装しないという意味です。

	input iterator	output iterator	forward iterator	bidirectional iterator	random access iterator
共通			itr()	○	○
	itr(const itr&)	○	○	○	○
	itr& operator=(const itr&)	○	○	○	○
	~itr() noexcept	○	○	○	○
	void swap(itr&, itr&)	○	○	○	○
読取	unspecified operator*() const		const reference operator*() const	○	○
			pointer operator->() const	○	○
	bool operator==(const itr&, const itr&)		○	○	○
	bool operator!=(const itr&, const itr&)		○	○	○
書込		reference operator*() const	※	※	※
前進	itr& operator++()	○	○	○	○
	itr operator++(int)	○	○	○	○
後退				itr& operator--()	○
				itr operator--(int)	○
ランダムアクセス					reference operator[](difference_type)
					itr& operator+=(difference_type)
					itr operator+(const itr&, difference_type)
					itr operator+(difference_type, const itr&)
					itr& operator-=(difference_type)
					itr operator-(const itr&, difference_type)
					difference_type operator-(const itr&, const itr&)
					bool operator>(const itr&)
					bool operator>=(const itr&)
					bool operator<(const itr&)
					bool operator<=(const itr&)

示されている型について

itrはそのイテレータの型です。
value_typeはイテレータの管理する型です。
pointerはイテレータが管理する型のポインタだとみなす型です。通常はvalue_type*です。
referenceはイテレータが管理する型の参照型とみなす型です。通常はvalue_type&です。
difference_typeはポインタ間の距離を表すのに十分な符号付き整数型です。通常はstd::ptrdiff_tが使われます。

unspecifiedは指定なしという意味です。何でもOK。
これらの型はイテレータを作成する場合は通常std::iteratorを継承するときに指定してあげます。
さらに、std::iteratorでtypedefされるこれらの型を再び定義してあげます。

using iterator_category = typename base::iterator_category;
using value_type = typename base::value_type;
using difference_type = typename base::difference_type;
using pointer = typename base::pointer;
using reference = typename base::reference;

std::iteratorを継承しない（できない）場合は、ハードコートするしかないですね。

using iterator_category = std::random_access_iterator_tag;
using value_type = Ty;
using difference_type = std::ptrdiff_t;
using pointer = Ty*;
using reference = Ty&;

これらの型定義がないと、std::iterator_traitsで情報が得られなくなってしまいます。
イテレータのカテゴリによっては不必要な場合もありますが、わたしは全てのイテレータに全ての型定義をすることをおすすめします。

書き込みについて

※をつけてある書き込みについては、イテレータの指す値がmutableな場合に限り可能になります。その場合は、outputイテレータの要求も満たさなければなりません。

戻り値について

実は、unspecifiedとなってなくても殆どの関数がそれぞれ条件（デリファレンス演算子の戻り値はinputの場合はvalue_typeへ暗黙に変換できる、outputの場合はvalue_typeを書き込むことができるなど）を満たす限りで戻り値を自由に設定できます。
おそらく通常は図のようになりますが、std::vector< bool >::iteratorなど特殊な例もあります。（悪名高いstd::vector< bool >ですが名前以外は素晴らしいデータ構造です。）

二項演算子・swapなどの関数について

これらはフレンド関数かグローバル関数で定義することをおすすめします。

おまけ

最後になりましたが、random_access_iteratorを例にひとつ書いてみたいと思います。関数は宣言だけで定義はありませんが、それでもかなり大きくなります。

// rand_acs_itr
template< class Ty >
class itr : public std::iterator< std::random_access_iterator_tag,
                                  Ty, std::ptrdiff_t, Ty*, Ty& >
{
  using base = std::iterator< std::random_access_iterator_tag, Ty, std::ptrdiff_t, Ty*, Ty& >;
public:
  using iterator_category = typename base::iterator_category;
  using value_type = typename base::value_type;
  using difference_type = typename base::difference_type;
  using pointer = typename base::pointer;
  using reference = typename base::reference;

  itr();
  itr(const itr&);
  itr& operator=(const itr&);
  ~itr() noexcept;

  reference operator*() const;
  pointer operator->() const;
  reference operator[](difference_type) const;
  itr& operator++();
  itr operator++(int);
  itr& operator--();
  itr operator--(int);
  itr& operator+=(difference_type);
  itr& operator-=(difference_type);

  friend itr operator+(const itr&, difference_type);
  friend itr operator+(difference_type, const itr&);
  friend itr operator-(const itr&, difference_type);
  friend difference_type operator-(const itr&, const itr&);

  friend void swap(const itr&, const itr&);

  friend bool operator==(const itr&, const itr&);
  friend bool operator!=(const itr&, const itr&);
  friend bool operator<(const itr&, const itr&);
  friend bool operator<=(const itr&, const itr&);
  friend bool operator>(const itr&, const itr&);
  friend bool operator>=(const itr&, const itr&);
};

読み書き可能なランダムイテレータです。
これより高機能なイテレータはC++14時点ではありませんので(C++17で出るみたいです)、これから機能を削ったり多少の変更を加えればインターフェースは出来上がることになります。
読み込み専用のconst_iteratorを作る場合は、itr< const Ty >としてあげましょう。
reverse_iteratorを作る場合は、std::reverse_iterator< itr< Ty > >とするだけで大丈夫です。