Go to Qiita Advent Calendar 2024 Top
LoginSignup
31
24

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

C++Advent Calendar 2022

Day 4
@tomolatoon

C++20のイテレータ事情

Last updated at Posted at 2022-12-03

0. C++ Advent Calendar 2022 4日目です

3日目 | std::optional のモナド的操作 by lewisacid さん
5日目 | ［C++］地に足のついた範囲for文 - 地面を見下ろす少年の足蹴にされる私 by onihusube さん

どうも、tomolatoonです。

この記事を書き終える少し前にはWoven Planetさん主催でC++ Meetupが開催され、TwitterのC++コミュニティに生息していらっしゃる方々とご挨拶させていただいたり、個人的な話だとcpprefjpやOpenSiv3DにPull Request出したりと色々ありましたが、もう年末。Advent Calendarの季節になりました。（でも今年は去年にも増して過疎ってますね...）

ところで、C++20では<ranges>が登場し、C++での配列やコンテナ（std::vector、std::string、etc）など「範囲」に対する処理がイテレータペアだけでなく、「範囲」そのものを使って行えるようになりました。

しかし、Ranges は結局のところイテレータペアのラッパーでしかなく、実際の処理はイテレータに殆どぶん投げられています。そのイテレータも、C++20になってそこそこ大きな変更が入りました。というわけn番煎じではありますが、この記事ではイテレータの解説をしようと思います。最後まで読めばあなたもイテレータを作れるはず！（？）

0.1. 記事構成

この記事は

  1. イテレータ概説（入門、イテレータを知らない人向け）
  2. イテレータカテゴリ（中級、イテレータを使う人向け）
  3. イテレータコンセプト（上級、イテレータの実装をする人向け）

で構成されています。必要な部分を必要なだけ読むことをおすすめします。

0.2. 注意

この記事でのコードは全てC++20を前提として書かれています。C++17以前で動かすにはコードを変更する必要があったり、そもそも無理なコードも多くありますので、ご注意ください。（ごく一部C++23が必要な部分が生じたので、その部分は明記しています）

1. イテレータ概説

イテレータは日本語では「反復子」とも呼ばれ、多くの場合、配列などのコンテナの要素全てにアクセス（反復）するために使用されるものです。C++においては組み込み配列に対するポインタが基本となっており、イテレータは 「ポインタ」と、「コンテナ等に実装されているクラス」 を指します。

ここからは、std::vector<int>::iteratorを例にして、このイテレータができることを紹介することでイテレータの概説をしていきます。（細かいことは §2 で扱いますが、std::vector<int>::iteratorは一番出来ることが多いカテゴリに属するイテレータです）

1.1. イテレータの取得と値の取得

イテレータを取得するときには、std::ranges::begin（C++17以前はstd::begin）を使います。取得できるイテレータの型はstd::ranges::iterator_t<R>を使用して取得できますが、autoで推論してもらうほうが楽です。

イテレータの取得と値の取得
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>

int main()
{
	std::vector<int> vec = {9, 8, 7};

	// vec の先頭を指すイテレータを取得
	auto                                      it = std::ranges::begin(vec);
	std::ranges::iterator_t<std::vector<int>> _  = std::ranges::begin(vec);

	// 間接参照をして値（今回は int& ですが）を取得
	std::cout << *it << std::endl; // 9
}
出力
9

1.1.1. std::beginの使い方

深いことは端折りますが、std::beginは 「カスタマイゼーションポイント」と呼ばれる「関数」で、使い方が複雑です。それでもC++17以前では使わないといけないので、使い方を説明しておきます。次の2点を気をつける必要があります。

  • 呼び出す前にusing宣言（using std::begin;）をすること
  • 呼び出す時に非修飾名（std::beginではなく、begin）で使用すること

そのため、使う際はこのような風貌になります。

std::beginの使い方
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>

int main()
{
	std::vector<int> vec = {9, 8, 7};

	using std::begin;
	auto it = begin(vec);
}

反して、std::ranges::beginは「カスタマイゼーションポイントオブジェクト」と呼ばれる「オブジェクト」で、単純にstd::ranges::beginと使用します。

なお、std::beginの他に、std::endとstd::swap（後で正体がわかります）も同じ使い方をする必要があります。（C++20以降はstd::ranges::begin/end/swapを使ってください）

1.2. イテレータの進行・後退

イテレータが指す場所を移動するときには、インクリメントやデクリメント、加算減算が使用できます。（但し、イテレータが属するカテゴリによっては使用できないものがあります）

イテレータの進行・後退
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>

int main()
{
	std::vector<int> vec = {9, 8, 7};
	auto             it  = std::ranges::begin(vec);

	std::cout << *it << std::endl; // 9

	// 1つ進める
	++it;

	std::cout << *it << std::endl; // 8

	// 1つ戻す
	--it;

	std::cout << *it << std::endl; // 9

	// 2つ進める
	it += 2;

	std::cout << *it << std::endl; // 7

	// 2つ戻す
	it -= 2;

	std::cout << *it << std::endl; // 9
}
出力
9
8
9
7
9

1.2.1. ユーティリティで進行・後退

イテレータの進行・後退を行うstd::ranges::advance（C++17以前はstd::advance）が存在しています。こちらに関しては、イテレータが加算減算をサポートしていなかったとしても、インクリメント/デクリメントを繰り返すことでイテレータの進行・後退を行ってくれます。

advance
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>

int main()
{
	std::vector<int> vec = {9, 8, 7};
	auto             it  = std::ranges::begin(vec);

	std::cout << *it << std::endl; // 9

	// 1つ進める
	std::ranges::advance(it, 1);

	std::cout << *it << std::endl; // 8

	// 1つ戻す（負整数は後退として解釈される）
	std::ranges::advance(it, -1);

	std::cout << *it << std::endl; // 9

	// 2つ進める
	std::ranges::advance(it, 2);

	std::cout << *it << std::endl; // 7

	// 2つ戻す
	std::ranges::advance(it, -2);

	std::cout << *it << std::endl; // 9
}
出力
9
8
9
7
9

1.2.2. ユーティリティをもうすこし

ここまで加算減算とは言ってきましたが、複合代入の方しか示していなかったので、通常の加算減算について触れていなかったので、そちらも一応触れておきます。複合代入に対応するのはstd::ranges::advanceでしたが、通常の加算減算に対応するのはstd::ranges::prevとstd::ranges::nextがあります。（advanceと同様、加算減算が実装されていないイテレータに対しては、インクリメント/デクリメントを繰り返して操作を行います）

prevとnext
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>

int main()
{
	std::vector<int> vec = {9, 8, 7};
	auto             it  = std::ranges::begin(vec);

	// 説明の都合上先に進めておきます
	++it;

	std::cout << *it << std::endl; // 8

	// `it`のコピーを1つ進めたイテレータが帰ってくる
	std::cout << *(it + 1) << std::endl; // 7

	// `it`のコピーを1つ戻したイテレータが帰ってくる
	std::cout << *(it - 1) << std::endl; // 9

	// `it + 1`と同じ
	std::cout << *next(it, 1) << std::endl; // 7

	// `it - 1`と同じ
	std::cout << *prev(it, 1) << std::endl; // 9
}
出力
8
7
9
7
9

1.3. 範囲を表現

イテレータは単独では「ある要素1つ」を指すことしか出来ませんが、2つをペアにして始まりと終わりを表現することで「範囲」を表す事ができるようになります。その時に始まりを表すものはそのままイテレータと呼びますが、終わりを表すものはセンチネルと呼び分けます。

次の画像のように、イテレータもセンチネルも 「範囲」の区切りを表現していると考える事ができます。実際、イテレータは「範囲の先頭の要素」を指しますが、センチネルは「範囲の末尾の次の要素」を指します。

iterator_sentinel_range.png
図: 筆者作成（CC-BY）

便宜上、この後は「イテレータとセンチネルが指す要素のインデックス」で範囲を表示することにします。例えば、上の画像の場合は[0, 3)として表示します。

1.3.1. センチネルの取得・使用

コンテナ全体を「範囲」とした時のセンチネルは、std::ranges::end（C++17以前はstd::end）で取得することが出来ます。これによって取得できるセンチネルの型はstd::ranges::sentinel_t<R>を使用して取得できますが、autoの方がいいです。

センチネルの取得・使用
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>

int main()
{
	// bool値をtrue/falseで表示するためのフラグ
	std::cout << std::boolalpha;

	std::vector<int> vec = {9, 8, 7};

	// vec の末端の要素の次の要素を指していると考えられるセンチネルを取得
	auto                                      sen = std::ranges::end(vec);
	std::ranges::sentinel_t<std::vector<int>> _   = std::ranges::end(vec);

	// イテレータと等値比較するのに使用する
	std::cout << (std::ranges::begin(vec) != sen) << std::endl;
}
出力
true

1.3.2. 補: イテレータとセンチネルの関係

詳しくは §2 で説明しますが、イテレータが属すカテゴリやイテレータの供給元の「範囲」によって、センチネルの実態は異なります1。標準ライブラリのコンテナの場合はイテレータとセンチネルは同じ型のオブジェクトを使用しています。

というわけで、std::vector<T>の場合はイテレータとセンチネルは同じ型のオブジェクトを使用しているので、イテレータの位置を動かすことによってセンチネルを取得することも可能です。

更に、コンテナからイテレータ/センチネルを取得する際には、メンバ関数begin/endを使用することも出来ます。（というより、std::ranges::begin/endもそこから取得することも出来るようになっています2）

イテレータとセンチネルの関係
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>

int main()
{
	std::vector<int> vec = {9, 8, 7};

	// std::ranges::begin(vec) と同等
	auto begin = vec.begin();

	// std::ranges::end(vec) と同等
	auto end = vec.end();

	// std::vector<T> のイテレータとセンチネルの型は同じ
	//  static_assert(e)    : 式 e が false の時、コンパイルエラーを起こす
	//  decltype(e)         : 式 e の型を取得する
	//  std::is_same_v<T, U>: 型 T と型 U が cv修飾含めて同じ型かを bool 値で返す
	static_assert(std::is_same_v<decltype(begin), decltype(end)>);
}

1.3.3. 「範囲」の要素数（サイズ）

配列やコンテナの要素数はstd::ranges::size（符号付き整数で取得する場合はstd::ranges::ssize）で取得できますが、イテレータとセンチネルによって表現されている「範囲」はstd::ranges::distanceで取得することが出来ます。（C++17以前はstd::size、std::distanceを使用）

「範囲」の要素数
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>

int main()
{
	// bool値をtrue/falseで表示するためのフラグ
	std::cout << std::boolalpha;

	std::vector<int> vec{9, 8, 7};

	// true（コンテナ全体の要素数を2通りで求めている）
	std::cout << (std::ranges::size(vec) == std::ranges::distance(vec.begin(), vec.end())) << std::endl;
}

1.3.4. 範囲をfor文で走査する

イテレータとセンチネルのペアで、コンテナ全体でも、コンテナの一部分でも「範囲」としての表現が出来たので、for文と組み合わせることで「範囲」を走査（「範囲」内の要素全てにアクセス）する事が出来ます。

「範囲」を走査する
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>

int main()
{
	std::vector<int> vec = {9, 8, 7};

	// [0, 3) （コンテナ全体）
	{
		auto begin = std::ranges::begin(vec);
		auto end   = std::ranges::end(vec);
		for (; begin != end; ++begin)
		{
			std::cout << *begin << std::endl;
		}
	}

	std::cout << std::endl;

	// [1, 3) （インデックス1 以降が含まれる）
	{
		auto begin = std::ranges::begin(vec) + 1;
		auto end   = std::ranges::end(vec);
		for (; begin != end; ++begin)
		{
			std::cout << *begin << std::endl;
		}
	}

	std::cout << std::endl;
	
	// [1, 2) （インデックス1 のみが含まれる）
	{
		auto begin = std::ranges::begin(vec) + 1;
		auto end   = std::ranges::begin(vec) + 2;
		for (; begin != end; ++begin)
		{
			std::cout << *begin << std::endl;
		}
	}
}
出力
9
8
7

8
7

8

1.3.5. 範囲for文

コンテナ全体を走査する時は、範囲（ベースの）for文を使用するとより簡潔に書くことが出来ます。（イテレータも同時に取得したい場合はすこしコードを変える必要がありますが...）

範囲for文
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>

int main()
{
	std::vector<int> vec = {9, 8, 7};

	for (auto e : vec)
	{
		std::cout << e << std::endl;
	}
}
出力
9
8
7

1.3.5.1. 範囲for文の展開

範囲for文がやっていることは、イテレータとセンチネルによって行っていることと全く変わりありません。範囲for文に渡したコンテナがvectorの場合は、次のようになります。展開後はイテレータとセンチネルで処理されるのがわかるかと思います。

範囲for文の展開
// 展開前
for (auto e : vec)
{
    std::cout << e << std::endl;
}

// 展開後
{
  auto && __range = vec;

  for (auto __begin = __range.begin(), __end = __range.end(); __begin != __end; ++__begin) {
    auto e = *__begin;

    std::cout << e << std::endl;
  }
}

1.3.5.2. 注意

本題とは外れますが、auto eの部分によって、コンテナの要素に変更を加えられるかは異なる（型推論のautoは、そのままでは参照に推論されない）ので注意してください。

autoの部分 要素への参照か コンテナに変更が出来るか
auto No No
auto& Yes Yes
const auto& Yes No
auto&& Yes Yes
コンテナに変更は加えられていない例
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>

int main()
{
	std::vector<int> vec = {9, 8, 7};

	for (auto e : vec)
	{
		e = 0;
	}

	for (auto e : vec)
	{
		std::cout << e << std::endl;
	}
}
出力
9
8
7

