std::tuple_element的编译时间复杂度（即编译器的运行时间复杂度）<N, TupleType>

Question

假设在我的代码中我有以下行：

using T = std::tuple_element<N,TupleType>

其中 TupleType 是一个非常大的元组的类型，N 是一个非常大的数字（比如 1,000,000）

我知道这行代码对我的程序的运行时性能没有影响。但是它对我的程序编译所需的时间有什么样的影响（即这如何影响编译器的运行时间）

编译器基本上会在 O(N) 内解决这个问题吗？ O(log(N))？ O(1)？

据我所知，使用标准 C++ 的简单实现将是 O(N)。使用标准 C++ 的更智能实现将是 O(log(N))。如果编译器在幕后做了一些特殊的事情，它可以实现 O(1)。对于 GNU GCC 编译器，以下哪一项是正确的？

注意：我需要处理模板元编程任务的多种类型。我从未真正实例化过此元组类型的实例。只是在编译时将其用作类型的容器。

Answer 1

这里是一些（python）基准代码；它生成几个 .cpp 文件并测量编译时间

#!/usr/bin/python3

import sys
import os
import time

compiler = sys.argv[1] if len(sys.argv)>1 else "g++"

################################################################################
def test(N,nbruns=4):

    code = [];
    code.append ("#include <tuple>");
    code.append ("using type = std::tuple<{:s}>;".format(",".join(['int']*N)));
    code.append ("static_assert (std::is_same<int,std::tuple_element<{:d},type>::type >::value);".format(N-1))
    code.append ("int main() {}")

    filename = "output.cpp";
    
    with open(filename, "w") as f: 
        f.write("\n".join(code));

    t = 0;
    for n in range(1,nbruns):
        t0 = time.time_ns();        
        os.system ("{:s} {:s} -std=c++11 -ftemplate-depth={:d}".format (compiler, filename, max(100,N)));       
        t1 = time.time_ns();
        t += (t1-t0);
        
    return t/nbruns/1000/1000/1000;
    
################################################################################    
            
for i in range(2000,20000,2000):
    N = i;
    print ("{:8d}  {:8.3f}".format (N, test(N)));
            

例如，N=10 的生成文件将是：

#include <tuple>
using type = std::tuple<int,int,int,int,int,int,int,int,int,int>;
static_assert (std::is_same<int,std::tuple_element<9,type>::type >::value);
int main() {}

以下是 g++ 基准测试的一些结果，其中第一列是元组中的项目数，第二列是编译时间（以秒为单位）

    2000     0.334
    4000     1.128
    6000     2.426
    8000     4.784
   10000     6.780
   12000     9.555
   14000    12.408
   16000    16.952
   18000    21.839

这听起来不太线性。