std :: make_integer_sequence究竟是如何实现的？

Question

我正在观看C++ 11/14元编程演讲,其中描述了常见算法和tmp模式的一些有效替代方案.

大多数效率增益来自使用可变参数模板而不是递归遍历,并且在许多情况下,使用可变参数模板的方法是扩展通过索引技巧或其他std::integer_sequence即时技巧生成的可变参数包.
由于效率来自实例化a std::integer_sequence,特别是别名std::make_integer_sequence不是一项昂贵的任务,我想确保C++ 1y标准库的当前最先进的实现是足够有效的,以使make_integer_sequence即时不是一个复杂的,耗时的/内存消耗的任务.
究竟std::make_integer_sequence是如何在C++ 1y-ready编译器中实际实现的？

请注意,我不是要问如何有效地实现它,而是编译器供应商如何实际决定实现它.

make_sequence我所知道的唯一实现是简单的O(n)递归方法和聪明的O(logN)划分和征服.

Answer 1

目前,主要的编译器标准库都没有提供N3658编译时整数序列的子O(n)(对数或其他)实现.

libstdc ++(gcc):

标准O(n)实现走一条链typedef.这相当于连接到递归调用返回的列表末尾的FP函数.

libc ++(clang):

O(n)实现,但有一个有趣的8x展开循环.

MSVC(VS14 CTP1):

O(n),使用在整数常量和整数序列上模板化的递归继承,后者用作累加器(在FP意义上).(注意,VS14实现实际上位于type_traits标题中,而不是在utility.)

ICC目前尚未记录为提供编译时整数常量支持.

std::integer_sequence在这一点上担心效率可能不值得; 编译时整数序列适合的任何问题都会在编译器的大O性能影响编译时间之前很快就会遇到编译器的限制(就函数和模板参数的数量等而言).还要考虑如果std::make_integer_sequence在编译中的任何其他位置使用(例如在库模板代码中),那么编译器将能够重用该调用,因为模板元编程纯粹是功能性的.

Answer 2

6 年多后，编译器支持内置函数来快速完成此任务。Clang 和 MSVC 有__make_integer_seq. 海湾合作委员会有__integer_pack. 事实上，STL 实现假设存在这样的内置函数！在这三个编译器之间，似乎只有 clang's/libc++ 有make_integer_sequence.

GCC 手册的 C++ 扩展：类型特征部分描述__integer_pack如下：

__integer_pack（长度）

当用作模板定义中的包扩展模式时，扩展为包含从 0 到 length-1 的整数的模板参数包。这是为了有效实现 std::make_integer_sequence 而提供的。

我没有在 clang 手册中找到描述 的部分__make_integer_seq，但是有一篇对将其添加到 clang 的提交的评论。

在与我的 GCC 11.1.0 副本一起安装的 libstdcxx 中，这是<utility>（第 328 行）中的代码make_integer_sequence：

/// Alias template make_integer_sequence
template<typename _Tp, _Tp _Num>
using make_integer_sequence
#if __has_builtin(__make_integer_seq)
      = __make_integer_seq<integer_sequence, _Tp, _Num>;
#else
      = integer_sequence<_Tp, __integer_pack(_Num)...>;
#endif

同样，Microsoft 的 STL在第 34 行对此进行了定义<type_traits>：

template <class _Ty, _Ty _Size>
using make_integer_sequence = __make_integer_seq<integer_sequence, _Ty, _Size>;

最后，从libcxx/include/__utility/integer_sequence.h第 39 行开始，有一个预处理器条件来检查我们是否需要使用后备：

#if __has_builtin(__make_integer_seq) && !defined(_LIBCPP_TESTING_FALLBACK_MAKE_INTEGER_SEQUENCE)

template <class _Tp, _Tp _Ep>
using __make_integer_sequence _LIBCPP_NODEBUG = __make_integer_seq<integer_sequence, _Tp, _Ep>;

#else
// fallback implementation that uses recursive templates