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

Question

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

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

请注意，我不是在问 how to implement it efficiently ，但编译器供应商实际上是如何决定实现它的。

我所知道的 make_sequence 的唯一实现是简单的 O(n) 递归方法和巧妙的 O(logN) 分治法。

Answer 1

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

libstdc++ (海合会):

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

libc++ ( clang ):

O(n) 实现，但有一个有趣的 8 倍展开循环。

MSVC ( VS14 CTP1 ):

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

ICC 是 not currently documented作为提供编译时整数常量支持。

---

此时担心 std::integer_sequence 的效率可能不值得；编译时整数序列适用的任何问题都会在所用算法的大 O 性能影响编译时间之前很久就达到编译器的限制(在函数和模板参数的数量等方面)。还要考虑，如果 std::make_integer_sequence 在编译中的其他任何地方使用(例如，在库模板代码中)，那么编译器将能够重用该调用，因为模板元编程是纯函数式的。