递归模板实现元组的编译时开销量化及优化问询

背景与需求 #

多个资料表明，递归模板实现的元组存在编译时开销。我计划开发一个需使用数百个元组的系统，元组大小范围为1-100（中位数约5-10），担忧所用标准库的递归实现会带来性能影响，希望能量化其对编译时间、内存占用的具体影响（例如编译时长增加25%或内存占用提升50%）。此前我曾因模板实例化问题遭受严重影响，因此对此尤为关注。

我的核心需求是创建元组并通过std::get完成遍历，拟采用如下代码实现遍历逻辑：

// for_each_tuple
template <typename TupleT, typename Fn>
void for_each_tuple(TupleT&& tp, Fn&& fn)
{
    std::apply([&fn]<typename... T>(T&&... args) { (fn(std::forward<T>(args)), ...); },
               std::forward<TupleT>(tp));
}

各编译器标准库实现分析 #

我注意到libstdc++的std::get为非递归实现，编译复杂度为O(1)，但MSVC和GCC的实现细节不够清晰：我认为MSVC的std::get是递归实现，编译复杂度为O(n)，但无法确定GCC的实现是否为递归。

MSVC的std::get与元组实现 #

std::get实现：

template <size_t _Index, class... _Types>
constexpr tuple_element_t<_Index, tuple<_Types...>>& get(tuple<_Types...>& _Tuple) noexcept {
    using _Ttype = typename tuple_element<_Index, tuple<_Types...>>::_Ttype;
    return static_cast<_Ttype&>(_Tuple)._Myfirst._Val;
}

其tuple_element采用递归定义：

template <size_t _Index, class _This, class... _Rest>
struct tuple_element<_Index, tuple<_This, _Rest...>>
    : tuple_element<_Index - 1, tuple<_Rest...>> {}; // recursive tuple_element definition

元组类定义为递归继承：

template <class _This, class... _Rest>
class tuple<_This, _Rest...> : private tuple<_Rest...> { // recursive tuple definition
public:
    using _This_type = _This;
    using _Mybase    = tuple<_Rest...>;

GCC libstdc++的std::get与元组实现 #

std::get实现：

template<size_t __i, typename... _Elements>
    constexpr __tuple_element_t<__i, tuple<_Elements...>>&
    get(tuple<_Elements...>& __t) noexcept
    { return std::__get_helper<__i>(__t); }

  template<size_t __i, typename _Head, typename... _Tail>
    constexpr _Head&
    __get_helper(_Tuple_impl<__i, _Head, _Tail...>& __t) noexcept
    { return _Tuple_impl<__i, _Head, _Tail...>::_M_head(__t); }

元组实现采用递归继承的_Tuple_impl：

/**
   * Recursive tuple implementation. Here we store the @c Head element
   * and derive from a @c Tuple_impl containing the remaining elements
   * (which contains the @c Tail).
   */
  template<size_t _Idx, typename _Head, typename... _Tail>
    struct _Tuple_impl<_Idx, _Head, _Tail...>
    : public _Tuple_impl<_Idx + 1, _Tail...>,
      private _Head_base<_Idx, _Head>
    {
      template<size_t, typename...> friend struct _Tuple_impl;

Clang libc++的std::get与元组实现 #

std::get实现：

template <size_t _Ip, class ..._Tp>
typename tuple_element<_Ip, tuple<_Tp...> >::type&
get(tuple<_Tp...>& __t) _NOEXCEPT
{
    typedef typename tuple_element<_Ip, tuple<_Tp...> >::type type;
    return static_cast<__tuple_leaf<_Ip, type>&>(__t.__base_).get();
}

元组采用非递归实现：

template <class ..._Tp>
class tuple
{
    typedef __tuple_impl<typename __make_tuple_indices<sizeof...(_Tp)>::type, _Tp...> _BaseT;
    _BaseT __base_;

核心疑问 #

综上，若我的理解正确，MSVC和GCC中至少有一个的std::get为递归实现，编译复杂度为O(n)，而我使用的for_each_tuple代码编译复杂度为O(n²)。请问：

• 能否将遍历的编译复杂度降至O(n)？
• 即便做到这点，MSVC和GCC的递归元组构造是否仍会给编译器带来显著的时间/空间开销？

（注：我使用的编译器版本为MSVC 2022 17.6、GCC 13.2、Clang 16，上述标准库代码已删减冗余内容以提升可读性。）

内容的提问来源于stack exchange，提问作者TooTone