読者です 読者をやめる 読者になる 読者になる

とくにあぶなくないRiSKのブログ

危ないRiSKのブログだったかもしれない。本当はRiSKだけどググラビリティとか取得できるIDの都合でsscriskも使ったり。

テンプレートの再帰を無くそう

C++

再帰の欠点

「テンプレートの再帰を無くす」…言うは易く行うは難しだとはいえ、再帰

  • 遅い
  • 再帰深度に限界がある
  • 恐ろしいエラーメッセージを出す

再帰を消し去る例

再帰を消し去ることに挑戦してみましょう。 T::value が全て true である時に true を返す all メタ関数を考えます。

再帰バージョン

普通に実装すると再帰を使って…

template<typename... T>
struct all;

template<>
struct all<>
{
    static constexpr bool value = true;
};

template<typename T, typename... Ts>
struct all<T, Ts...>
{
    static constexpr bool value = T::value && all<Ts...>::value;
};

使ってみます。ただし意図的にエラーにすると

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

エラーメッセージは…

prog.cc:13:35: error: type 'int' cannot be used prior to '::' because it has no members
    static constexpr bool value = T::value && all<Ts...>::value;
                                 ^
prog.cc:13:47: note: in instantiation of template class 'all<int>' requested here
   static constexpr bool value = T::value && all<Ts...>::value;
                                             ^
prog.cc:13:47: note: in instantiation of template class 'all<FalseSample<2>, int>' requested here
   static constexpr bool value = T::value && all<Ts...>::value;
                                             ^
prog.cc:13:47: note: in instantiation of template class 'all<FalseSample<1>, FalseSample<2>, int>' requested here
   static constexpr bool value = T::value && all<Ts...>::value;
                                             ^
prog.cc:13:47: note: in instantiation of template class 'all<FalseSample<0>, FalseSample<1>, FalseSample<2>, int>' requested here
   static constexpr bool value = T::value && all<Ts...>::value;
                                             ^
prog.cc:13:47: note: in instantiation of template class 'all<TrueSample<3>, FalseSample<0>, FalseSample<1>, FalseSample<2>, int>' requested here
   static constexpr bool value = T::value && all<Ts...>::value;
                                             ^
prog.cc:13:47: note: in instantiation of template class 'all<TrueSample<2>, TrueSample<3>, FalseSample<0>, FalseSample<1>, FalseSample<2>, int>' requested here
    static constexpr bool value = T::value && all<Ts...>::value;
                                             ^
prog.cc:13:47: note: in instantiation of template class 'all<TrueSample<1>, TrueSample<2>, TrueSample<3>, FalseSample<0>, FalseSample<1>, FalseSample<2>, int>' requested here
   static constexpr bool value = T::value && all<Ts...>::value;
                                             ^
prog.cc:27:17: note: in instantiation of template class 'all<TrueSample<0>, TrueSample<1>, TrueSample<2>, TrueSample<3>, FalseSample<0>, FalseSample<1>, FalseSample<2>, int>' requested here
static_assert(! all<TrueSample<0>, TrueSample<1>, TrueSample<2>, TrueSample<3>,FalseSample<0>, FalseSample<1>, FalseSample<2>, int>::value, "Ooops");
               ^
1 error generated.

これはひどい。 (コンパイラの種類やバージョンによっては、これよりメッセージが改善されていることがあります。)

再帰無しバージョン

なんと再帰を使わないでも実装できます。

#include<type_traits>

template<bool...> struct boollist {};

template<typename...T>
struct all
{
    static constexpr bool value = std::is_same<boollist<T::value...>, boollist<(T::value, true)...>>::value;
};

使ってみます。

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

今回のエラーメッセージは…

prog.cc:8:57: error: type 'int' cannot be used prior to '::' because it has no members
    static constexpr bool value = std::is_same<boollist<T::value...>, boollist<(T::value, true)...>>::value;
                                                       ^
prog.cc:22:17: note: in instantiation of template class 'all<TrueSample<0>, TrueSample<1>, TrueSample<2>, TrueSample<3>, FalseSample<0>, FalseSample<1>, FalseSample<2>, int>' requested here
static_assert(! all<TrueSample<0>, TrueSample<1>, TrueSample<2>, TrueSample<3>,FalseSample<0>, FalseSample<1>, FalseSample<2>, int>::value, "Ooops");
               ^
1 error generated.

短い。そして分かりやすいですね。

まとめ

テンプレートの再帰を極力使わないで実装してみよう!

参照