介绍

假设我们有一个类型的线性层次结构,如下所示:

然后我想要的是一种机制,可以从该世系中任意数量的类型中返回最低的共同祖先

尝试输入的代码

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

    09-11 19:30
    查看更多