c++ 检查元组中的每个元素是否有值

我有一个std::tuple< std::optional<Args> ... >，需要检查每个元素都有一个值。我已经用std：：index_sequence实现了它。但是我不确定这是最快编译时间的最有效的解决方案。

using data_type = std::tuple< std::optional<Arg_1>, 
                              std::optional<Arg_2>,
                               //....
                              std::optional<Arg_n>  // where n > 40
                             >;

// My solution.
template <size_t ... indexes>
bool has_value_all_elements_impl(const data_type& tuple_data, std::index_sequence<indexes ...> ) {
       //I assume there O(n) lookup for each index in compile time. 
       // So total O(n^2) lookup for tuple ?
       return (std::get<indexes>(tuple_data).has_value() && ... ) ;
}

bool has_value_all_elements(data_type const& tuple_data)
{
     return has_value_all_elements_impl(
      tuple_data, std::make_index_sequence<std::tuple_size<data_type>::value>{});
}

对于这样的问题，有没有更有效的O（n）算法？
时间复杂度O（n）

我决定回答我自己的问题。
看来"慢性评论"是对的。

- 源代码**on godbold-似乎取决于STL实现。GCC stdlibc ++增加的编译时间不是线性的。libc ++增加的编译时间是线性的。

海湾合作委员会：

$ g++ --version
g++ (Ubuntu 11.1.0-1ubuntu1~20.04) 11.1.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

 
$ time g++ -DARG_SIZE=10 -Wall -o "example" "example.cpp" -std=c++17     -lpthread  -Wall -Wextra -pedantic -O2

real    0m0.431s
user    0m0.384s
sys 0m0.047s

$ time g++ -DARG_SIZE=20 -Wall -o "example" "example.cpp" -std=c++17     -lpthread  -Wall -Wextra -pedantic -O2

real    0m0.507s
user    0m0.461s
sys 0m0.046s

$ time g++ -DARG_SIZE=40 -Wall -o "example" "example.cpp" -std=c++17     -lpthread  -Wall -Wextra -pedantic -O2

real    0m0.737s
user    0m0.666s
sys 0m0.071s

$ time g++ -DARG_SIZE=80 -Wall -o "example" "example.cpp" -std=c++17     -lpthread  -Wall -Wextra -pedantic -O2

real    0m2.030s
user    0m1.882s
sys 0m0.148s

$ time g++ -DARG_SIZE=160 -Wall -o "example" "example.cpp" -std=c++17     -lpthread  -Wall -Wextra -pedantic -O2

real    0m23.532s
user    0m23.216s
sys 0m0.312s

$ time g++ -DARG_SIZE=320 -Wall -o "example" "example.cpp" -std=c++17     -lpthread  -Wall -Wextra -pedantic -O2

real    10m40.392s
user    10m37.992s
sys 0m2.067s

铿锵：

$ clang++ --version
Ubuntu clang version 12.0.0-3ubuntu1~20.04.5
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/bin

$ time clang++ -DARG_SIZE=10 -Wall -o "example" "example.cpp" -std=c++17  -stdlib=libc++   -lpthread  -Wall -Wextra -pedantic -O2
example.cpp:36:15: warning: unused variable 'd' [-Wunused-variable]
    data_type d;
              ^
1 warning generated.

real    0m1.056s
user    0m0.667s
sys 0m0.066s

$ time clang++ -DARG_SIZE=20 -Wall -o "example" "example.cpp" -std=c++17  -stdlib=libc++   -lpthread  -Wall -Wextra -pedantic -O2
example.cpp:36:15: warning: unused variable 'd' [-Wunused-variable]
    data_type d;
              ^
1 warning generated.

real    0m0.816s
user    0m0.764s
sys 0m0.048s

$ time clang++ -DARG_SIZE=40 -Wall -o "example" "example.cpp" -std=c++17  -stdlib=libc++   -lpthread  -Wall -Wextra -pedantic -O2
example.cpp:36:15: warning: unused variable 'd' [-Wunused-variable]
    data_type d;
              ^
1 warning generated.

real    0m1.455s
user    0m0.985s
sys 0m0.095s

$ time clang++ -DARG_SIZE=80 -Wall -o "example" "example.cpp" -std=c++17  -stdlib=libc++   -lpthread  -Wall -Wextra -pedantic -O2
example.cpp:36:15: warning: unused variable 'd' [-Wunused-variable]
    data_type d;
              ^
1 warning generated.

real    0m1.565s
user    0m1.484s
sys 0m0.067s

$ time clang++ -DARG_SIZE=160 -Wall -o "example" "example.cpp" -std=c++17  -stdlib=libc++   -lpthread  -Wall -Wextra -pedantic -O2
example.cpp:36:15: warning: unused variable 'd' [-Wunused-variable]
    data_type d;
              ^
1 warning generated.

real    0m3.172s
user    0m2.410s
sys 0m0.080s

$ time clang++ -DARG_SIZE=320 -Wall -o "example" "example.cpp" -std=c++17  -stdlib=libc++   -lpthread  -Wall -Wextra -pedantic -O2 -fbracket-depth=400
example.cpp:36:15: warning: unused variable 'd' [-Wunused-variable]
    data_type d;
              ^
1 warning generated.

real    0m4.576s
user    0m4.337s
sys 0m0.238s

c++ 检查元组中的每个元素是否有值

1条答案

相关问题

热门标签

最新问答