介绍
假设我们有一个类型的线性层次结构,如下所示:
然后我想要的是一种机制,可以从该世系中任意数量的类型中返回最低的共同祖先。
尝试输入的代码
template<typename...Ts>
struct LCA;
template<typename T1, typename T2, typename...Ts>
struct LCA<T1, T2, Ts...>
{
using base = typename std::conditional
<
std::is_base_of<T1, T2>::value, T1,
typename std::conditional <
std::is_base_of<T2, T1>::value, T2, void
>::type
>::type;
using type = typename LCA<base, Ts...>::type;
};
template<typename T>
struct LCA<T>
{
using type = T;
};
Live Demo
用例
我的用例很典型:在制作一些
iterator
工具时,我要提取“最严格的”迭代器类型,因此,由于迭代器中存在(某种)线性层次结构,因此我应该能够根据需要增加层次结构:LCA<Bidirectional, RandomAccess, RandomAccess> -> Bidirectional
LCA<RandomAccess, Input, Forward> -> Input
问题
void
,希望在实际使用该类型的大多数情况下会导致失败。 base
成员是否有问题?我是否应该在单独的类中提取该功能,并在type
中内联使用它来保持的一致性? 最佳答案
1.技术方面
我会使用派生,因为这比类型定义干净。这是一些示例代码:
#include <iostream>
#include <typeinfo>
#include <type_traits>
struct Grandma {};
struct Mom : Grandma {};
struct Daughter : Mom {};
struct Son : Mom {};
struct Grandchild : Son {};
struct Stranger {};
namespace detail
{
struct TypeIsNotPartOfTheHierarchy {};
template<typename T>
struct TypeWrapper
{
static_assert(!std::is_same<TypeIsNotPartOfTheHierarchy, T>::value,
"using types of different type hierarchies.");
using type = T;
};
}
template<typename... Ts>
struct LCA;
template<typename T>
struct LCA<T>: detail::TypeWrapper<T>
{};
template<typename T1, typename T2>
struct LCA<T1, T2>:
std::conditional
<
std::is_base_of<T1, T2>::value,
detail::TypeWrapper<T1>,
typename std::conditional
<
std::is_base_of<T2, T1>::value,
detail::TypeWrapper<T2>,
detail::TypeWrapper<detail::TypeIsNotPartOfTheHierarchy>
>::type
>::type
{};
template<typename T1, typename... Ts>
struct LCA<T1, Ts...>: LCA<T1, typename LCA<Ts...>::type>
{};
int main()
{
std::cout << typeid(LCA<Son, Mom, Grandchild, Grandma, Son, Son>::type).name() << std::endl;
std::cout << typeid(LCA<Son>::type).name() << std::endl;
// error because Daughter and Son are siblings.
// std::cout << typeid(LCA<Son, Daughter, Son>::type).name() << std::endl;
// error because Son is not related to the Stranger.
// std::cout << typeid(LCA<Son, Stranger, Son>::type).name() << std::endl;
return 0;
}
从技术上讲,您可以使用
std::enable_if
而不是std::condition
,但是使用std::enable_if
意味着您必须从if-true,if-false和if-types-not-compatible情况派生。恕我直言,使用std::condition
更具可读性。必须再次包装该类型以具有类型,可以通过条件启用该类型,然后提供typedef以供在外部使用。为了得到一个编译错误,静态地声明它会给您一个很好的消息,而不是在编译器输出中出现困难的模板错误。然后,您可以随意使用
void
表示错误。我建议使用额外的类型来命名此错误。这也提高了可读性。2.基本类型
我认为
base
成员应该被隐藏,因为否则您向用户显示了超出需求的内容,这可能会使他们感到困惑。使用类型派生解决了这个问题。3.复杂性
我认为,不可能提高复杂度O(n)。如果每种类型可能是
LCA
类型,则必须至少检查一次。因此,每种类型至少是比较的一部分。4.其他层次结构(美丽的部分)
上面的实现(也是您自己的实现)在线性层次结构上没有其他意义(例如
LCA<Daughter, Grandma, Son>
将返回Grandma
,而LCA<Grandma, Daughter, Son>::type
将导致错误,因为仅比较邻居类型)。但是,在C++中可能有两种类型的“分支继承”(当然还有混合):
具有多个根的树:
struct Dad {};
struct Mom {};
struct Son: Dad, Mom {};
在某些情况下
LCA
是不确定的(例如,我猜是LCA<Mom, Dad>::type
,妈妈和爸爸的 parent 并不相同)。因此,我建议删除这种情况。一棵树的根:
struct Mom {};
struct Son: Mom {};
struct Daughter: Mom {};
我建议,如果列表中存在一种类型,则该算法仅返回一种类型,所有类型都可以转换为该类型(例如
LCA<Son, Daughter>::type
没有LCA,因为我希望它们是同级)。因此,我们在列表中搜索所有其他类型的基本类型。因为上面仅将相邻类型进行了比较,所以必须扩展比较以将每种类型进行比较(可悲的是,这是O(n ^ 2))。因此,基本思想是检查每种类型(如果它是所有其他类型的共同祖先)。这仅是
LCA
的情况。顺便说一句:用这种方法解决还有另一个优势,因为在“多个根”方案中会出现错误,但是如果多个根又在一个公共(public)根(属于列表的一部分)中连接,则结果正确。我们首先需要一个功能,该功能确定一种类型是否是所有其他类型的基本类型:
template<typename StillCommonAncestor, typename TypeToCheck, typename... Ts>
struct IsCommonAncestor;
template<typename StillCommonAncestor, typename TypeToCheck>
struct IsCommonAncestor<StillCommonAncestor, TypeToCheck>
{
static constexpr bool value = StillCommonAncestor::value;
};
template<typename StillCommonAncestor, typename TypeToCheck, typename T1, typename... Ts>
struct IsCommonAncestor<StillCommonAncestor, TypeToCheck, T1, Ts...>:
IsCommonAncestor
<
std::integral_constant
<
bool,
std::conditional
<
std::is_base_of<TypeToCheck, T1>::value,
std::true_type,
std::false_type
>::type::value && StillCommonAncestor::value
>,
TypeToCheck,
Ts...
>
{};
要检查某个类型是否是所有其他类型的共同祖先,只需使用
IsCommonAncestor<std::true_type, Mom, Grandchild, Daughter, Son>::value
(此处为true,而IsCommonAncestor<std::true_type, Grandchild, Grandchild, Daughter, Son>::value
为false)。请注意,如果一种类型不属于类型层次结构的一部分,则该值也为false。然后需要一些“设施”,以遍历类型并捕获唯一的
IsCommonAncestor<...>::value
为真的类型:template<typename Pack, typename... Ts>
struct LCA;
template<typename... PackParams, typename T1>
struct LCA<std::tuple<PackParams...>, T1>:
std::conditional
<
IsCommonAncestor<std::true_type, T1, PackParams...>::value,
TypeWrapper<T1>,
TypeWrapper<TypeIsNotPartOfTheHierarchy>
>::type
{};
template<typename... PackParams, typename T1, typename... Ts>
struct LCA<std::tuple<PackParams...>, T1, Ts...>:
std::conditional
<
IsCommonAncestor<std::true_type, T1, PackParams...>::value,
TypeWrapper<T1>,
LCA<std::tuple<PackParams...>, Ts...>
>::type
{};
LCA将每个元素与整个模板参数包进行比较。首先
这就是所有基本类型。如果最后一个也不是所有基本类型
其他人,LCA再次从
TypeWrapper<TypeIsNotPartOfTheHierarchy>
派生,将引发典型的静态断言。
这很不方便。包装器将解决此问题:
template<typename... Ts>
struct LCA: detail::LCA<std::tuple<Ts...>, Ts...>
{};
此处提供了树的LCA的完整代码:http://ideone.com/pYEPYl