1.4. 各種アルゴリズム

イテレータやイテレータとセンチネルによる範囲を引数に取るアルゴリズムも多く標準ライブラリには用意されています。そのようなアルゴリズムを用いれば、「コンテナの一部だけソートする」といったことが可能です。

等にまとめられていますので、そちらを参照してください。なお、これらもstd::hogehogeとstd::ranges::hogehogeの2種類用意されています。後者は全てC++20で追加されたもので、イテレータの実装が不十分な場合は使用できないことがあります。（Projectionについての説明は省きます）

1.5. reverse/const_iterator

ついでに、std::ranges::begin/endの仲間について紹介します。

1.5.1. reverse_iterator

std::ranges::rbegin/rendを使用すると、「範囲」を逆順に走査する「reverse_iterator」と呼ばれるイテレータが取得できます。（標準ライブラリコンテナはメンバ関数としても持っています。）

std::rbegin/end
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>

int main()
{
	std::vector<int> vec = {9, 8, 7};

	auto rit = std::ranges::rbegin(vec);

	auto rend = std::ranges::rend(vec);

	for (; rit != rend; ++rit)
	{
		std::cout << *rit << std::endl;
	}
}
出力
7
8
9

std::reverse_iteratorを使用して普通のイテレータからreverse_iteratorを作ることが出来ます。

std::reverse_iterator
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>

int main()
{
	std::vector<int> vec = {9, 8, 7};

	// 逆順に走査するので、`end`が`begin`になる
	auto rit = std::reverse_iterator{vec.end()};

	// ヘルパ関数あり
	auto rend = std::make_reverse_iterator(vec.begin());

	for (; rit != rend; ++rit)
	{
		std::cout << *rit << std::endl;
	}
}
出力
7
8
9

1.5.2. const_iterator

std::ranges::cbegin/cendか、constな「範囲」からstd::ranges::begin/endでイテレータを取得した場合、「const_iterator」と呼ばれるイテレータが取得できます。（標準ライブラリコンテナはメンバ関数としても持っています。）

const_iteratorは「指す要素がconst」であるイテレータです。イテレータを前後に進めることは出来ますが、間接参照の返り値は変更できない型になります。

const_iterator
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>

int main()
{
	std::vector<int> vec = {9, 8, 7};

	{
		auto cit = std::ranges::cbegin(vec);

		auto cend = std::ranges::cend(vec);

		// *cit = 10; // NG: 間接参照の返り値は`const int&`なので変更はできない！

		for (; cit != cend; ++cit)
		{
			std::cout << *cit << std::endl;
		}
	}

	{
		// constなvector
		const auto& cvec = vec;

		// constなvectorのイテレータは勝手にconst_iteratorになる
		auto cit = std::ranges::begin(cvec);

		// constなvectorのイテレータは勝手にconst_iteratorになる
		auto cend = std::ranges::end(cvec);

		// *cit = 10; // NG: 間接参照の返り値は`const int&`なので変更はできない！

		for (; cit != cend; ++cit)
		{
			std::cout << *cit << std::endl;
		}
	}
}
出力
9
8
7
9
8
7

また、普通のイテレータはconst_iteratorへ変換することが出来ます。

const_iteratorへの変換
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>

int main()
{
	std::vector<int> vec = {9, 8, 7};

	const auto& cvec = vec;

	decltype(vec.begin()) it = vec.begin();
	// decltype(vec.begin()) it = cvec.begin(); // NG: constを剥がすような方向には変換できない
	decltype(cvec.begin()) it = vec.begin();    // OK: const性が付く分には問題ない
	decltype(cvec.begin()) it = cvec.begin();
}

1.5.3. const_reverse_iterator

cosnt_iteratorかつreverse_iteratorなイテレータもあります。これはstd::ranges::crbegin/crendで取得できます。（標準ライブラリコンテナはメンバ関数としても持っています。）

const_reverse_iterator
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>

int main()
{
	std::vector<int> vec = {9, 8, 7};

	auto crit = std::ranges::crbegin(vec);
	auto crend = std::ranges::crend(vec);

	// reverse_iteratorからは暗黙に変換可能
	decltype(crit) _ = std::ranges::rbegin(vec);

	for (; crit != crend; ++crit)
	{
		std::cout << *crit << std::endl;
	}
}
出力
7
8
9

1.6. イテレータが指す値に対するユーティリティ

イテレータが指す値に対してのstd::moveやstd::ranges::swapを行うものがユーティリティとして用意されており、そちらを使うべきなので、その2つの説明もしておきます。

1.6.1. std::ranges::iter_move

このカスタマイゼーションポイントオブジェクトは、イテレータiに対してstd::move(*i)と書くのを、std::ranges::iter_move(i)と書くことができるものです。ということで、iが指している要素をムーブして取得する時に使います。iter_moveを使うことで、場合によっては「コピーの省略による直接構築によるムーブ操作の減少」等で性能が向上することがあります。

std::ranges::iter_move
#include <iterator>
#include <ranges>
#include <vector>

struct S
{
	S()                    = default;
	// コピー禁止
	S(const S&)            = delete;
	S& operator=(const S&) = delete;
	// ムーブは許可
	S(S&&)                 = default;
	S& operator=(S&&)      = default;
};

int main()
{
	// ムーブのみ可能な型の vector
	std::vector<S> vec;

	vec.emplace_back(S{});

	// コピーなのでだめ
	// S s = *vec.begin();

	// ムーブなので大丈夫
	S s = std::ranges::iter_move(vec.begin());
}

1.6.2. std::ranges::iter_swap

このカスタマイゼーションポイントは、イテレータi1/i2に対してstd::ranges::swap(*i1, *i2)と書くのを、std::ranges::iter_swap(i1, i2)と書くことができるものです。ということで、イテレータが指す要素同士をswapする時に使います。（なお、C++17以前はstd::iter_swapを使用できます）

std::ranges::iter_swap
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>

int main()
{
	std::vector<int> vec = {9, 8, 7};

	std::ranges::iter_swap(vec.begin(), vec.begin() + 2);

	for (auto e : vec)
	{
		std::cout << e << std::endl;
	}
}
出力
7
8
9

1.7. イテレータによる範囲 vs コンテナそのもの

ここまではイテレータの使い方を説明してきたので、最後になぜイテレータがよいものなのかという点ですが、それは

  • イテレータを実装することで、どのコンテナでも共通のインターフェース（使い方）で扱える
    • どんなアルゴリズムでもテンプレート×イテレータで実装すれば、どんな未知のコンテナでも使用可能に！
  • イテレータを使うことで、より柔軟に範囲の指定ができるようになる
    • コンテナだと一部の範囲だけを表すことは出来なかったので大きな利点（でもC++20からはそれもできる、そう、<ranges> ならね）

というのが大きな理由です。

2. イテレータカテゴリとその他性質

とりあえずイテレータがどういうものかという雰囲気は感じていただけたかと思います。
さて、イテレータはC++20においては以下6つのカテゴリーによって分類がされていますので、それぞれのカテゴリについて見ていきます。

  • 入力イテレータ（Input Iterator）
  • 前方向イテレータ（Forward Iterator）
  • 双方向イテレータ（Bidirectional Iterator）
  • ランダムアクセスイテレータ（Random Access Iterator）
  • 隣接イテレータ（Contiguous Iterator）
  • 出力イテレータ（Output Iterator）

2.1. イテレータカテゴリ同士の関係

6種類のイテレータカテゴリは下の画像のような関係になっています。

矢印は「指している方が指されている方を含む」ことを表します。（例えば双方向イテレータは、前方向イテレータや入力イテレータとしても使用できる）ただし、破線矢印は「前方向イテレータ以上のイテレータ」が出力イテレータでもある場合のみ成立します。

6種類のイテレータの定義とその関係
図: iterator - cpprefjp C++日本語リファレンス を元に筆者作成（CC-BY）

2.2. それぞれのカテゴリで「出来る操作」

それぞれのカテゴリについて、具体例で「出来る操作」を説明していきます。ただし、「出来る操作」というのはそのカテゴリで保証されている操作、「出来ない操作」というのはそのカテゴリで保証されていない操作です。つまり、「出来ない操作」が実装されていることがあります。（特に前方向～隣接イテレータで扱う例のイテレータは、出力イテレータでもあるので書き込みもできる。）

2.3. 入力イテレータ

入力イテレータでは、std::istream_iterator<T>を例にします。std::istream_iterator<T>は、任意のstd::istreamオブジェクト（std::cinなど）から、operator>>でTの入力を受け取るのを、イテレータのインターフェースで出来るようにしたイテレータです。

センチネルとの比較は、std::istream_iteratorが保持しているstd::istreamオブジェクトから入力ができるかを表します。なのでこのコードでは、標準入力から入力が受け取れる間（EOFが流れて来ない間）、operator>>でstd::stringを受け取り続けることになります。

istream_iteratorの例
static_assert(std::input_iterator<std::istream_iterator<std::string>>);

// std::stringを`operator>>`を使ったかのように入力できるイテレータ
std::istream_iterator<std::string> i(std::cin);

// センチネル（今回は標準入力が使用できる状態かを表しているか）
//  std::default_sentinelはグローバルコンパイル時定数として既に宣言されている
std::default_sentinel;

for (std::string str; i != std::default_sentinel; ++i)
{
	str = *i;

	std::cout << str << std::endl;
}
入力例
a b c
def
出力例
a
b
c
def

なお、このイテレータが走査する「範囲」は、時間軸上に存在する値の並びであり、あるタイミングで「範囲」が全てメモリ上に存在するとは限りません。

2.3.1. 入力イテレータが出来ること

動作 動作の内容 備考
ムーブ イテレータをムーブする コピーは出来ない
インクリメント イテレータiが指す要素を次に進める 前置はiへの参照が返り値（後置は未規定だが、iへの参照のことが多い）
間接参照 イテレータが指す要素の値を取得する 書き込みは通常出来ない
センチネルとの等値比較 イテレータが範囲外の要素を指しているかを取得する 今回の例だと標準入力からもう入力出来ないかどうかを取得する

ちなみに、デフォルト構築したstd::istream_iteratorは、std::istream_iteratorのセンチネルとして扱うことが出来たりします。（ただし、この仕様は入力イテレータが保証している範囲を超えたものなので、全ての入力イテレータがこの仕様というわけでないので注意です）

2.3.2. マルチパスではない（シングルパス）ということ

今回の例では、読み取りをするたびに標準入力から入力を受け取っているので、標準入力の状況によって読み取れる値は変わることがわかります。

このように、入力イテレータが走査する範囲は、走査するたびに結果が変わる可能性があり、再現性もありません。そのため、必然的に入力イテレータは2度以上同じ範囲を走査することが出来ません。同じ範囲を2回以上走査することが出来ないので、マルチパスではなく、 シングルパス（1回しか走査出来ない） であることになります。

2.3.3. コピーについて

マルチパス保証が無いが故に、入力イテレータはコピーが出来ないと考えるべきです。というのも、仮に入力イテレータaをコピーした入力イテレータbがあったとしましょう。この場合、aから得られた範囲r_aとbから得られた範囲r_bは異なるものになる可能性があります。bはaをコピーしたものなのに、b_rはa_rと異なる事があるということは、本質的にはbはaのコピーではないと言えるので、コピーは出来ないと考えるべき、ということです。

2.4. 前方向イテレータ

前方向イテレータは、std::forward_list<T>::iteratorを例にします。std::forward_list<T>は単方向リンクリストと呼ばれるコンテナで、各要素がそれぞれ動的にメモリ上に確保され、それぞれの要素は次の要素へのポインタを持つような形で、それを辿って走査することが出来ます。ただし前の要素へのポインタは持たないので、逆順にアクセスすることは出来ません。

forward_list::iteratorの例
static_assert(std::forward_iterator<std::ranges::iterator_t<std::forward_list<int>>>);

