LoginSignup
3
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@terukazu(Terukazu Inoue)

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

Last updated at Posted at 2021-03-08

ことの発端

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

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

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

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

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

失敗の巻

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*}]

予想以上に分かりやすいエラーメッセージ！
ふむ、２つのテンプレートでどっちを採用して良いか分からんという事みたいで、定義をよ〜〜〜く見てみると...

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

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 で定義して終了とする。

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

成功の巻

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になるのがオチかと思いますが）

捻ってみた（その１）

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

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 を反転して再帰させる的な。

書いてみた（その１）

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っぽいものを想像しながら書く感じになると思います。
知らないというのは人生に１回ですからね〜
こういう楽しみ方ができるまたとないチャンスです。

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

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 {};

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

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 <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を採用
  • 静的解析部なので、範囲外はコンパイルエラー扱いとする

書いてみた（その３）

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 さん、否、神様、楽しい時間をありがとうございました！

3
2
4

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
3
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?