可変引数テンプレートと再帰テンプレートの洗礼

## ことの発端

可変引数テンプレートに渡した最初の```N```個を```std::tuple```にしたいという話の続きです。

https://qiita.com/terukazu/items/f3218b613b13dcd0fdc1

具体的にはこんなことをやりたいわけです。

```cpp
using x = pick<2, int, double, int*, double*>;
/* x = std::tuple<int, double> */
```

当初はマクロで```N```を 0 〜 10 まで作るなんてアホはコードになっていたのですが、別の記事で神様が降臨されまして、私めに```再帰テンプレート```という技を教えていただきました。

https://qiita.com/terukazu/items/7332bad136e0ff207db8

こりゃ、「```pick```も再帰テンプレートにしなきゃ！」ということで内心盛り上がり、遠足前の小学生並みに寝付けなかったのですが、実際やってみたら、躓いたというお話です。

## 失敗の巻

```cpp
template <std::size_t, std::size_t, typename ...> struct pick_impl;

/* I < N まで再帰を続ける */
template <std::size_t N, std::size_t I, typename ...TPARGS, typename T, typename ...ARGS>
  struct pick_impl<N, I, std::tuple<TPARGS...>, T, ARGS...> :
    pick_impl<N, I + 1, std::tuple<TPARGS..., T>, ARGS...> {};

/* I == N になったら終了 */
template <std::size_t N, typename ...TPARGS, typename ...ARGS>
  struct pick_impl<N, N, std::tuple<TPARGS...>, ARGS...>
{
  using types = std::tuple<TPARGS...>;
  using after = std::tuple<ARGS...>;
};

template <std::size_t N, typename ...ARGS>
  struct pick :
    pick_impl<N, 0, std::tuple<>, ARGS...> {}; /* ここからスタート */
```

おそらく、テンプレートの達人なら初見で「こりゃアカン」ってなるんでしょうね。。。
で、具体的にエラーを見てみると、

```
[build] /workspaces/asyncfn_util/main.cpp:8:10: error: ambiguous template instantiation for 'struct pick_impl<2, 2, std::tuple<int, double>, void*, void*>'
[build]    struct pick_impl<N, I, std::tuple<TPARGS...>, T, ARGS...> :
[build]           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
[build] /workspaces/asyncfn_util/main.cpp:8:10: note: candidates are: template<long unsigned int N, long unsigned int I, class ... TPARGS, class T, class ... ARGS> struct pick_impl<N, I, std::tuple<_Tail ...>, T, ARGS ...> [with long unsigned int N = 2; long unsigned int I = 2; TPARGS = {int, double}; T = void*; ARGS = {void*}]
[build] /workspaces/asyncfn_util/main.cpp:12:10: note:                 template<long unsigned int N, class ... TPARGS, class ... ARGS> struct pick_impl<N, N, std::tuple<_Elements ...>, ARGS ...> [with long unsigned int N = 2; TPARGS = {int, double}; ARGS = {void*, void*}]
```

これじゃ分かりにくいので、エディタで整理してみると。。。

```
ambiguous template instantiation for
'struct pick_impl<2, 2, std::tuple<int, double>, void*, void*>'

candidates are:

template<long unsigned int N, long unsigned int I, class ... TPARGS, class T, class ... ARGS>
struct pick_impl<N, I, std::tuple<_Tail ...>, T, ARGS ...>
[with long unsigned int N = 2; long unsigned int I = 2; TPARGS = {int, double}; T = void*; ARGS = {void*}]

template<long unsigned int N, class ... TPARGS, class ... ARGS>
struct pick_impl<N, N, std::tuple<_Elements ...>, ARGS ...>
[with long unsigned int N = 2; TPARGS = {int, double}; ARGS = {void*, void*}]
```
予想以上に分かりやすいエラーメッセージ！
ふむ、２つのテンプレートでどっちを採用して良いか分からんという事みたいで、定義をよ〜〜〜く見てみると...

```cpp
struct pick_impl<N, I, std::tuple<TPARGS...>, T, ARGS...>
```

```cpp
struct pick_impl<N, N, std::tuple<TPARGS...>, T, ARGS...>
```

なるほど、どちらも型が同じですね。
確かに ```N, N``` と ```N, I``` で条件分けできそうな気がしてましたが、今回のケースでは```2, 2```はどちらも適用できるでしょうね。。。
そして、```N, N```で「やりきっちゃってる感」が出ちゃっているも問題かと。。。つまり、```types```が確定してしまう、と。