std::forward_list<int> list{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

{
	// std::forward_list<int>::iterator
	auto i = std::ranges::begin(list);

	// 前方向イテレータ以上はイテレータ自身がセンチネルでもある
	decltype(i) s = std::ranges::end(list);

	for (; i != s; ++i)
	{
		std::cout << *i << std::endl;
	}
}

{
	auto i = std::ranges::begin(list);

	// コピー可
	auto copy = i;

	// どちらもtrue, コピー元とコピーは影響しあわない
	++copy == ++std::ranges::begin(list);
    i == std::ranges::begin(list);
}
出力
0
1
2
3
4
5
6
7
8
9

2.4.1. 前方向イテレータが出来ること

入力イテレータが出来る操作に加えて、次の操作が出来るようになります。

動作 動作の内容 備考
コピー イテレータをコピーする デフォルト構築も出来るようになる
インクリメント イテレータiが指す要素を次に進める 前置はiへの参照、後置はインクリメント前のiのコピーが返り値
センチネルとの等値比較 イテレータが範囲外の要素を指しているかを取得する センチネルにイテレータを用いることも可能
全部乗せ版
動作 動作の内容 備考
ムーブ イテレータをムーブする
コピー イテレータをコピーする デフォルト構築も出来るようになる
インクリメント イテレータiが指す要素を次に進める 前置はiへの参照、後置はインクリメント前のiのコピーが返り値
間接参照 イテレータが指す要素の値を取得する
センチネルとの等値比較 イテレータが範囲外の要素を指しているかを取得する センチネルにイテレータを用いることも可能

2.4.2. マルチパスであるということ

前方向イテレータ以上はマルチパス（同じ範囲を2回以上走査することが出来る）になり、同時に入力イテレータで触れた「意味論的に正しいコピー」が可能になります。よって、イテレータをコピーして複数回走査してもよい（複数回走査しても得られる範囲は同じ）ことが保証（マルチパス保証） されています。

2.5. 双方向イテレータ

双方向イテレータは、std::list<T>::iteratorを例にします。std::listは双方向リンクリストと呼ばれるコンテナで、std::forward_listのように各要素が動的にメモリ上に確保されますが、次の要素だけでなく前の要素へのポインタを持ちます。これによって、逆順の走査が可能になっています。

std::list::iterator
static_assert(std::bidirectional_iterator<std::ranges::iterator_t<std::list<int>>>);

std::list<int> list{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

{
	// std::list<int>::iterator
	auto i = std::ranges::begin(list);

	// やっぱりイテレータ自身がセンチネルでもある
	decltype(i) s = std::ranges::end(list);

	// インクリメント出来る
	for (; i != s; ++i)
	{
		std::cout << *i << std::endl;
	}

	std::cout << std::endl;

	// デクリメントも出来る
	--i;

	// 逆順に走査する時は範囲外アクセスのチェック場所をよくよく気をつける
	for (;; --i)
	{
		std::cout << *i << std::endl;

		if (i == std::ranges::begin(list)) break;
	}
}
出力
0
1
2
3
4
5
6
7
8
9

9
8
7
6
5
4
3
2
1
0

2.5.1. 双方向イテレータが出来ること

前方向イテレータが出来る操作に加えて、次の操作が出来るようになります。

動作 動作の内容 備考
デクリメント イテレータiを指す要素を前に戻す 前置はiへの参照、後置はデクリメント前のiのコピーが返り値
全部乗せ版
動作 動作の内容 備考
ムーブ イテレータをムーブする
コピー イテレータをコピーする デフォルト構築も出来る
インクリメント イテレータiが指す要素を次に進める 前置はiへの参照、後置はインクリメント前のiのコピーが返り値
デクリメント イテレータiを指す要素を前に戻す 前置はiへの参照、後置はデクリメント前のiのコピーが返り値
間接参照 イテレータが指す要素の値を取得する
センチネルとの等値比較 イテレータが範囲外の要素を指しているかを取得する センチネルにイテレータを用いることも可能

2.5.2. reverse_iterator

双方向イテレータ以上は逆順の走査が可能になりますが、通常の走査と同じように扱えません。というのも

  • そもそもインクリメントとデクリメントが逆
  • インクリメントとデクリメントを取り替えても:
    • 普通のイテレータで言う所のendからbeginに行きたいので、最初の要素はendの1つ前から
      • endそれ自体は「範囲」の外を参照しているので、endはループ開始前に1つ前に移動する必要がある
    • end != beginとでもしようものなら、beginが指す要素にアクセス出来ない
      • 「逆順の範囲」の末端（「元の範囲」の先頭）の要素が抜け落ちることになる
      • ということはbeginもループ開始前に1つ前に移動する必要がある
  • 面倒！！！

そこで、イテレータを包むことで逆順の走査を通常と同じように書けるstd::reverse_iteratorが存在します。

リバースイテレータ
static_assert(std::bidirectional_iterator<std::ranges::iterator_t<std::list<int>>>);
static_assert(std::bidirectional_iterator<std::reverse_iterator<std::ranges::iterator_t<std::list<int>>>>);

std::list<int> list{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

{
	// イテレータ、リバースイテレータの型
	using iter    = std::ranges::iterator_t<decltype(list)>;
	using re_iter = std::reverse_iterator<iter>;

	// リバースイテレータのbeginはイテレータのend、endはbeginで構築する
	re_iter re_beg(std::ranges::end(list));
	re_iter re_end(std::ranges::begin(list));

	// std::ranges::rbegin/rend でも取得できる
	auto re_beg_ = std::ranges::rbegin(list);
	auto re_end_ = std::ranges::rend(list);

	for (; re_beg != re_end; ++re_beg)
	{
		std::cout << *re_beg << std::endl;
	}

	std::cout << std::endl;

	// リバースイテレータも双方向イテレータなのでデクリメント可能
	--re_beg;

	// リバースイテレータを更に逆順に走査することも可能
	for (;; --re_beg)
	{
		std::cout << *re_beg << std::endl;
		
		if (re_beg == std::ranges::rbegin(list)) break;
	}
}
出力
9
8
7
6
5
4
3
2
1
0

0
1
2
3
4
5
6
7
8
9

2.6. ランダムアクセスイテレータ

ランダムアクセスイテレータは、std::deque<T>::iteratorを例にします。std::deque<T>はシーケンスコンテナで、名の由来（double-ended queue）通り、先頭と終端のどちらからも要素を効率よく追加/削除出来るコンテナです。「ある特定のインデックスの要素に直接アクセスする」（ランダムアクセス）が行えます。

std::deque::iterator
static_assert(std::random_access_iterator<std::ranges::iterator_t<std::deque<int>>>);

std::deque<int> deque{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

{
	// bool値をtrue/falseで表示するためのフラグ
	std::cout << std::boolalpha;

	auto i = std::ranges::begin(deque);
	auto s = std::ranges::end(deque);

	// 任意の整数だけ移動したイテレータを定数時間で取得可能
	std::cout << "*(i + 1)   " << *(i + 1) << std::endl;

	// イテレータ同士の引き算が可能（「範囲」の要素数＝イテレータの距離を定数時間で取得可能）
	std::cout << "s - i      " << s - i << std::endl;

	// イテレータが指す要素のインデックスを比較している感じ
	std::cout << "i < s      " << (i < s) << std::endl;

	// イテレータが指す要素を基準としたインデックスでアクセス
	std::cout << "(i + 1)[1] " << (i + 1)[1] << std::endl;
}
出力
*(i + 1)   1
s - i      10
i < s      true
(i + 1)[1] 2

2.6.1. ランダムアクセスイテレータが出来ること

双方向イテレータが出来る操作に加えて、次の操作が出来るようになります。

動作 動作の内容 備考
整数nとの加算 イテレータiが指す要素をnだけ次に進める i + n/n + i（返り値はiのコピー）i += n（返り値はiへの参照）
整数nとの減算 イテレータiが指す要素をnだけ前に戻す i - n/n - i（返り値はiのコピー）i -= n（返り値はiへの参照）
イテレータ同士の減算 左辺のイテレータi_lhsから右辺のイテレータi_rhsへの距離nを取得する i_lhsをn回インクリメントするとi_rhsになる
イテレータ同士の比較 イテレータ同士（左辺i_lhs、右辺i_rhs）の距離nによる大小/等値比較 n > 0ならi_lhs < i_rhs、n < 0ならi_lhs > i_rhsが成立
整数nによる添え字アクセス イテレータiからnだけ進めたイテレータが指す要素を取得する 組み込み同様、意味論的にi[n]は*(i + n)と同じことをする
全部乗せ版
動作 動作の内容 備考
ムーブ イテレータをムーブする
コピー イテレータをコピーする デフォルト構築も出来る
インクリメント イテレータiが指す要素を次に進める 前置はiへの参照、後置はインクリメント前のiのコピーが返り値
デクリメント イテレータiを指す要素を前に戻す 前置はiへの参照、後置はデクリメント前のiのコピーが返り値
整数nとの加算 イテレータiが指す要素をnだけ次に進める i + n/n + i（返り値はiのコピー）i += n（返り値はiへの参照）
整数nとの減算 イテレータiが指す要素をnだけ前に戻す i - n/n - i（返り値はiのコピー）i -= n（返り値はiへの参照）
イテレータ同士の減算 左辺のイテレータi_lhsから右辺のイテレータi_rhsへの距離nを取得する i_lhsをn回インクリメントするとi_rhsになる
イテレータ同士の比較 イテレータ同士（左辺i_lhs、右辺i_rhs）の距離nによる大小/等値比較 n > 0ならi_lhs < i_rhs、n < 0ならi_lhs > i_rhsが成立
間接参照 イテレータが指す要素の値を取得する
整数nによる添え字アクセス イテレータiからnだけ進めたイテレータが指す要素を取得する 組み込み同様、意味論的にi[n]は*(i + n)と同じことをする
センチネルとの等値比較 イテレータが範囲外の要素を指しているかを取得する センチネルにイテレータを用いることも可能

2.7. 隣接イテレータ

隣接イテレータは、std::vector<T>::iteratorを例にします。3std::vector<T>は動的配列として有名なシーケンスコンテナで、ランダムアクセスはもちろん、組み込み配列のように全ての要素が連続してメモリ上に配置されています。

対して、std::deque<T>は全ての要素がメモリ上に連続しているとは限らず、ある程度の要素数毎にチャンクとして分割し、メモリ上に分散して配置されることがあります。そのためstd::dequeの場合は、要素から取得したアドレスに演算すると、チャンク外に出て結果が正しく得られなくなることがあるわけです。

なお、std::addressofはオブジェクトのアドレスを取得する関数です。（&演算子を使っても結果は変わらないですが、今回は関数の方を使いました）

std::vector::iterator
C

std::vector<int> vec{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

{
	// bool値をtrue/falseで表示するためのフラグ
	std::cout << std::boolalpha;

	auto i = std::ranges::begin(vec);

	// vec[0] のアドレスに演算するときと、イテレータに演算してからアドレスを取るのは必ず同じアドレスになる
	// （std::deque は全ての要素を連続して配置せず、ある程度で区切ったチャンクでメモリに配置するため、保証されない）
	std::cout << (std::addressof(vec[0]) + 1 == std::addressof(*(i + 1))) << std::endl;
}
出力
true

2.7.1. 隣接テレータが出来ること

ランダムアクセスイテレータが出来る操作に加えて、次の操作が出来るようになります。

動作 動作の内容 備考
メモリ連続性 イテレータが指す要素は全てメモリ上に連続されて配置される 間接参照の返り値から取ったアドレスに対して演算しても、イテレータと同じ結果を得ることが出来る
全部乗せ版
動作 動作の内容 備考
ムーブ イテレータをムーブする
コピー イテレータをコピーする デフォルト構築も出来る
インクリメント イテレータiが指す要素を次に進める 前置はiへの参照、後置はインクリメント前のiのコピーが返り値
デクリメント イテレータiを指す要素を前に戻す 前置はiへの参照、後置はデクリメント前のiのコピーが返り値
整数nとの加算 イテレータiが指す要素をnだけ次に進める i + n/n + i（返り値はiのコピー）i += n（返り値はiへの参照）
整数nとの減算 イテレータiが指す要素をnだけ前に戻す i - n/n - i（返り値はiのコピー）i -= n（返り値はiへの参照）
イテレータ同士の減算 左辺のイテレータi_lhsから右辺のイテレータi_rhsへの距離nを取得する i_lhsをn回インクリメントするとi_rhsになる
イテレータ同士の比較 イテレータ同士（左辺i_lhs、右辺i_rhs）の距離nによる大小/等値比較 n > 0ならi_lhs < i_rhs、n < 0ならi_lhs > i_rhsが成立
間接参照 イテレータが指す要素の値を取得する
整数nによる添え字アクセス イテレータiからnだけ進めたイテレータが指す要素を取得する 組み込み同様、意味論的にi[n]は*(i + n)と同じことをする
センチネルとの等値比較 イテレータが範囲外の要素を指しているかを取得する センチネルにイテレータを用いることも可能
メモリ連続性 イテレータが指す要素は全てメモリ上に連続されて配置される 間接参照の返り値から取ったアドレスに対して演算しても、イテレータと同じ結果を得ることが出来る

2.8. 出力イテレータ

出力イテレータは、既存の「範囲」を走査するためではなく、既存の「範囲」を任意の場所に出力するために使用するものです。そのため、センチネルはありません。（前方向イテレータ以上が出力イテレータを満たす時は当然センチネルがありますが、出力イテレータとしては保証されていません）

例としては、次の3つを扱います。

  • std::output_iterator<Val>
    • 任意のstd::ostreamオブジェクト（std::coutなど）から、operator<<でValを出力するのを、イテレータのインターフェースで出来るようにしたイテレータ
  • std::back_insert_iterator<Container>
    • メンバ関数push_backが実装されているコンテナContainerにpush_backをするのを、イテレータのインターフェースで出来るようにしたイテレータ
  • 生配列へのポインタ
    • 生配列へのポインタ。これ自体は隣接イテレータに属するが、間接参照した結果に書き込みが出来る場合は出力イテレータとしても扱える。

出力イテレータ3種類
std::vector source{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

// 今回は std::vector と生配列を表示するために使う（このラムダ式はジェネリックラムダ）
auto display = [](auto&& container) {
	std::string s;

	s += "[";
	for (auto e : container)
	{
		s += (std::to_string(e) + ", ");
	}
	s.pop_back();
	s.pop_back();
	s += "]\n";

	std::cout << s;
};

// std::ostream_iterator
{
    // コンセプトを満たす
    static_assert(std::output_iterator<std::ostream_iterator<int>, int>);

	// ostream_iterator<T> （T は出力したい値の型）
	std::ostream_iterator<int> out(std::cout);

	// これで標準出力出来ている
	// *out = -1; ++out; と等価
	*out++ = -1;

	// source.begin() から source.end() までを out にコピー
	// イテレータ out は標準出力に出力している
	std::ranges::copy(source.begin(), source.end(), out);
}

std::cout << std::endl;

// std::back_insert_iterator
{
    // コンセプトを満たす
    static_assert(std::output_iterator<std::back_insert_iterator<std::vector<int>>, int>);

	// メンバ関数 push_back が実装されているコンテナを出力先として用意（今回は0初期化しておく）
	std::vector<int> output = {};

	// back_insert_iterator （ちなみに、<decltype(output)> は省略可）
	std::back_insert_iterator<decltype(output)> out(output);

	// これで push_back 出来ている
	//  *out = -1; ++out; と等価
	*out++ = -1;

	// source.begin() から 5個を out にコピー
	// イテレータ out は std::vector output に push_back している
	std::ranges::copy_n(source.begin(), 5, out);

	display(output);
}

// 生配列へのポインタ
{
    // コンセプトを満たす
    static_assert(std::output_iterator<int*, int>);

	// 生配列を用意（バッファオーバーランには注意）
	int buffer[11];

	// 生配列の名前は、生配列の先頭の要素のポインタに変換されることに留意
	// これが出力イテレータになる（std::ranges::begin でも同じ結果が得られる）
	int* out = buffer;
	int* _   = std::ranges::begin(buffer);

	// これで書き込みできている
	// *out = -1; ++out; と同じ。（進めるのを忘れると同じ場所に書き込むことになる）
	*out++ = -1;

	// ラムダ式による関数が返す値の並びを 10個 out にコピー（バッファオーバーランには注意）
	//  [&n] { return n++; }: n を参照して n の値を返し、 n をインクリメントする
	int n = 10;
	std::ranges::generate_n(out, 10, [&n] { return n++; });

	display(buffer);
}
出力
-10123456789
[-1, 0, 1, 2, 3, 4]
[-1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

2.8.1. 出力イテレータが出来ること

動作 動作の内容 備考
ムーブ イテレータをムーブする
インクリメント イテレータiが指す書き込み位置を次に進める 前置はiへの参照が返り値（後置は未規定だが、iへの参照が返り値のことも）
間接参照 書き込み操作が出来る参照やオブジェクトを返す
*i++ = e *i = e; ++iと等価 eは出力したい式

2.9. 距離（サイズ）を定数時間で求められるか

イテレータのペアや、イテレータとセンチネルのペアでは、それらのペアが指し示す「範囲」に幾つの要素が含まれるかを考えることが出来、これを「距離（サイズ）」と呼びます。これはstd::ranges::distance（C++17以前ではstd::distance）で求められると説明しましたが、それは必ずしも定数時間で求められるわけではありません。

それぞれの要素にはインデックスが振られるなどしている場合には、そのインデックスの引き算で距離を求めることが出来ますが、一方、そうではない場合は、実際にイテレータをインクリメントして走査することによって距離を求めなくてはならず、比較的大きな実行時負荷が掛かってしまいます。

というように、距離を求めるにも「定数時間」で取得できるかどうかというのはそれなりに重要な情報であるとわかります。そして、これの情報を取得するには、std::sized_sentinel_for<S, I>を使用します。Sがセンチネルの型、Iがイテレータの型です。

3. イテレータコンセプトコンセプトと実装について

<ranges>やC++20のイテレータは、同じくC++20で導入されたコンセプトを用いて何たるかが定義されています。というわけで、イテレータコンセプトを読んでいくとイテレータの詳しいことがわかります。

を参照してください。参照に書いてある記事を書いてくださっている方々に感謝申し上げます。

3.1. イテレータコンセプト概要

イテレータコンセプトは、基本的にはイテレータカテゴリをそのまま表現しており、下の図のようになっています。

コンセプトの包摂関係

図: 筆者作成（CC-BY） 4

3.1.0. おやくそく

いくつか注意点・約束点があるので、そちらの説明をまとめてします。

3.1.0.1. 定義

以後、文脈によって明示はされることがほとんどですが、次の語は次のような意味で使用されます。

  • I: イテレータの型（または、テンプレート引数）
  • i: Iのインスタンス
  • RI: Iからcv修飾と参照を取っ払った型（または、テンプレート引数）
  • ri: RIのインスタンス
  • S: センチネルの型（または、テンプレート引数）
  • s: Sのインスタンス
  • T: イテレータに限らない一般的な型（または、テンプレート引数）
  • U: イテレータに限らない一般的な型（または、テンプレート引数）
  • e: 出力イテレータで出力する式
  • Val: 式eの型（または、テンプレート引数）
  • P: 出力イテレータが間接参照した時に返すプロキシオブジェクトの型
  • p: Pの値
  • value_type: std::iter_value_t<I>
  • reference: std::iter_reference_t<I>
  • rvalue_reference: std::iter_rvalue_reference_t<I>

3.1.0.2. イテレータの文脈での説明であるということ

後述しますがIやSには参照（cv修飾も）が付くことはありません。（なのでRIが存在する必要はなかったりしますが、一応使用します）

また、イテレータで使用する文脈でのみ説明をするので、イテレータ以外にも使用できるタイプエイリアスやコンセプトについて、イテレータ以外の文脈での使用法については、適宜リファレンスを参照してください。

3.1.0.3. std::の省略

これからは全て名前空間stdの元で話が進んでいきますので、std::を省略することが多くなります。適宜読み替えてください。

3.1.0.4. 各節の「まとめ」について

§3.2. 以降、各節の最後に全文太文字にした順序なしリストでまとめを書くので、それだけでも見ればわかるかと思います。

3.1.1. センチネルのコンセプト

センチネルに関しては、イテレータとペアで使われるので、std::sentinel_for<S, I>というコンセプトを用います。つまり、「ある型SはイテレータIのセンチネルか」を表しています。（詳細は §3.4.4. で説明しています）

なお、テンプレート引数がS→Iの順番であるのは、

template <std::sentinel_for<I> S>

というようにテンプレート引数の宣言と共に使用する際、宣言されるテンプレート引数（この例だとS）が、一番先頭に挿入される、つまり

template <class S>
requires std::sentinel_for<S, I>

と等価になるという仕様があるからです。（意味論的にも、主体となるテンプレート引数が1番先頭に来ているのでわかりやすい、というのもあります）

3.1.2. イテレータコンセプトの使われ方

イテレータやセンチネルは値渡し（実引数はコピーかムーブをして渡される）ことが原則5とされています。そのため、イテレータコンセプト（とセンチネルのコンセプト）は、次のように使われます。

イテレータコンセプトの使われ方
template <std::input_or_output_iterator I, std::sentinel_for<I> S>
void f(I i, S s);

つまり、IやSに渡される型は参照が付くことはありません。したがって、イテレータコンセプトに対して渡されるテンプレート引数には参照が付いていないことを前提としていることに留意してください。（うっかり仮引数をforwarding referenceにしたら面倒なことになります...）

3.1.3. 補: requires式のパラメータと値カテゴリ

コンセプトの定義におけるrequires式はパラメータを取ることが出来ます。このパラメータを使用して、値カテゴリとconst性についてを表明することが出来ます。（一部、値カテゴリとconstをまとめて「値カテゴリ」と呼称していますが、気にしないでください）

requires式のパラメータと値カテゴリ
template <class T>
concept C = requires(T t, T& lr, const T& clr, T&& rr, const T&& crr)
{
	// それぞれ、関数 f はコメントする値カテゴリを受け取れなければならない
	f(t);              // lvalue
	f(lr);             // lvalue
	f(clr);            // const lvalue
	f(std::move(rr));  // rvalue
	f(std::move(crr)); // const rvalue
};

このとき、テンプレート引数Tが配列以外のオブジェクト型（参照は付いていない）でcv修飾も付いていないと仮定すると、コード中のコメントのように値カテゴリを決定することが出来、それについての制約を課していると考えることが出来ます。

3.1.4. 補: 暗黙的な式のバリエーション

先程のコードのrequires式で出てこなかったconst Tですが、これにはまた別の意味が付与されており、

  • lvalue
  • const lvalue
  • rvalue
  • const rvalue

の4種類の値カテゴリを同時に表すものとされています。したがって、const Tの式を1つ書くと、上に上げた4種類の全てについて、その式が成立することを要求するのです。（明示的に、それぞれの値カテゴリに制約を書いている場合は除く）

暗黙的な式のバリエーション
template <typename T>
concept C = requires(const T a, T b)
{
	a + b;
};

// コンセプト C のrequires式にある const T による式は
// 次のように、4種類の値カテゴリの制約を一度に制約している
template<class T>
concept C_ =
  requires(T a, T b) { a + b; } &&
  requires(const T a, T b) { a + b; } &&
  requires(T&& a, T b) { std::move(a) + b; } &&
  requires(const T&& a, T b) { std::move(a) + b; };

ここでconst Tのパラメータを受け入れる関数を考えた時、const Tのパラメータ受け取る引数が、（ここではTは任意の型、Uはテンプレート引数とします）

  • T（値渡し、ムーブ/コピーが起こる）
  • const T&（const lvalue reference）
  • U&（lavlue reference、U = const Tと推論されてなんとかなる）
  • U&&（forwarding reference）

であれば、1つで4種類全てを受け取ることが可能です。一方、メンバ関数は、

  • const修飾しているメンバ関数（参照修飾子なし）

であれば、1つで4種類全てを受け取ることが可能であるとわかります。（参照修飾子がある場合は、const &とconst &&のどちらもを用意しないといけないでしょう）

3.2. std::input_or_output_iterator<I>

std::input_or_output_iterator<I>は、イテレータコンセプトの最も基礎、つまりC++イテレータの最低条件を定めるコンセプトです。このコンセプトは特に名称が付いているイテレータカテゴリを表しませんが、この記事では「C++20イテレータ」というカテゴリを表している、ということにします。（この記事内だけの用法です）

それ単体のコンセプトのみを満たすイテレータは（多分）存在せず、たとえこのコンセプトのみ満たしていたとしても、ほとんど何もできません。

input_or_output_iterator
namespace std {
  template<class I>
  concept input_or_output_iterator =
    #1
    requires(I i) {
      { *i } -> can-reference;
    } &&
    #2
    weakly_incrementable<I>;
}

3.2.1. #1

can-reference<T>は説明専用のコンセプトで、Tがlvalue referenceを付けられる型であることを要求します。これは結局のところ、Tがvoidでないことを要求しているらしいです。

  • iは間接参照が可能で、その返り値の型はvoidではないことを要求しています

3.2.2. #2

weakly_incrementable<I>は、主にIが前置/後置インクリメント可能であることを表すコンセプトで、次のように定義されています。6

weakly_incrementable
namespace std {
  template<class I>
  concept weakly_incrementable =
    ##1
    movable<I> &&
    requires(I i) {
      ##2
      typename iter_difference_t<I>;
      requires is-signed-integer-like<iter_difference_t<I>>;
      ##3
      { ++i } -> same_as<I&>;   // 等しさを保持することを要求しない
      i++;                      // 等しさを保持することを要求しない
    };
}

3.2.2.1. ##1

movable<T>は、Tがオブジェクト型（算術型、列挙型、ポインタ型、メンバポインタ型、std::nullptr_t、配列型、共用型、クラス型、これらのcv修飾を含む）でムーブ構築/代入が可能であることを表すコンセプトです7。

  • Iがムーブ構築/代入（それに伴ってstd::ranges::swapによるスワップ操作）が出来るオブジェクト型であることを要求しています

3.2.2.2. ##2

iter_difference_t<I>は、Iからイテレータ間の距離を表す型（difference_type）を取得してくれるエイリアステンプレートです。これから型を取得出来ることを要求しています。

  • std::iter_difference_t<I>は、RIに対して、difference_typeを次のどれかから取得してきてくれます。
    • std::incrementable_traits<RI>の特殊化
    • RI::difference_type（std::iterator_traits<RI>経由）
    • ri - riの結果の型

is-signed-integer-like<T>はTが符号付整数として扱える型であることを要求する説明専用コンセプトです。（主にコンパイラーが独自実装する整数型等を許容するために使われます。一般のプログラマーはptrdiff_tなどの普通の整数型を使えば事足りるでしょう）

  • Iからdifference_typeを取得でき、取得できた型は符号付き整数のように扱えることを要求しています8

3.2.2.3. ##3

same_as<T, U>は、TとUがcv修飾や参照を含め、型が完全に一致することを要求するコンセプトです。よって、前置インクリメントがイテレータの参照を返すことを要求します。（なお §3.2.2.4. でわかるのですが、これは前置インクリメントが*thisを返すことを念頭にしています）

ただし、今回はこの2の式には等しさを保持することを要求されていません。したがって、マルチパスであることは要求されていません。

  • イテレータが前置/後置インクリメントが出来ることと、前置インクリメントはi自身への参照を返すことを要求しています（等しさは保持しなくてよい＝シングルパスでよい）

3.2.2.4. weakly_incrementableの意味論的制約

weakly_incrementableのモデルとなるためには、次の要件を満たす必要があります。

  • i++と++iは同じ定義域を持つ
  • iが前置/後置インクリメントの定義域（どちらも同じ定義域だが）に含まれている場合
    • ++iとi++はいずれも、イテレータiが次の要素を指すように変更する
    • std::addressof(++i) == std::addressof(i)を満たす
      • つまり、前置インクリメントの返り値は*thisである
         
  • i++と++iのどちらも、同じ範囲を走査する上に、次の要素を指すように変更することを要求しています（前置インクリメントの返り値はi自身への参照）

3.2.3. まとめ

すべてまとめると、std::input_or_output_iterator<I>では、次のことを要求しています。

備考（以後表形式のまとめでは全て適用されます）:

  • Tは、voidではない型を表します
  • autoは、その部分の型が未規定であることを示します
  • 対象が書かれていない場合は、上のものに準じます
  • メンバ関数に対する右辺値/左辺値修飾子は、最低要件を表しています
対象 要求される内容 制約関係特記 実装・備考・制約その他
I オブジェクト型である イテレータは原則ポインタかクラスなので問題にはならない
std::iter_difference_t<I>が符号付整数型を表す std::incrementable_traits<I>を特殊化するか、I::difference_typeを定義する
i I(I&&) noexcept I& operator=(I&&) noexcept デフォルト構築、コピー構築/代入は必要ではない これはムーブ構築/代入のこと
T operator*() & 返り値の型はvoidではない型
I& operator++() & 返り値は*this 等しさを保持しなくてよい（指す「範囲」を変更するような操作を行ってよい）
auto operator++(int) & 返り値に関して、型・値ともに未規定 等しさを保持しなくてよい（指す「範囲」を変更するような操作を行ってよい）
++i, i++ 同じ定義域を持ち、次の要素を指すようにイテレーターを更新する 通常前置インクリメントを用いて後置インクリメントを実装するので問題にはならない

3.3. std::input_iterator<I>

std::input_iterator<I>は、入力イテレータという、何らかのシーケンスの入力を受け取るのに使えるイテレータを表すコンセプトです。

input_iterator
namespace std {
  template<class I>
  concept input_iterator =
    #1
    input_or_output_iterator<I> &&
    #2
    indirectly_readable<I> &&
    #3
    requires { typename ITER_CONCEPT(I); } &&
    derived_from<ITER_CONCEPT(I), input_iterator_tag>;
}

3.3.1. #1

始めに画像で示したように、std::input_iterator<I>はstd::input_or_output_iterator<I>を包含していることがわかります。

  • 入力イテレータはC++20イテレータであることを要求しています

3.3.2. #2

indirectly_readable<In>は、Inのインスタンスを間接参照した返り値から何らかを読み取れることを要求するコンセプトです。（スマートポインタなどもこのコンセプトのモデルになることが可能です）

以下のように、説明専用コンセプトindirectly-readable-impl<In>を用意し、indirectly_readable<In>はInのcv修飾/参照を外した型をindirectly-readable-impl<In>に渡す形で表現されます。

indirectly_readable
namespace std {
  // 説明専用
  template<class In>
  concept indirectly-readable-impl =
    requires(const In in) {
      ## 1
      typename iter_value_t<In>;
      ## 2
      typename iter_reference_t<In>;
      ## 3
      typename iter_rvalue_reference_t<In>;
      ## 4
      { *in } -> same_as<iter_reference_t<In>>;
      { ranges::iter_move(in) } -> same_as<iter_rvalue_reference_t<In>>;
    } &&
    ## 5
    common_reference_with<iter_reference_t<In>&&, iter_value_t<In>&> &&
    common_reference_with<iter_reference_t<In>&&, iter_rvalue_reference_t<In>&&> &&
    common_reference_with<iter_rvalue_reference_t<In>&&, const iter_value_t<In>&>;

  // cv修飾と参照を外している
  template<class In>
  concept indirectly_readable =
    indirectly-readable-impl<remove_cvref_t<In>>;
}

3.3.2.1. ##1

iter_value_t<I>はイテレータが指す要素の型（以下value_type）を取得するタイプエイリアスです。この型は、トップレベルの参照やcv修飾が無い型が求められます。

  • std::iter_value_t<I>は、RIに対して、value_typeを次のどれかから取得してきてくれます。
    • std::iterator_traits<RI>の特殊化のvalue_type
    • std::indirectly_readable_traits<RI>の特殊化のvalue_type
    • RI::value_type（std::indirectly_readable_traits<RI>経由、トップレベルcv修飾は削除される）
       
  • value_typeをiter_value_t<I>を通じて取得できることを要求しています

3.3.2.2. ##2

iter_reference_t<I>は、イテレータの要素を取得する時の型、つまりイテレータの間接参照の結果の型（以下reference、要素の型のlvalue referenceが多い）を取得するタイプエイリアスです。

  • std::iter_reference_t<I>は、iに対して、referenceを次のように型を取得します。
    • decltype(*std::declval<I&>())

特に何か新しい制約が加わってはいないのでまとめは省略します。

3.3.2.3. ##3

iter_rvalue_reference_t<I>は、イテレータの要素をムーブして取得する時の型（以下rvalue_reference、要素の型のrvalue referenceが多い）を取得するタイプエイリアスです。

  • std::iter_rvalue_reference_t<I>は、iに対して、rvalue_referenceを次のように取得します。
    • decltype(ranges::iter_move(declval<I&>()))

なお、ranges::iter_moveは間接参照が何らか値を返していればデフォルト実装でも動きはします。特に何か新しい制約が加わってはいないのでまとめは省略します。

3.3.2.4. ##4

間接参照の結果がreferenceと同じ、iter_moveによって取得した値がrvalue_refereneceで取得された型と同じことを要求しています。（暗黙的な式のバリエーションが適用されています）

  • iはどの値カテゴリ（const性含む）であったとしても、間接参照が可能で、その返り値はvoidでないことを要求しています

型が一致する件は、型を調査する式と、型を取得する経路が一致しており、必然的に同じになる（はず）なので、まとめには取り上げていません。

3.3.2.5. ##5

common_reference_with<T, U>は、TとUのどちらも束縛できる参照型がstd::common_reference<T, U>を用いて取得できることを要求するコンセプトです。ユーザー定義型に対してはstd::basic_common_reference<T, U, TQual, UQual>を用いて定義することが出来ます。

これは、従来からの通常のイテレータにおいて成立していた、value_typeとreference、rvalue_referenceの三者（C++17以前はrvalue_refernceという用語は使いませんでしたが）についての関係を、よりジェネリックに要求していると考えられます。

正直よくわからないですが、とりあえず参照を置いて逃げます。

3.3.2.6. indirectly_readable<In>の意味論的制約

indirectly_readable<In>のモデルとなるためには、次を満たす必要があります。

  • *iが等しさを保持している

ただ、これはstd::input_or_output_iterator<I>の時点で要求されており、特に新しい制約ではないのでまとめは省略します。

3.3.3. #3

この部分ではイテレータのカテゴリが適切に定義されているかをチェックしています。

3.3.3.1. イテレータカテゴリを表すタグ型

イテレータカテゴリを表すタグ型（以下イテレータタグ型）として、

イテレータカテゴリを表すタグ型たち
namespace std {
  struct input_iterator_tag { };
  struct output_iterator_tag { };
  struct forward_iterator_tag : input_iterator_tag { };
  struct bidirectional_iterator_tag : forward_iterator_tag { };
  struct random_access_iterator_tag : bidirectional_iterator_tag { };
  struct contiguous_iterator_tag: random_access_iterator_tag { };
}

の6種類の型がイテレータカテゴリに対応する形で用意されています。イテレータカテゴリに包含関係があったように、イテレータタグ型でも継承によって包含関係を表現しています。

3.3.3.2. ITER_CONCEPT(I)

ITER_CONCEPT(I)は、Iから次のようにイテレータタグ型を取得します。（ちなみに、iterator_categoryはC++17以前に使っていた名前です。C++20のイテレータとして使用できるならばiterator_conceptを定義、C++17以前のイテレータとして使用できるならばiterator_categoryを定義します）

  • std::iterator_traits<I>がプライマリテンプレートを表す時
    • I::iterator_concept
    • I::iterator_category
    • どれもなければstd::random_access_iterator_tag
  • std::iterator_traits<I>が特殊化を表す時
    • iterator_traits<I>::iterator_concept
    • iterator_traits<I>::iterator_category
    • どれもなければ取得失敗

取得が失敗すれば、明らかにコンセプトが満たされることはありません。なお、std::random_access_iterator_tagがフォールバックとして取得されるのは、ひとまずランダムアクセスイテレータとして扱って、コンセプトの他の部分の調査によって実際のカテゴリを判定できるようにするための仕様です。

3.3.3.3. std::derived_from<Derived, Base>

std::derived_from<Derived, Base>は、DerivedがBaseを基底クラスに持つ（DerivedがBaseを継承している）かどうかを調査するコンセプトです。

より強いイテレータカテゴリに属するイテレータは、より弱いイテレータカテゴリにも属しているので、ちゃんとイテレータタグ型の継承関係を調査する必要があるわけです。

3.3.3.4.

  • ITER_CONCEPT(I)によって取得したイテレータタグ型が、std::input_iterator_tag以上のカテゴリであることを要求しています

3.3.4. まとめ

備考:

  • 新しく加わった制約についてをまとめます
  • std::iter_value_t<I>をVとします
  • std::iter_reference_t<I>をRとします
  • std::iter_rvalue_reference_t<I>をRRとします
対象 要求される内容 制約関係特記 実装・備考・制約その他
I std::input_or_output_iterator<I>を満たす
std::iter_value_t<I>（以下V）が取得できる std::indirectly_readable_traits<I>を特殊化するか、I::value_typeを定義する。この型は参照にはしない（のが普通）
std::iter_reference_t<I>（以下R）が取得できる *iの返り値の型 *iの返り値の型から推論、勝手に使用可能になる
std::iter_rvalue_reference_t<I>（以下RR）が取得できる std::ranges::iter_move(i)の返り値の型 std::ranges::iter_move(i)の返り値の型から推論、勝手に使用可能になる
イテレータコンセプトを表すタグ型がstd::input_iterator_tagか、それを継承した型である I::iterator_conceptを定義する
i T operator*() const どの値カテゴリでも呼び出し可能、返り値の型はRと一致 イテレーターがconstかどうかで返り値のconst性を変えるべきではない（イテレーターのconst性と参照先の値のconst性は異なる）
std::ranges::iter_move(i)が呼び出し可能 返り値の型はRRと一致 Hidden Friendsとしてfriend T iter_move(const I&)を実装することでカスタマイズ可能
V, R, RR std::commmon_reference_t<R&&, V&>/<R&&, RR&&>/<RR&&, const V&>がどれも取得できる ユーザー定義型に関してはstd::basic_common_reference<T, U, TQual, UQual>を特殊化することで定義可能。特殊なことをしていなければ特殊化する必要はない。

3.4. std::forward_iterator<I>

std::forward_iterator<I>は、前方向イテレータという、前方向（一方通行）で複数回走査が出来るイテレータを表すコンセプトです。

forward_iterator
namespace std {
  template<class I>
  concept forward_iterator =
    #1
    input_iterator<I> &&
    #2
    derived_from<ITER_CONCEPT(I), forward_iterator_tag> &&
    #3
    incrementable<I> &&
    #4
    sentinel_for<I, I>;
}

3.4.1. #1

始めに画像で示したように、std::forward_iterator<I>はstd::input_iterator<I>を包含していることがわかります。

  • 前方向イテレータは入力イテレータであることを要求しています

3.4.2. #2

この部分ではイテレータのカテゴリが適切に定義されているかをチェックしています。

  • ITER_CONCEPT(I)によって取得したイテレータタグ型が、std::forward_iterator_tag以上のカテゴリであることを要求しています

3.4.3. #3

incrementable<I>は、weakly_incrementable<I>の強化版で、前置/後置インクリメントが等しさを保持する（マルチパス）ことや、デフォルト構築出来ることなどが追加で要求されます。

incrementable
namespace std {
  template<class I>
  concept incrementable =
    ##1
    regular<I> &&
    ##2
    weakly_incrementable<I> &&
    ##3
    requires(I i) {
      { i++ } -> same_as<I>;
    };
}

3.4.3.1. ##1

型の性質として、正則（regular、半正則かつ等値比較が可能）と半正則（semiregular、ムーブ/swap/コピー/デフォルト構築が可能）というものがあります。今回はIが正則な型であることを要求しています。そしてこれらは、

  • 正則: regular<T>
  • 半正則: semiregular<T>
  • 等値比較可能: equality_comparable<T>
  • （ムーブ可能: movable<T>）
  • （コピー可能: copyable<T>）
  • （デフォルト構築可能: default_initializable<T>）

などのコンセプトで表現されます。以下に関係するコンセプトをある程度示しました。詳しくは、コメントを参照してください。

regularとsemiregular、equality_comparable
namespace std {
  // 半正則かつ等値比較可能であることを要求
  template<class T>
  concept regular = semiregular<T> && equality_comparable<T>;

  // コピー可能（ムーブ/swap可能を含む）かつデフォルト構築可能であることを要求
  template<class T>
  concept semiregular = copyable<T> && default_initializable<T>;

  template<class T>
  concept equality_comparable = weakly-equality-comparable-with<T, T>;

  // ==, != による 2種2方向 の同値比較が可能であることを要求
  // 返り値は`bool`として扱える型を要求
  template<class T, class U>
  concept weakly-equality-comparable-with =
    requires(const remove_reference_t<T>& t,
             const remove_reference_t<U>& u) {
      { t == u } -> boolean-testable;
      { t != u } -> boolean-testable;
      { u == t } -> boolean-testable;
      { u != t } -> boolean-testable;
    };
  }

  // `T`が`bool`として扱える型であることを表明するコンセプト（一部簡単のため変更を加えています）
  template<class T>
  concept boolean-testable =
    // `T`が`bool`に変換できることを要求
    convertible_to<T, bool> &&
    // `T`の値を論理否定する文脈での値が`bool`に変換できることを要求
    requires (T&& t) {
      { !std::forward<T>(t) } -> convertible_to<bool>;
    };
  • イテレータが正則（ムーブ/swap/コピー/デフォルト構築/等値比較が可能）な型であることを要求しています

3.4.3.2. ##2

std::input_or_output_iterator<I>で登場しているため、省略します。

3.4.3.3. ##3 + incrementable<T>の意味論的制約

incrementable<T>のモデルとなるためには、次を満たす必要があります。

  • 前置/後置インクリメントはどちらも等しさを保持する
    • weakly_incrementable<T>での「等しさを保持することを要求しない」の指定を上書きする形で適用される
  • a == bとなるインクリメント可能なイテレータa, bがあるとき:
    • a++ == b
      • 後置インクリメントの返り値は、インクリメント前のイテレータのコピーである
    • (a++, a) == ++b
      • 等値なイテレータのペアに片方前置、片方後置インクリメントを行ったとしても、評価後の値は等値
      • イテレータが指す「範囲」をインクリメントによって変更しない（マルチパス）
         
  • イテレータが前置/後置インクリメントが出来ることと、前置はi自身への参照を、後置はインクリメント前のiのコピーを返すことを要求しています（等しさを保持することを要求される＝マルチパス）

3.4.4. #4

sentinel_for<S, I>は、SがIのセンチネルであることを要求するコンセプトです。これは意味論的制約のために存在しており、構文的制約で新しいのはありません。

sentinel_for
namespace std {
  template<class S, class I>
  concept sentinel_for =
    // `S`が半正則（ムーブ/コピー/デフォルト構築可能）な型であることを要求
    semiregular<S> &&
    // `I`がC++20イテレータであることを要求
    input_or_output_iterator<I> &&
    // `S`と`I`の値が等値比較可能であることを要求
    weakly-equality-comparable-with<S, I>;
}

意味論的には、次を要求しています。

  • i == sが適格である（未定義動作しない）
  • iが有効な「範囲」を表す時:
    • *iが有効
    • [++i, s)も有効な「範囲」を表す
  • I&とSがstd::assignable_from<I&, S>のモデルとならない時:
    • 構文的にもstd::assignable_from<I&, S>を満たさない
    • （≒ I&とSの間に代入演算子を定義していない）
       
  • I自身がIのセンチネルとなれる（イテレータペアで「範囲」を表すことが出来る）ことを要求しています

意味論的制約も、今回の文脈だと他の場所で要求されていたりするので無視できるものばかりです。

3.4.5. std::forward_iterator<I>の意味論的制約

デフォルト構築された前方向イテレータ同士は、等値比較した時にtrueとなることが定められています。つまり、デフォルト構築した前方向イテレータは全て同じ空の「範囲」を指していると考えられます。

また、次も要求されています。

  • a == bならば++a == ++b
  • ((void)[](X x){++x;}(a), *a)は*aと等値
     
  • 同じ範囲を指すイテレータは、同じ範囲を同じ順番でイテレートし、イテレータをコピーしてから何かをしても、元のイテレータに影響はないことを要求しています。また、デフォルト構築された前方向イテレータ同士は等値比較でtrueとなることも要求されています

3.4.6. まとめ

備考:

  • Boolは、boolean-testableを満たす型（boolのように扱える型）を表します
  • const I&の部分は、コピーコンストラクタ引数を除いて、Iに変えても問題ありません
対象 要求される内容 制約関係特記 実装・備考・制約その他
I std::input_iterator<I>を満たす
イテレータコンセプトを表すタグ型がstd::forward_iterator_tagか、それを継承した型である I::iterator_conceptを定義する
I自身がIのセンチネルとなれる 特にこれによって追加される要件はない
i I() 正則の一部 これはデフォルト構築のこと
I{} == I{}はtrueとなる デフォルト構築したイテレータは全て同じ空の「範囲」を指していると考えられる
I(const I&) I& operator=(const I&) 正則の一部 これはコピー構築/代入のこと
friend Bool operator==(const I&, const I&) 正則の一部 これは等値比較のこと。C++20からはoperator!=はoperator==から自動導出される
I& operator++() & 返り値は*this 等しさを保持する（指す「範囲」を変更するような操作を行わない）
I operator++(int) & 返り値はインクリメントする前のiのコピー 等しさを保持する（指す「範囲」を変更するような操作を行わない）
同じ範囲を指すイテレーターは同じ範囲を同じ順番で走査する マルチパス保証の一部
イテレーターをコピーした場合、コピー元とコピーは互いに独立で影響しあわない マルチパス保証の一部 コピーになにか操作をしても、コピー元には影響が無い、ということ

3.5. std::bidirectional_iterator<I>

std::bidirectional_iterator<I>は、双方向イテレータという、前方向にも後ろ方向にも走査が出来るイテレータを表すコンセプトです。

bidirectional_iterator
namespace std {
  template<class I>
  concept bidirectional_iterator =
    #1
    forward_iterator<I> &&
    #2
    derived_from<ITER_CONCEPT(I), bidirectional_iterator_tag> &&
    #3
    requires(I i) {
      { --i } -> same_as<I&>;
      { i-- } -> same_as<I>;
    };
}

3.5.1. #1

始めに画像で示したように、std::bidirectional_iterator<I>はstd::forward_iterator<I>を包含していることがわかります。

  • 双方向イテレータは前方向イテレータであることを要求しています

3.5.2. #2

この部分ではイテレータのカテゴリが適切に定義されているかをチェックしています。

  • ITER_CONCEPT(I)によって取得したイテレータタグ型が、std::bidirectional_iterator_tag以上のカテゴリであることを要求しています

3.5.3. #3 + std::bidirectional_iterator<I>の意味論的制約

デクリメントが出来ることを要求しているところです。前置と後置の扱いは、インクリメントの時と同じようなものです。

  • 次を満たす時、前置/後置デクリメントは定義域にあるとする:
    • ++iter == iとなるようなイテレータiterが存在する
  • a == bとなる、デクリメント可能なイテレータa, bがあるとき:
    • std::addressof(--a) == std::addressof(a)を満たす
      • つまり、前置デクリメントの返り値は*thisである
    • a-- == b
      • 後置インクリメントの返り値は、インクリメント前のイテレータのコピーである
    • (a--, a) == --b
      • 等値なイテレータのペアに片方前置、片方後置インクリメントを行ったとしても、評価後の値は等値
    • ++(--a) == b
      • デクリメントしてインクリメントしたら操作前に戻る
  • a == bとなる、インクリメント可能なイテレータa, bがあるとき:
    • --(++a) == b
      • インクリメントしてデクリメントしても操作前に戻る
         
  • イテレータが前置/後置デクリメントが出来ることと、前置はi自身への参照を、後置はインクリメント前のiのコピーを返すこと、インクリメントとデクリメント（順不同）をすると元に戻ることを要求しています

3.5.4. まとめ

対象 要求される内容 制約関係特記 実装・備考・制約その他
I std::forward_iterator<I>を満たす
イテレータコンセプトを表すタグ型がstd::bidirectional_iterator_tagか、それを継承した型である I::iterator_conceptを定義する
I& operator--() & 返り値は*this 返り値の制約はインクリメントと同じ
I operator--(int) & 返り値はデクリメントする前のiのコピー 返り値の制約はインクリメントと同じ
--i, i-- 定義域は、インクリメントするとiになるようなイテレーターがある時である インクリメントの逆演算となることを要求しているとも言える
前の要素を指すようにイテレーターを更新する インクリメントとデクリメントする（順不同）と、操作前のイテレータと等値になる
番外 std::disable_sized_sentinel_for<I, I>をtrueに特殊化する コンセプトとは関係無い もしイテレーター同士の減算が定数時間で実行できない場合はこれをtrueに特殊化する必要がある

3.6. std::random_access_iterator<I>

std::random_access_iterator<I>は、ランダムアクセスイテレータという、両方向の走査に加えて、ランダムアクセスが可能なイテレータを表すコンセプトです。

random_access_iterator
namespace std {
  template<class I>
  concept random_access_iterator =
    #1
    bidirectional_iterator<I> &&
    #2
    derived_from<ITER_CONCEPT(I), random_access_iterator_tag> &&
    #3
    totally_ordered<I> &&
    #4
    sized_sentinel_for<I, I> &&
    #5
    requires(I i, const I j, const iter_difference_t<I> n) {
      { i += n } -> same_as<I&>;
      { j +  n } -> same_as<I>;
      { n +  j } -> same_as<I>;
      { i -= n } -> same_as<I&>;
      { j -  n } -> same_as<I>;
      {  j[n]  } -> same_as<iter_reference_t<I>>;
    };
}

3.6.1. #1

始めに画像で示したように、std::random_access_iterator<I>はstd::bidirectional_iterator<I>を包含していることがわかります。

  • ランダムアクセスイテレータは双方向イテレータであることを要求しています

3.6.2. #2

この部分ではイテレータのカテゴリが適切に定義されているかをチェックしています。

  • ITER_CONCEPT(I)によって取得したイテレータタグ型が、std::random_access_iterator_tag以上のカテゴリであることを要求しています

3.6.3. #3

totally_ordered<T>は、Tの値同士で==, !=, <, >, <=, >=で比較が出来ることと、その比較演算子による順序付けが「全順序の要件」を満たすことを要求するコンセプトです。

totally_ordered
namespace std {
  template<class T, class U>
  concept totally_ordered =
    // 等値比較可能であることを要求
    equality_comparable<T> &&
    // 比較演算子が使用可能であることを要求
    partially-ordered-with<T, T>;

  // <, >, <=, >= による 4種2方向 の比較演算子が可能であることを要求
  // 返り値は`bool`として扱える型を要求
  template<class T, class U>
  concept partially-ordered-with =
    requires(const remove_reference_t<T>& t, const remove_reference_t<U>& u) {
      { t <  u } -> boolean-testable;
      { t >  u } -> boolean-testable;
      { t <= u } -> boolean-testable;
      { t >= u } -> boolean-testable;
      { u <  t } -> boolean-testable;
      { u >  t } -> boolean-testable;
      { u <= t } -> boolean-testable;
      { u >= t } -> boolean-testable;
    };

  // `T`が`bool`として扱える型であることを表明するコンセプト（一部簡単のため変更を加えています）
  template<class T>
  concept boolean-testable =
    // `T`が`bool`に変換できることを要求
    convertible_to<T, bool> &&
    // `T`の値を論理否定する文脈での値が`bool`に変換できることを要求
    requires (T&& t) {
      { !std::forward<T>(t) } -> convertible_to<bool>;
    };
}

3.6.3.1. 全順序 in 数学

元々全順序は数学に存在する概念です。数学において、ある値の集合Xの値x, y, zについて、演算<=を定めたときに、

  • 反射律: 「x <= x」が任意のxについて成立
  • 推移律: 「x <= yかつy <= z」ならばx <= z
  • 反対称律: 「x <= yかつy <= x」ならばx == y
  • 完全律: 「x <= yまたはy <= x」が任意のx, yについて成立

の全てを満たすような演算を「全順序関係」、集合を「全順序集合」と呼びます。全順序集合に属するすべての値は、その全順序関係を満たすように一直線に並べることが出来ます。つまり、整数集合や実数集合は大小関係による演算<=による全順序集合であると言えます。

3.6.3.2. 全順序 in C++ + totally_ordered<T>の意味論的制約

C++では、Tの値a, bについて、

  • 「a < b, a > b, a == b」は何れか1つのみ成立
  • 「a < bかつb < c」ならばa < c
  • 「(a <= b) == !(a > b)」が成立
  • 「(a >= b) == !(a < b)」が成立

という意味論的制約で、数学の全順序集合を表現しています。（これがtotally_ordered<T>の意味論的制約です）

というわけで、整数型（char、int、long等）はtotally_ordered<T>を満たします。（double等浮動小数点数は、少なくともIEEE 754準拠の場合はNaNとかがあるので満たさないですね...）

3.6.3.3. イテレータの実装では

イテレータは「範囲」のどこかを指しているわけなので、1つの方法としては、イテレータが指している要素のインデックスを保持しておいて、そのインデックスによって順序付けが行えるように比較演算子を実装しておくことで満たすことが可能です。

なお、C++20では比較演算子の自動導出が存在するため、operator==とoperator<=>のみを実装すれば、自動的に他の演算が導出されます。

3.6.3.4.

  • 等値比較・比較演算が全種類（==, !=, <, >, <=, >=）可能で、その比較は全順序関係であることを要求しています

3.6.4. #4

sized_sentinel_for<S, I>は、I, Sの値i, sについて、i - s、s - iによって定数時間で距離が求められることを要求するコンセプトです。

sized_sentinel_for
namespace std {
  template<class S, class I>
  concept sized_sentinel_for =
    // ##1 `S`が`I`のセンチネルであることを要求
    sentinel_for<S, I> &&
    // ##2 意味論を満たせない場合にこれでコンセプトを満たさないようにする
    !disable_sized_sentinel_for<remove_cv_t<S>, remove_cv_t<I>> &&
    // ##3 `i - s`、`s - i`で距離を求められることを要求
    requires(const I& i, const S& s) {
      { s - i } -> same_as<iter_difference_t<I>>;
      { i - s } -> same_as<iter_difference_t<I>>;
    };
}

3.6.4.1. ##1

  • SがIに対するセンチネルであることを要求しています

3.6.4.2. ##2

disable_sized_sentinel_for<S, I>は、sized_sentinel_for<S, I>の構文的制約は満たせるけれど、意味論的制約を満たせない場合にtrueに特殊化する用途に使う、constexprなグローバル定数です。

たとえばi - sとs - iが可能だけれども、定数時間で求められないとすると、sized_sentinel_for<S, I>の意味論的制約を満たせないので、次のように特殊化することになります。

disable_sized_sentinel_for
template<>
inline constexpr bool std::disable_sized_sentinel_for<S, I> = true;
  • sized_sentinel_for<S, I>の意味論的制約を満たせるかどうかを実装者が表明することを要求しています。満たせない場合は、disable_sized_sentinel_for<S, I>をtrueに特殊化しなくてはなりません

3.6.4.3. ##3

  • s - i、i - sでイテレータとセンチネル間の距離を求められ、その返り値の型はiter_difference_t<I>と一致することを要求しています

3.6.5. #5 + std::random_access_iterator<I>の意味論的制約

インクリメント/デクリメントはイテレータが指す要素を「1だけ」次/前に移動させますが、加算減算はそれの「nだけ次/前に移動させる」（nが負の場合は逆方向に移動する）ものであると考えられます。

なお、ここで「nだけ移動する」（nは整数）を

  • n > 0のとき:
    • nだけ次へ進める
    • nだけインクリメントした場合と等値なイテレータが得られる
  • n < 0のとき:
    • nだけ前へ進める
    • nだけデクリメントした場合と等値なイテレータが得られる
  • n == 0のとき:
    • 何もしない

と定義します。この時、制約に書かれている式たちは

  • i + n, n + i, i - n:
    • iのコピーをnだけ移動（減算は-nだけ移動）して返す
    • 返り値はiをコピーして移動したもので、返り値の型はI
    • iの全て値カテゴリとconst修飾で使用可能
    • 加算がオペランドが逆でも動作するのは結合則を満たすために
  • i += n, i -= n:
    • iをnだけ移動（減算は-nだけ移動）して返す
    • 返り値はiを移動した後の*thisで、返り値の型はI&
    • iがlvalueの時だけ使用可能でいい
  • i[n]:
    • iのコピーをnだけ移動して、間接参照結果を返す
    • ということはやっぱり*(i + n)と等値な操作
    • ということは当然、返り値の型は間接参照の返り値の型と同じ型
    • iがlvalueの時だけ使用可能でいい

となります。なお、全て定数時間で実行できることも要求されます。

3.6.6. まとめ

備考:

  • Dの部分は、const D&に変えても問題ありません
  • が、Dはptrdiff_tを使用することが多く、基本的に値渡しで扱ったほうがよいです
対象 要求される内容 制約関係特記 実装・備考・制約その他
I std::bidirectional_iterator<I>を満たす
イテレータコンセプトを表すタグ型がstd::random_access_iterator_tagか、それを継承した型である I::iterator_conceptを定義する
std::disable_sized_sentinel_for<I, I>を特殊化しない 逆に、定数時間でイテレータ同士の減算が出来ないのであれば、これをtrueに特殊化しないといけない
i friend std::strong_ordering operator<=>(const I&, const I&) 全順序の一部 三方比較。これとoperator==によって、全ての比較演算子が導出される。実装はdefaultか、std::compare_strong_order_fallbackを使用するなど
全順序の要件を満たす イテレータが指す要素のインデックスなどの比較で実装されることが想定される。整数や実数（小数）は全順序。
friend D operator-(const I&, const I&) イテレーター同士の距離（符号付き）を返す 定数時間で実行できない場合は、std::disable_sized_sentinel_for<I, I>をtrueに特殊化する
I& operator+=(D) & 返り値は*this 定数時間で実行可能
friend I operator+(const I&, D) 返り値はiをコピーして移動したもの 定数時間で実行可能
friend I operator+(D, const I&) 返り値はiをコピーして移動したもの operator+の結合則を満たすために存在している。定数時間で実行可能
I& operator-=(D) & 返り値は*this 定数時間で実行可能
friend I operator-(const I&, D) 返り値はiをコピーして移動したもの 定数時間で実行可能
R operator[](D) const 返り値は*(i + n)と等値 定数時間で実行可能
番外 移動とは、「引数で与えられた回数」だけ、加算ではインクリメント、減算ではデクリメントすることと等価な演算を指す。ただし、負の値である場合は、インクリメントとデクリメントを逆転させる。 定数時間で実行可能

3.7. std::contiguous_iterator<I>

std::contiguous_iterator<I>は、隣接イテレータという、両方向の走査やランダムアクセスに加え、イテレータが指す範囲がメモリ上に連続して配置されていることが保証されているイテレータを表すコンセプトです。

contiguous_iterator
namespace std {
  template<class I>
  concept contiguous_iterator =
    #1
    random_access_iterator<I> &&
    #2
    derived_from<ITER_CONCEPT(I), contiguous_iterator_tag> &&
    #3
    is_lvalue_reference_v<iter_reference_t<I>> &&
    same_as<iter_value_t<I>, remove_cvref_t<iter_reference_t<I>>> &&
    #4
    requires(const I& i) {
      { to_address(i) } -> same_as<add_pointer_t<iter_reference_t<I>>>;
    };
}

3.7.1. #1

始めに画像で示したように、std::contiguous_iterator<I>はstd::random_access_iterator<I>を包含していることがわかります。

  • 隣接イテレータはランダムアクセスイテレータであることを要求しています

3.7.2. #2

この部分ではイテレータのカテゴリが適切に定義されているかをチェックしています。

  • ITER_CONCEPT(I)によって取得したイテレータタグ型が、std::contiguous_iterator_tag以上のカテゴリであることを要求しています

3.7.3. #3

登場する2つのメタ関数は次のようなものです。

  • is_lvalue_reference_v<T>:
    • Tがlvalue reference（&）であるかのbool値
  • remove_cvref_t<T>
    • Tにトップレベル参照やcv修飾があれば、それを外した型となるタイプエイリアス

よって次のことを要求しているとわかります。

  • referenceが、lvalue referenceな型であること
  • referenceのトップレベル参照とcv修飾を外した型が、value_typeと一致すること

ここで注意しておきたいのは、ここでのvalue_typeはstd::iter_value_t<I>で取得できる型のことを指すので、I::value_typeから取得される場合にはトップレベルcv修飾は消されることです。これに注意して言い換えると、

  • value_typeにはトップレベル参照がなく、referenceはvalue_typeのlvalue reference（const修飾は任意）であることを要求しています

3.7.4. #4

ここでは、to_addressを使用して、イテレータからアドレスが取得でき、そのアドレスの型は間接参照の結果（reference）から取得するポインタ型と一致することを要求しています。詳しく説明します。

3.7.4.1. std::to_address

std::to_addressは、C++20で追加された「ポインタと見做せる型（スマートポインタなど）」からポインタを取得する関数です。

to_address
namespace std {
  template <class PtrLike>
  constexpr auto to_address(const PtrLike& p) noexcept; // (1)

  template <class T>
  constexpr T* to_address(T* p) noexcept;           // (2)
}

(1)が（繰り返し）呼び出されることで、最終的に(2)が呼び出されることになります。(2)はただ単にポインタをポインタとして返すだけの関数で、本質は(1)にあります。

(1)は

  • std::pointer_traits<PtrLike>::to_address(p)が有効ならその値を返す
  • 上のがダメならto_address(p.operator->())を返す
  • 全部ダメなら取得失敗

という動きをします。基本的にoperator->を定義して対応することになります。（pointer_traits<PtrLike>を特殊化するよりかは遥かに楽なので...）

3.7.4.2. operator->の定義について

アロー演算子さんですが、基本的にはポインタを返すことになるでしょう。このときも、「自らのconst性」と「参照先の値のconst性」に気をつけて実装しましょう。

operator-> の例
struct A
{
	using Storage = struct
	{
		int i = 0;
	};

	Storage* operator->()
	{
		return &storage;
	}

    // 今回は、`*this`がconstなら、`storage`もconstなので2種類用意
    // 大半のイテレータの場合は1個目の方にconst修飾子をつけて、これは用意しなくていい
	const Storage* operator->() const
	{
		return &storage;
	}

private:
	Storage storage;
};

int main()
{
	A a;

    // a.operator->()->i と同じ
	a->i;
}

3.7.4.3. add_pointer_t<T>

add_pointer_T<T>は、Tの要素へのポインタの型を取得するメタ関数です。具体的には、Tが参照であればそれを除去し、それへのポインタの型を定義します。

参照はオブジェクトではない（メモリ上に存在しないかもしれない）ので、参照それ自体のアドレスは取れません。というわけで、参照の場合は参照先のオブジェクトへのアドレスを取るのが適当である、というわけです。

#3 の制約も鑑みれば、(const) value_type*（ここでの丸括弧は、constがあってもなくてもよいの意味）であることがわかります。

3.7.4.4

  • std::to_addressを通じて要素のポインタを取得できることと、そのポインタの型はadd_pointer_t<reference>による型（（const）value_type*）を要求しています。現実的にはアロー演算子を実装することで対応します。

3.7.5. std::contiguous_iterator<I>の意味論的制約

隣接イテレータは、そのイテレータが指す「範囲」がメモリ上で連続していることを保証する「メモリ連続性の保証」がされているイテレータでした。なので、意味論的制約ではメモリ連続性についての制約が要求されています。

3.7.5.1. 例: メモリ連続性とstd::deque<T>、std::vector<T>

ランダムアクセスが可能な標準ライブラリにある汎用コンテナとしてはstd::deque<T>とstd::vector<T>が有名です。これらのコンテナを考えてみましょう。

一見すると差がわからないかもしれませんが、この2つのコンテナはメモリ確保の仕方が異なり、std::deque<T>::iteratorはランダムアクセスイテレータ止まりですが、std::vector<T>::iteratorは隣接イテレータにまでカテゴライズされます。

そんなこれら2つのコンテナの特徴としては次のようなものがあります。

  • std::deque<T>:
    • ある程度の数の要素を一纏めにした「チャンク」をメモリ上で分割配置
    • それぞれのチャンクに関してはメモリ上の連続した領域に配置される
    • 確保済みメモリが足りない時は、チャンク1つ分だけメモリを確保する
    • チャンクを増やす分のメモリ確保だけをすれば良いので負荷は少なめ
    • ただしアクセス時にはチャンクを考慮した計算をするので多少の負荷
  • std::vector<T>:
    • 全ての要素をメモリ上の連続した領域に保存する
    • 確保済みメモリが足りない時は、更に大きなメモリ領域を確保する
    • 全領域を別のメモリに再配置することになるとそれなりの負荷がかかる
    • ただしアクセス時にはアドレス演算を1回するだけで良いので軽い

vector_deque.png

図: 筆者作成（CC-BY）

このように、std::deque<T>の持つ要素はメモリ上に分散されて配置されることがあり、必ずしもメモリ上で連続せず、std::deque<T>::iteratorは隣接イテレータの要件を満たしません。

3.7.5.2.

間接参照可能（≒範囲内のメモリアドレスを指している）イテレータa, bと、間接参照不可能（≒範囲外のメモリアドレスを指している）イテレータcがあり、aからb、bからcへと進行可能であるとします。その時に、difference_typeをDとして、次の式が成り立つことを要求しています。

  • to_address(a) == addressof(*a)
  • to_address(b) == to_address(a) + D(b - a)
  • to_address(c) == to_address(a) + D(c - a)

addressofは、オブジェクトのアドレスを取得する関数です。operator&がオーバーロードされているオブジェクトに対してもアドレスが取得できるようになっています。

  • 「to_addressによって取得できるアドレス」と「間接参照が返すオブジェクトのアドレス」が一致し、イテレータに対する移動操作と、アドレスに対する移動演算が一致することを要求しています

3.7.6. まとめ

対象 要求される内容 制約関係特記 実装・備考・制約その他
I std::random_access_iterator<I>を満たす
イテレータコンセプトを表すタグ型がstd::contiguous_iterator_tagか、それを継承した型である I::iterator_conceptを定義する
i T operator->() const Tはstd::to_addressで、型std::add_pointer_t<R>の値が取れる型であればよい std::addressof(*i)を返すなどすればいい。なお、これの実装の代わりにstd::pointer_traits<I>を特殊化することでも対応可能。
std::to_address(i)とstd::addressof(*i)が一致する operator->がstd::addressof(*i)を返していれば自然と一致する
イテレーターに対する移動操作と、アドレスに対する移動演算が一致する イテレータがポインタのラッパーのようなもので、イテレータの各値はアドレスと対応しているということになる
V トップレベル参照が存在しない トップレベルcv修飾は、I::value_typeを定義している場合には、std::iter_value_t<I>で取得される途中で除去される
R V&かconst V&である ということはstd::add_pointer_t<R>の結果は、Rのconstによって、V*かconst V*になる

3.8. std::output_iterator<I, Val>

std::output_iterator<I, Val>は、出力イテレータという、Valのシーケンスを出力するのに使えるイテレータを表すコンセプトです。

output_iterator
namespace std {
  template<class I, class Val>
  concept output_iterator =
    #1
    input_or_output_iterator<I> &&
    #2
    indirectly_writable<I, Val> &&
    #3
    requires(I i, Val&& val) {
      *i++ = std::forward<Val>(val); // 等しさを保持することを要求しない
    };
}

3.8.1. #1

始めに画像で示したように、std::output_iterator<I, Val>はstd::input_or_output_iterator<I>を包含していることがわかります。

  • 出力イテレータはC++20イテレータであることを要求しています

3.8.2. #2

indirectly_writable<Out, T>は、Outのインスタンスを間接参照した返り値に対してTを書き込めることを要求するコンセプトです。スマートポインタなどもこのコンセプトのモデルになることが出来ますが、イテレータの場合のみ考えます。

indirectly_writable
namespace std {
  template<class Out, class T>
  concept indirectly_writable =
    // 以下全て、等しさを保持することを要求しない 
    requires(Out&& o, T&& t) {
      *o                                                          = forward<T>(t);
      *forward<Out>(o)                                            = forward<T>(t);
      const_cast<const iter_reference_t<Out>&&>(*o)               = forward<T>(t);
      const_cast<const iter_reference_t<Out>&&>(*forward<Out>(o)) = forward<T>(t);
    };
}

3.8.2.1. 書かれている式4つ

requires式に書かれている4つの式は細かいことを考えなければ、全て間接参照した返り値に対して、Tの値を書き込み（代入）が出来ることを要求しています。

2つ目と4つ目の式は「イテレータがrvalueであっても間接参照・書き込みが出来ること」を要求していて、3つ目と4つ目の式は「間接参照の返り値はconstであっても書き込み可能であること」を要求しています。これは、プロキシイテレータだけがこのコンセプトを満たすために書かれています。（この後説明します）

式 間接参照時のo 書き込み操作時の間接参照の返り値
1つ目 lvalue non-const
2つ目 rvalue non-const
3つ目 lvalue const
4つ目 rvalue const

3.8.2.2. プロキシイテレータ

プロキシは英語で「代理」などと言う意味があります。

イテレータの文脈におけるプロキシイテレータは、あるイテレータの間接参照時に、そのイテレータが指す要素を直接返すのではなく、その要素のように振る舞う別の型の値を返すようなものを指します。

また、その「間接参照したときに返す値」のことは、プロキシオブジェクトなどと呼びます。プロキシオブジェクトは特別に設計されたクラスのことや、イテレータそれ自身であることもあります。

3.8.2.3. 例: std::vector<bool>::iterator（C++23）

std::vector<T>は何故か9boolのときだけ特殊化されていて、boolの配列としてではなく、bitの配列のように振る舞います。つまり、各要素は実際には1bitしかメモリを専有しないように設計されています。

しかし、C++の型の最小単位はchar やbool10 の1Byteです。間接参照の返り値で1bitを返すことなんて出来ません。そこで、次のようなプロキシオブジェクトが該当の1bitとのやり取りを中継することになっています。

vector(bool)の reference（C++23）
class reference {
  friend class vector;
  constexpr reference() noexcept;
public:
  constexpr reference(const reference&) = default;
  constexpr ~reference();

  // `bool`への暗黙変換
  constexpr operator bool() const noexcept;

  // `bool`からの代入
  constexpr reference& operator=(bool x) noexcept;
  constexpr reference& operator=(const reference& x) noexcept;

  // このクラス自体がconstでも、書き込みは出来る
  constexpr const reference& operator=(bool x) const noexcept;

  // flipする（0と1を入れ変える）
  constexpr void flip() noexcept;
};

boolへの暗黙変換や、boolからの代入が可能になっており、boolのように扱えることがわかります。また、このオブジェクト自体がconstであったとしても書き込みが可能です（これはプロキシオブジェクトの性質です）。このオブジェクトへの書き込み操作は、このオブジェクトが指し示す1bitの領域への書き込みとして処理されることになります。

ちなみに（C++20）

実のところ、C++20ではこのプロキシオブジェクトは何故かconstの時に書き込みが出来ません。ということは、

  • std::indirectly_writable<std::vector<bool>::iterator, bool>
  • std::output_iterator<std::vector<bool>::iterator, bool>

のどちらも満たされません...（制約を守れていない）どうしてこんなことに。C++23においては、std::ranges::zip_viewの提案（P2321R2 zip）によって修正されました。

vector(bool)のプロキシイテレータの reference（C++20）
class reference {
  friend class vector;
  constexpr reference() noexcept;
public:
  constexpr reference(const reference&) = default;
  constexpr ~reference();

  // `bool`への暗黙変換
  constexpr operator bool() const noexcept;

  // `bool`からの代入
  constexpr reference& operator=(const bool x) noexcept;
  constexpr reference& operator=(const reference& x) noexcept;

  // このクラス自体がconstでも、書き込みが出来...出来ない！？

  // flipする（0と1を入れ変える）
  constexpr void flip() noexcept;
};

3.8.2.4. 復習（？）: ポインタとconstの関係

プロキシオブジェクトがconstでも書き込み可能なことを理解するために、ポインタとconstの関係を思い出してみましょう。

ポインタとconst
int a, b;

// constの付け方は4つあった
      int*       _1 = &a; // `int`      へのポインタ
const int*       _2 = &a; // `const int`へのポインタ
      int* const _3 = &a; // `int`      への「constなポインタ」
const int* const _4 = &a; // `const int`への「constなポインタ」

{
    // `int`へのポインタ
    int* p = &a;

    *p = 0;  // ok: 参照先の変数（間接参照で得た変数）の変更
     p = &b; // ok: 参照する変数（自らが持つアドレス）の変更
}

{
    // `const int`へのポインタ
    const int* p = &a;

//	*p = 0;  // ng: 参照先の変数（間接参照で得た変数）の変更
     p = &b; // ok: 参照する変数（自らが持つアドレス）の変更
}

{
    // `int`への「constなポインタ」
    int* const p = &a;

    *p = 0;  // ok: 参照先の変数（間接参照で得た変数）の変更
//	 p = &b; // ng: 参照する変数（自らが持つアドレス）の変更
}

{
    // `const int`への「constなポインタ」
    const int* const p = &a;

//	*p = 0;  // ng: 参照先の変数（間接参照で得た変数）の変更
//	 p = &b; // ng: 参照する変数（自らが持つアドレス）の変更
}

ポインタは、

  • 自らのconst性
    • 参照する変数（＝自らの持つアドレス）を変更できるか
  • 参照先のconst性
    • 参照先の変数（＝間接参照して得た変数）を変更できるか

の2種類のconst性がありました。思い出せたでしょうか。

例としてintへのポインタについて 自らのconst性なし 自らのconst性あり
参照先のconst性なし int* int* const
参照先のconst性あり const int* const int* const

3.8.2.5. 普通のオブジェクトとプロキシオブジェクトとconst

ここまでの話から 「プロキシオブジェクト自体がconst」であるということは、「自らのconst性」を持っていても「参照先のconst性」を持っていないことがわかってもらえたかと思います。

というわけで、「プロキシオブジェクト自体がconst」であっても「参照先への書き込み」は可能なのです。（尤も、ムーブ/コピー代入に関しては、プロキシオブジェクト自体を変更するので不可能ですが）

さて、対照的に普通のオブジェクトについても考えてみましょう。普通のオブジェクトは特に何かの参照というわけではなく、自らで値を保持しています。そのような 「普通のオブジェクトがconst」である場合は「自らのconst性」によって値（自らが持っている）が変更できなくなるので、書き込みは不可能ということになります。

3.8.2.6. std::indirectly_writable<Out, Val>の意味論的制約

std::indirectly_writable<Out, Val>のモデルとなるには、式Eと、decltype((E))の型となるVal、std::dereferenceableな型Outのオブジェクトoについて次を満たす必要があります。

  • indirectly_readable<Out> && same_as<iter_value_t<Out>, decay_t<Val>>を満たす場合
    • 制約式の4式のどれかで出力をした後、*oはEと等値になる
    • ただし、書き込み後のoは間接参照出来る必要はない

なお、ここで登場したdecay_t<T>は、関数テンプレートにおける値渡し（仮引数がT）で推論される型Tを定義するもので、

  • 左辺値から右辺値への変換
  • 配列からポインタへの縮退
  • 関数からポインタへの縮退

を適用した後の型を定義するタイプエイリアスです。

  • ちゃんとプロキシイテレータ及びプロキシオブジェクトによって書き込み操作が出来ることを要求しています

3.8.3. #3 + std::output_iterator<I, Val>の意味論的制約

式Eとdecltype((E))の型となるValを考えて、*i++ = Eについて考えます。

  • 演算子の結合順位で考えると:
    • *(i++) = Eと等価です。
  • 意味論的制約では:
    • *i = E; ++i;と等価であるように要求されます。
       
  • 後置インクリメントしてから間接参照して書き込みを行うのが、間接参照して書き込んでから前置インクリメントを行うのと等価であることを要求しています

3.8.4. まとめ

対象 要求される内容 制約関係特記 実装・備考・制約その他
I std::input_or_output_iterator<I>を満たす
i P operator*() 等しさを保持しなくてよい。自身をプロキシオブジェクトとして返すこともある
p auto operator=(/*Valを受け取れる型*/) const プロキシオブジェクト自身がconstでも書き込みができる イテレータ自身がプロキシオブジェクトなら、ここで、書き込み+次の要素へと進めることになることも
*i++ = e *i = e; ++iと等価 コピーできないイテレータの場合は、インクリメントで「何もせず*thisを返す」などして実現する

3.9. const_iteratorの場合

const_iteratorは間接参照した値に書き込みが出来ないので、当然出力イテレータにはなりません。ただし、入力イテレータ以上の場合なら実装することが必要であるかもしれません。

const_iteratorの実装の注意点としては

  • const_iterator用のコンセプトは存在しない
    • 普通のイテレータコンセプトを満たせばOK
    • 出力イテレータにはなれないのには注意
  • 間接参照の返り値によって、指す要素を変更できないようにする
    • int&ならconst int&
    • int*ならconst int*
    • などなど
  • const_iteratorは普通のイテレータからも構築できるようにする
    • const性が強くなる分には問題ないため

くらいです。なお、reverse_iteratorに関しては、隣接イテレータ以上であれば自動的にstd::reverse_iteratorで実現可能になります。

なお、const_iteratorの実装は、通常のイテレータとほとんどが共通のコードになるので、boolを非型テンプレート引数で受け取ってrequires節を使用して制約等することで、最小限のコード量で実装出来ます。

インタフェースだけ例として紹介しておくと、次のようになります。

const_iteratorのインタフェースだけ紹介
#include <iterator>
#include <type_traits>
#include <compare>
#include <cstddef>

// 隣接イテレータ
template <bool IsConst>
struct iterator
{
	template <bool>
	friend class iterator;

	// `I::value_type`で定義しているので、const がついても特に問題にならない
	// C++17 のイテレータに準拠させようとするとまずいかも。
	// その場合は`reference`の方で条件分岐して、それを間接参照の返り値にすればいい。
	using value_type       = std::conditional_t<IsConst, const int, int>;
	using difference_type  = ptrdiff_t;
	using iterator_concept = std::contiguous_iterator_tag;

	using I = iterator;
	using D = difference_type;

    // 任意のコンストラクタを定義すると
    // デフォルトコンストラクタが暗黙定義されなくなるので定義する
	iterator();

	// clang-format off
    // `IsConst`が`true`のときだけ定義される
	iterator(iterator<!IsConst>&&) noexcept requires IsConst;
	iterator(const iterator<!IsConst>&) requires IsConst;
	// clang-format on

	// clang-format off
    // `IsConst`が`true`のときだけ定義される
	I& operator=(iterator<!IsConst>&&) noexcept requires IsConst;
	I& operator=(const iterator<!IsConst>&) requires IsConst;
	// clang-format on

	value_type& operator*() const;
	value_type& operator[](D) const;
	value_type* operator->() const;

	I& operator++();
	I  operator++(int);

	// `std::strong_ordering`は全順序に準拠していることを表明している
	// 実装では`std::compare_strong_order_fallback`を使うといいかも
	// <compare> のインクルードが必要なことに注意
	friend bool                 operator==(const I&, const I&);
	friend std::strong_ordering operator<=>(const I&, const I&);

	I& operator--();
	I  operator--(int);

	friend D operator-(const I&, const I&);

	I&       operator+=(D);
	friend I operator+(const I&, D);
	friend I operator+(D, const I&);

	I&       operator-=(D);
	friend I operator-(const I&, D);
};

static_assert(std::contiguous_iterator<iterator<true>>);
static_assert(std::contiguous_iterator<iterator<false>>);

// clang-format off
static_assert(requires(
	iterator<false> a, 
	iterator<true> b
) {
	// 構築・代入
	iterator<true>{a};
	iterator<true>{std::move(a)};
	b = a;
	b = std::move(a);
});

4. あとがき

すごい頑張って書きました。これ、実は22年の1～2月に着手はしてたんですが、放置してたのでやっと完成できたなぁ、という感じです（）
分からない点・間違っていそうな点・教えて欲しいことなどあれば、コメントかTwitterのDMまでお知らせください。

ちなみに、まとめの表だけにしたC++20イテレータの制約一覧表もあります。是非便利にお使いください！（QVT）

5. 参照

  1. C++17までは「センチネル」という概念は無く、範囲を表すときには必ずイテレータペア（1つのイテレータ対）で表現していました。 ↩

  2. メンバ関数begin/endが必ずしもあるわけではない（生配列など）ので、あくまでもstd::ranges::begin/endを使うのがおすすめです。 ↩

  3. 実はstd::vector<bool>の場合だけ、色々あってイテレータは隣接イテレータを満たしません。 ↩

  4. [Twitterの方で高画質なのを置いてあります]
    (https://twitter.com/tomosann_tomo/status/1488569493236649985) ↩

  5. 参照で取ってもダメではないと思いますが、標準ライブラリでイテレータ/センチネルを渡しているところはみんな値渡しです。参照にする必要性ないですし、基本的に実装は面倒くさくなる筈です。（forwarding referenceの時は、参照を取った型をコンセプトに渡す必要があったりしますし...） ↩

  6. P2325R3「Views should not be required to be default constructible」がC++20へDRとして採択されたので、default_initializable<T>は削除されました。 ↩

  7. ムーブ構築/代入が可能であるという性質から、スワップ操作が可能であることも要求されます。普通はムーブ構築/代入でスワップ操作が実装されるので問題は起こりません。 ↩

  8. 普通ptrdiff_tを使います ↩

  9. 確かにboolは1byteのメモリを専有するので多少無駄があることは同意出来ますが、この特殊化のせいで、std::vector<bool>::iteratorだけ隣接イテレータを満たさなくなるし、あまりに罠で初心者殺しです... ↩

  10. boolのサイズは定まってないだということです。（定まっていると思い込んでた。） ↩

31
24
6

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
31
24

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?