C++20標準ライブラリ std::ranges::subrange のひみつ

C++2a(C++20)標準ライブラリ入りが予定されている「範囲(Ranges)ライブラリ」のうち、クラステンプレート宣言がやたら入り組んでいる `std::ranges::subrange` を（ちょっとだけ）分解してみるお話です。

本記事では2019年6月現在のC++仕様草案 [N4810][n4810] を参照します。

2020年9月追記：C++2a仕様の最終ドラフト [N4861][n4861] では、`std::ranges::subrange` クラステンプレートの意味論は変わっていませんが、同クラステンプレート定義で利用するコンセプト名は変更されています。


# 範囲ライブラリ

C++2aで新たに標準入りした範囲ライブラリによって、従来C++標準ライブラリで提供されていたイテレータ(_Iterator_)よりも便利で安全なコード記述が可能となります（なるはずです）。単純化した説明では、これまではイテレータのペアとして表現せざるを得なかった “範囲(_Range_)” を、単一オブジェクトで表現できるようになります。本記事ではこれ以上深入りしません。

```c++:c++2a範囲ライブラリの利用例
#include <iostream>
#include <vector>
#include <ranges>
namespace view = std::ranges::view;

auto ints = std::vector{0, 1, 2, 3, 4, 5};
auto even = [](int i){ return 0 == i % 2; };
auto square = [](int i) { return i * i; };
for (int i : ints | view::filter(even) | view::transform(square)) {
  std::cout << i << ' ';  // 0 4 16 を出力
}
```

本記事で取り上げる `std::ranges::subrange` クラステンプレート（以下`subrange`）は範囲ライブラリの一部として定義されます[^range.subrange]。ただし通常のC++アプリケーションプログラマが直接利用するクラスというよりも、`std::ranges::search`関数などの探索系アルゴリズムが返す「部分範囲(_subrange_)」表現のためにライブラリ実装者が利用するクラスです。

2020年9月追記：`std::ranges::subrange` クラステンプレートは、C++17現在のイテレータ・ペアからC++2aの範囲(_Range_)へ変換するアダプタとしても利用できます。

[^range.subrange]: [range.subrange]/p1: "The `subrange` class template combines together an iterator and a sentinel into a single object that models the `View` concept. Additionally, it models the `SizedRange` concept when the final template parameter is `subrange_kind::sized`."


# subrangeクラステンプレート

C++2a標準ライブラリにおける `subrange` クラステンプレート宣言は下記コードの通りです。<del>なんて分かりやすい！</del>

```cpp:C++2a(N4810)
namespace std::ranges {
  template<Iterator I, Sentinel<I> S = I, subrange_kind K =
      SizedSentinel<S, I> ? subrange_kind::sized : subrange_kind::unsized>
    requires (K == subrange_kind::sized || !SizedSentinel<S, I>)
  class subrange : public view_interface<subrange<I, S, K>> {
    /*...*/
  };
}
```

C++2a言語仕様で新たに導入される [コンセプト(Concepts)][concepts] に関する前提知識がないと全くの意味不明、むしろ知識があっても記号の羅列にしか見えないかもしれません。


# subrangeクラステンプレート w/o コンセプト

ひとまずコンセプトに関する構文を無視して、C++17現在の言語機能のみで表現してみましょう。

```cpp:C++17相当（requires節を削除）
namespace std::ranges {
  template<class D> class view_interface;
  enum class subrange_kind : bool { unsized, sized };

  template<class I, class S = I, subrange_kind K = /*...*/>
  class subrange : public view_interface<subrange<I, S, K>> {
    /*...*/
  };
}
```

だいぶスッキリしました。`subrange` クラステンプレートは3個のテンプレートパラメータ`I`, `S`, `K`をとり、2番目の型パラメータ`S`と3番目の非型パラメータ`K`にはデフォルト値が指定されています。

- `I` = イテレータ型
- `S` = [番兵][sentinel]型（通常はイテレータ型`I`に等しい）
- `K` = 部分範囲の長さが有界(`sized`)か否か(`unsized`)を表す定数（通常は`sized`）

`subrange` は自身をテンプレート引数に指定した基底クラス `view_interface<subrange<I, S, K>>` から派生する[CRTPイディオム][crtp]を利用しています。`view_interface<D>` から継承したクラスは “`View`オブジェクト[^view.interface]”、つまり “軽量な範囲(`Range`)オブジェクト[^range.req.general]” として扱えるようになります。本記事ではこれ以上深入りしません（2回目）。

[^view.interface]: [view.interface]/p1: "The class template `view_interface` is a helper for defining `View`-like types that offer a container-like interface."
[^range.req.general]: [range.req.general]/p2: "The `View` concept specifies requirements on a `Range` type with constant-time copy and assign operations."


# subrangeクラステンプレート w/ コンセプト

あらためてC++2a標準ライブラリに立ち返りつつ、`subrange` クラステンプレートから参照される3つのコンセプト(`Iterator`, `Sentinel`, `SizedSentinel`)も引用しておきます。

```cpp:C++2a(N4810)
namespace std {
  template<class I> concept Iterator = /*...*/;
  template<class S, class I> concept Sentinel = /*...*/;
  template<class S, class I> concept SizedSentinel = /*...*/;
}
namespace std::ranges {
  template<class D> class view_interface;
  enum class subrange_kind : bool { unsized, sized };

  template<Iterator I, Sentinel<I> S = I, subrange_kind K =
      SizedSentinel<S, I> ? subrange_kind::sized : subrange_kind::unsized>
    requires (K == subrange_kind::sized || !SizedSentinel<S, I>)
  class subrange : public view_interface<subrange<I, S, K>> {
    /*...*/
  };
}
```

テンプレートパラメータリスト部でのコンセプト指定（`template<C T>`）は、「テンプレートパラメータ型`T`がコンセプト`C<T>`を満たす」ことを表現しており、requires節を用いた`template<class T> requires C<T>`と同義です。

つまり `subrange` クラステンプレートは、テンプレートパラメータが下記3つの制約(_constraints_)を満たすときに限ってインスタンス化されます。

- 型テンプレートパラメータ `I` が `Iterator<I>` コンセプトを満たし、かつ
- 型テンプレートパラメータ `S` が `Sentinel<S, I>` コンセプトを満たし、かつ
- 非型テンプレートパラメータ `K` == `sized` もしくは `SizedSentinel<S, I>` コンセプトを満たさないとき。
 - 非型テンプレートパラメータ `K` のデフォルト値は、`SizedSentinel<S, I>` コンセプトを満たす場合は `sized` を、そうでなければ `unsized` をとる。

これで `subrange` クラステンプレート宣言を解釈できるようになりましたよね？本記事ではこれ以上深入りしません（3回目）


[n4810]: https://wg21.link/n4810
[n4861]: https://wg21.link/n4861
[concepts]: https://yohhoy.hatenadiary.jp/entry/20170904/p1
[crtp]: https://ja.wikibooks.org/wiki/More_C%2B%2B_Idioms/%E5%A5%87%E5%A6%99%E3%81%AB%E5%86%8D%E5%B8%B0%E3%81%97%E3%81%9F%E3%83%86%E3%83%B3%E3%83%97%E3%83%AC%E3%83%BC%E3%83%88%E3%83%91%E3%82%BF%E3%83%BC%E3%83%B3(Curiously_Recurring_Template_Pattern)
[sentinel]: https://ja.wikipedia.org/wiki/%E7%95%AA%E5%85%B5