## 解決方法を想定

こんな状況になると、実装系であればガチャガチャやって挙動を見るなんていうのも時にはアリなんだが、メタプログラミングとなると、きっちり状況を把握してから、対策をしないといつまでたっても終わらないように思える。
で、考えた解決方法は、

* 再帰テンプレートにおいては、全パラメータ処理をするまで再帰を終了しちゃダメじゃないか？（予想）
* 「```N```未満と```std::tuple```」 と 「```N```以上の```std::tuple```」 を作り込むべく再帰する。
* 「```N```未満と```std::tuple```」 と 「```N```以上の```std::tuple```」 は区別して、各々特殊化しなきゃダメだな。
* そこで、```std::tuple<>``` という表現が特殊化で判定されるかは賭け。（この時点では書かなきゃ確信できない状況）
* ```std::tuple<ARGS...>```だとARGSが0個以上だから、1個以上を表現するなら```std::tuple<T, ARGS...>```ってやらなきゃダメだろうな。
* 全てのパラメータを処理したら、「```N```未満と```std::tuple```」 と 「```N```以上の```std::tuple```」を```using``` で定義して終了とする。

こんな感じで、コードを書き直してみました。

## 成功の巻

```cpp
template <std::size_t, std::size_t, typename ...> struct pick_impl;

/* I < N */
template <std::size_t N, std::size_t I, typename ...FARGS, typename T, typename ...ARGS>
  struct pick_impl<N, I, std::tuple<FARGS...>, std::tuple<>, T, ARGS...> :
    pick_impl<N, I + 1, std::tuple<FARGS..., T>, std::tuple<>, ARGS...> {};

/* I > N */
template <std::size_t N, std::size_t I, typename ...FARGS, typename BT, typename ...BARGS, typename T, typename ...ARGS>
  struct pick_impl<N, I, std::tuple<FARGS...>, std::tuple<BT, BARGS...>, T, ARGS...> :
    pick_impl<N, I + 1, std::tuple<FARGS...>, std::tuple<BT, BARGS..., T>, ARGS...> {};

/* I == N */
template <std::size_t N, typename ...FARGS, typename T, typename ...ARGS>
  struct pick_impl<N, N, std::tuple<FARGS...>, std::tuple<>, T, ARGS...> :
    pick_impl<N, N + 1, std::tuple<FARGS...>, std::tuple<T>, ARGS...> {};

/* 全てのパラメータ処理 */  
template <std::size_t N, std::size_t I, typename ...FARGS, typename ...BARGS>
  struct pick_impl<N, I, std::tuple<FARGS...>, std::tuple<BARGS...>>
{
  using types = std::tuple<FARGS...>;
  using after = std::tuple<BARGS...>;
};

template <std::size_t N, typename ...ARGS>
  struct pick :
    pick_impl<N, 0, std::tuple<>, std::tuple<>, ARGS...> {}; /* ここからスタート */
```

動作確認もOKでした〜
神様の降臨時は ```omit``` という、可変引数テンプレートの特定のパラメータを消去した ```std::tuple``` を作るものでして、「今回の ```pick``` はそれより簡単じゃん」と思ったら、火傷したという話でした。

## 戒め

いつまでも無課金ユーザではダメだと悟り、「C++テンプレートテクニック」をボチりました。

## 神様からのお告げ　（2021/03/09 追記）

またも神様からのお告げがありました。

「そなたには```std::conditional```を授けよう」

そして、そのコードを見るなり

「！！！」

でした。
何に驚いたかって、コード量が少ないということより、メタプログラミング中に条件式的なのが導入されているって事でした。
普通なら```std::conditional```の仕様を調べるんでしょうが。。。
何でしょう。。。この```std::conditional```って、どうやっているんだと考え始めて。。。
「あ～、多分 true / false で部分特殊化やってるな」と思ったんです。
あ、まだ答え合わせしてませんのでコメントで答え書かないでくださいね。（苦笑）
で、```std::conditional```を使う前に、もうちょい捻ってみようかと思った次第です。
あと、神様にお告げするのを忘れていたのですが、後ろから ```N```個を取ってくる ```pick_r``` も欲しくって、イメージ的に ```pick``` と ```pick_r``` を別々に書かなきゃならんかと想像してみたり。。。
ということで。。。

