ISO C++ Standard - Future Proposals に投稿した
std-proposal は、C++標準化委員会メンバと非委員会メンバ両方が新しく提案したり、すでに存在する提案について議論する Google グループのページです。
先日書いた とおり、std::make_integer_seq に再帰深度のオーダーを定める提案です。
std::make_integer_seq should provide O(logN) order
内容
- std::make_integer_seq should provide O(logN) order
In my opinion, std::make_integer_seq should provide Ο(logN) order (template instantiation depth).
It becomes necessary for the generation of a "large integer sequence".
For example:
using t = make_integer_seq<int, 2000>;
In the simplest implementation of recursion Ο(N), which can not be compiled.
Because maximum depth defined by C++11 is 1024.
-
- make_integer_seq implementation Ο(N)
template<class T, T N, class Seq = integer_seq<T>, bool Break = N == 0> struct make_integer_seq_impl { using type = Seq; }; template<class T, T N, T... I> struct make_integer_seq_impl<T, N, integer_seq<T, I...>, false> : make_integer_seq_impl<T, N - 1, integer_seq<T, N - 1, I...>> {}; template<class T, T N> using make_integer_seq = typename make_integer_seq_impl<T, N>::type;
If implementation of the Ο(logN), can be compiled.
-
- make_integer_seq implementation Ο(logN)
template<class T, typename Seq, T Next> struct make_integer_seq_next_even; template<class T, T... I, T Next> struct make_integer_seq_next_even<T, integer_seq<T, I...>, Next> { using type = integer_seq<T, I..., (I + Next)...>; }; template<class T, typename Seq, T Next, T Last> struct make_integer_seq_next_odd; template<class T, T... I, T Next, T Last> struct make_integer_seq_next_odd<T, integer_seq<T, I...>, Next, Last> { using type = integer_seq<T, I..., (I + Next)..., Last>; }; template<class T, T N, class Enable = void> struct make_integer_seq_impl; template<class T, T N> struct make_integer_seq_impl<T, N, typename enable_if<(N == 0)>::type> { using type = integer_seq<T>; }; template<class T, T N> struct make_integer_seq_impl<T, N, typename enable_if<(N == 1)>::type> { using type = integer_seq<T, 0>; }; template<class T, T N> struct make_integer_seq_impl<T, N, typename enable_if<(N > 1 && N % 2 == 0)>::type> : make_integer_seq_next_even<T, typename make_integer_seq_impl<T, N / 2>::type, N / 2> {}; template<class T, T N> struct make_integer_seq_impl<T, N, typename enable_if<(N > 1 && N % 2 == 1)>::type> : make_integer_seq_next_odd<T, typename make_integer_seq_impl<T, N / 2>::type, N / 2, N - 1> {}; template<class T, T N> using make_integer_seq = typename make_integer_seq_impl<T, N>::type;
Therefore, std::make_integer_seq should be implemented in Ο(logN) order (template recursion depth).
And I think it should be defined as Ο(logN) order by the C++ standard.
It is the benefit for heavy users of template meta-programming, and it will not become to the detriment of other programmers.
My Sprout library provides Ο(logN) ordered index_tuple (the same as make_integer_seq).
The feature's order is very useful for large data computation.
See: https://github.com/bolero-MURAKAMI/Sprout/blob/master/sprout/index_tuple/index_range.hpp
翻訳前
- std::make_integer_seq にオーダー Ο(logN) を規定すべきである
私の考えるに、std::make_integer_seq にオーダー Ο(logN) を規定すべきである(テンプレート再帰深度)。
それは「巨大な数列」の生成のために必要となる。
例えば:
using t = make_integer_seq<int, 2000>;
Ο(N) の最も単純な再帰の実装では、これはコンパイルできない。
C++11 が規定している深度上限は 1024 だからである。
-
- make_integer_seq Ο(N) 実装
(実装)
Ο(logN) の実装ならば、コンパイルできる。
-
- make_integer_seq Ο(logN) 実装
(実装)
ゆえに、std::make_integer_seq は Ο(logN) で実装されるべきである。
そして私は C++標準でも Ο(logN) と規定すべきだと思う。
それはテンプレートメタプログラミングのヘビーユーザに利益をもたらすし、またそれ以外のプログラマの不利益にはならない。
私が開発している Sprout ライブラリでは、index_tuple という名前で同じ機能を Ο(logN) オーダーで提供している。
このオーダー規定は、大きなデータを計算するのに重宝している。
参照: https://github.com/bolero-MURAKAMI/Sprout/blob/master/sprout/index_tuple/index_range.hpp
謝辞
この提案の文章作成と翻訳にあたっては、アキラさん(id:faith_and_brave)とほっとさん(id:heisseswasser)による助言と協力をいただきました。
おかげで何とか意思伝達可能なものにすることができたと思います。
この場を借りてお礼申し上げます。