时间戳

首页 > 解决方案 > std::common_type 的复杂度是多少？

c++ - std::common_type 的复杂度是多少？

问题描述

我写了我的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>())>;
};

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

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

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

当 n 是提议的类型计数时，std::common_type 是否适用于 O(n!)（是的，我知道它适用于编译时）？

或者可能是 O(n^2)？

升级版：

std::common_type_t<Mother, Father, Granny>不起作用。以何种方式搜索常用类型？

标签： c++metaprogrammingtypetraits

解决方案

当应用于common_type三个或更多模板参数时，common_type<T1, T2, R...>::type定义为common_type_t<C, R...>C 所在的位置common_type_t<T1, T2>。如果 T1 和 T2 没有公共类型，则typetypedef 不存在。

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

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

推荐阅读