神様ごめんなさい。

遠回りですが、もう少し楽しませてください。（笑）
（最後は```std::conditional```になるのがオチかと思いますが）

## 捻ってみた（その１）

まず、こんなイメージが頭を過りました。

```cpp
template <std::size_t N, bool bAdd, typename ...TPARGS, typename T, typename ...ARGS>
  struct pick_impl<N, N, bAdd, std::tuple<TPARGS...>, T, ARGS...> :
    pick_impl<N, N + 1, !bAdd, std::tuple<TPARGS..., T>,  ARGS...> {};
```

非型パラメータの ```bAdd``` を導入して、追加するかしないかを判定してみようかと。
で、ポイントとしては、```N == N``` の時に bAdd を反転して再帰させる的な。

## 書いてみた（その１）

```cpp
template <std::size_t N, std::size_t I, bool bAdd, typename ...T> struct pick_impl;

/* I != N && bAdd */
template <std::size_t N, std::size_t I, typename ...TPARGS, typename T, typename ...ARGS>
  struct pick_impl<N, I, true, std::tuple<TPARGS...>, T, ARGS...> :
    pick_impl<N, I + 1, true, std::tuple<TPARGS..., T>, ARGS...> {};

/* I != N && !bAdd */
template <std::size_t N, std::size_t I, typename ...TPARGS, typename T, typename ...ARGS>
  struct pick_impl<N, I, false, std::tuple<TPARGS...>, T, ARGS...> :
    pick_impl<N, I + 1, false, std::tuple<TPARGS...>,  ARGS...> {};

/* I == I && !bAdd */
template <std::size_t N, typename ...TPARGS, typename T, typename ...ARGS>
  struct pick_impl<N, N, false, std::tuple<TPARGS...>, T, ARGS...> :
    pick_impl<N, N + 1, true, std::tuple<TPARGS..., T>,  ARGS...> {};

/* I == I && bAdd */
template <std::size_t N, typename ...TPARGS, typename T, typename ...ARGS>
  struct pick_impl<N, N, true, std::tuple<TPARGS...>, T, ARGS...> :
    pick_impl<N, N + 1, false, std::tuple<TPARGS...>,  ARGS...> {};

/* FINISH */
template <std::size_t N, std::size_t I, bool bAdd, typename ...TPARGS>
  struct pick_impl<N, I, bAdd, std::tuple<TPARGS...>>
{
  using type = std::tuple<TPARGS...>;
};

template <std::size_t N, typename ...ARGS>
  struct pick :
    pick_impl<N, 0, true, std::tuple<>, ARGS...> {};

template <std::size_t N, typename ...ARGS>
  struct pick_r :
    pick_impl<std::tuple_size<std::tuple<ARGS...>>::value - N, 0, false, std::tuple<>, ARGS...> {};
```

元々イメージしていたコードで試したところエラーになりまして（そりゃそうですよね）、```bAdd```を反転させ華麗にパスするという夢は打ち砕かれて、ベタに true / false を書くというトホホな結果になりました。
まぁ、元のコードに比べたら、後から見て、意図したいことが分からんでもない感じになりました。

さて。。。　次は ```std::conditional``` を答えを見ないで頑張ってみようかと。

このままだと寝ないで書いてそうなので、ここは我慢で、一旦、寝ますかね。

## 捻ってみた（その2）

ここからは```std::conditional```っぽいものを想像しながら書く感じになると思います。
知らないというのは人生に１回ですからね〜
こういう楽しみ方ができるまたとないチャンスです。

まず、神様のコードをイメージして。。。

```cpp
template <bool, typename T1, typename T2> struct cond;

template <typename T1, typename T2>
  struct cond<true, T1, T2> : public T1 {};

template <typename T1, typename T2>
  struct cond<false, T1, T2> : public T2 {};
```

ここまで書いてみて、「プリミティブ型なら良いけど、オブジェクト型の派生になると、ものによってはコンストラクタの面倒を見なきゃならんのでは？」と考えて一旦保留。
そして、今までの知識でできたのがこんな感じ。

```cpp
template <bool, typename T1, typename T2> struct cond;

template <typename T1, typename T2>
  struct cond<true, T1, T2> { using type = T1; };

template <typename T1, typename T2>
  struct cond<false, T1, T2> { using type = T2; };
```

これをベースにして。。。

## 書いてみた（その２）

