std::common_type 的复杂度是多少？

Question

我写了我的 std::common_type 实现：

template <typename Head, typename... Tail>
struct my_common_type {
  using type = typename my_common_type<Head, typename my_common_type<Tail...>::type>::type;
};

template <typename T, typename U>
struct my_common_type<T, U> {
  using type = std::remove_reference_t<decltype(true ? declval<T>() : declval<U>())>;
};

知道这个元函数 returns 类型从提议的我们可以转换其他的在这种情况下我的实现将不起作用：

struct Granny {};
struct Mother : Granny {};
struct Father : Granny {};

my_common_type<Granny, Mother, Father>::type 不会编译，但 std::common_type_t<Granny, Mother, Father> 会 return Granny 类型。

当 n 是建议类型的计数时，std::common_type 是否在 O(n!) 上运行（是的，我知道它在编译时运行）？

或者 O(n^2)？

更新：

std::common_type_t<Mother, Father, Granny> 不起作用。常用类型是通过什么方式搜索的？

Answer 1

当将 common_type 应用于三个或更多模板参数时，common_type<T1, T2, R...>::type 定义为 common_type_t<C, R...>，其中 C 为 common_type_t<T1, T2>。如果 T1 和 T2 没有共同的类型，那么 type typedef 不存在。

这意味着 common_type 被定义为从左到右处理其参数，并且可以在 O(n) 中完成。这也意味着重新排列参数的顺序会导致不同的结果。

在您自己的实施中，您从右到左工作，这就是您得到不同结果的原因。

std::common_type 的复杂度是多少？

What is complexity of std::common_type?

c++

metaprogramming

typetraits