```cpp
template <bool, typename T1, typename T2> struct cond;

template <typename T1, typename T2>
  struct cond<true, T1, T2> { using type = T1; };

template <typename T1, typename T2>
  struct cond<false, T1, T2> { using type = T2; };

template <std::size_t N, std::size_t I, typename ...T>
  struct pick_impl;

template <std::size_t N, std::size_t I, typename ...TPARGS, typename T, typename ...ARGS>
  struct pick_impl<N, I, std::tuple<TPARGS...>, T, ARGS...> :
    cond<
      I == N,
      pick_impl<N, I + 1, std::tuple<TPARGS...>>,
      pick_impl<N, I + 1, std::tuple<TPARGS..., T>, ARGS...>
    >::type {};
      
template <std::size_t N, std::size_t I, typename ...TPARGS>
  struct pick_impl<N, I, std::tuple<TPARGS...>>
{
  using type = std::tuple<TPARGS...>;
};

template <std::size_t N, typename ...ARGS>
  struct pick :
    pick_impl<N, 0, std::tuple<>, ARGS...> {};
```

うむ。。。　神様のコードに近づいたかな？
あと、比較演算子で ```I >= N``` とか使おうかと思ったんだけど、何だか```>```が嫌な予感しかしなくて、まだやってない。（あとで遊んでみようかな）

さて、もうちょい、```std::conditional```を使うのを我慢して、こんどは後ろから ```N``` 個をやってみようと思うんだけど、```pick_impl``` に似た別のテンプレート用意しなきゃだめかなぁ〜　と、悩んいる。。。

## 捻ってみた（その３）

そろそろお楽しみの時間ということで。。。
こんな感じで整理をしてみて。。。

* ```pick_impl``` に渡る ```ARGS...``` を ```FRONT``` と ```BACK``` に分解する
* 前の```N```個は```FRONT```を採用
* 後ろの```N```個の```N```は```ARGS...```の個数（```std::tuple```を使用）から算出し、```pick_impl```の```BACK```を採用
* 静的解析部なので、範囲外はコンパイルエラー扱いとする

## 書いてみた（その３）

```cpp
template <bool, typename T1, typename T2> struct cond;

template <typename T1, typename T2>
  struct cond<true, T1, T2> { using type = T1; };

template <typename T1, typename T2>
  struct cond<false, T1, T2> { using type = T2; };

template <std::size_t N, std::size_t I, typename ...T>
  struct pick_impl;

template <std::size_t N, std::size_t I, typename ...FRONT, typename T, typename ...ARGS>
  struct pick_impl<N, I, std::tuple<FRONT...>, std::tuple<>, T, ARGS...> :
    cond<
      I == N,
      pick_impl<N, I + 1, std::tuple<FRONT...>, std::tuple<T, ARGS...>>,
      pick_impl<N, I + 1, std::tuple<FRONT..., T>, std::tuple<>, ARGS...>
    >::type {};

template <std::size_t N, std::size_t I, typename ...FRONT, typename ...BACK>
  struct pick_impl<N, I, std::tuple<FRONT...>, std::tuple<BACK...>>
{
  using front = typename std::tuple<FRONT...>;
  using back  = typename std::tuple<BACK...>;
};

template <std::size_t N, typename ...ARGS> struct pick
{
  static_assert(N > 0, "N <= 0");
  static_assert(N <= std::tuple_size<std::tuple<ARGS...>>::value, "N > ARGS");
  using type = typename pick_impl<N, 0, std::tuple<>, std::tuple<>, ARGS...>::front;
};

template <std::size_t N, typename ...ARGS> struct pick_r
{
  static_assert(N > 0, "N <= 0");
  static_assert(N <= std::tuple_size<std::tuple<ARGS...>>::value, "N > ARGS");
  using type = typename pick_impl<std::tuple_size<std::tuple<ARGS...>>::value - N, 0, std::tuple<>, std::tuple<>, ARGS...>::back;
};
```

もう、何というか。。。
こりゃ、副作用が存在しないプログラムを作る感じですね。
それを「メタプログラミング」って云うんだと思いますが、そのメタプログラミングを実感できた気がします。

さぁ～て、いい加減、```std::condition```の実装を見てみて答え合わせする時間かな。（笑）

最後に、良いタイミングで毎回助言をいただく @myoukaku さん、否、神様、楽しい時間をありがとうございました！