类型线性谱系中最低的共同祖先

Question

介绍

让我们假设我们有一个类似于以下类型的线性层次结构:

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

试图代码

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;
};

现场演示

用例

我的用例是相当典型的:在制作一些iterator工具时我想提取"限制性最强"的迭代器类型,因此迭代器中存在(种类)线性层次结构,我应该能够根据需要提升层次结构:

LCA<Bidirectional, RandomAccess, RandomAccess> -> Bidirectional
LCA<RandomAccess, Input, Forward>              -> Input

问题

1. 是否有更简洁/惯用的方法来处理错误情况,其中两个或更多类型是层次结构的陌生人？目前的方法是返回void,希望在实际使用类型的大多数情况下都会失败.

2. base在第一次专业化中使用额外成员是否有问题？我应该在单独的类中提取该功能并使用内联type来保持一致性吗？

3. 是否有一种算法可以减少实例化的数量？有没有比成对比较更好的方法,这样可以降低算法的复杂性？

4. 任何人都可以扩展到非线性层次结构并按层次结构树深度查询吗？在这种情况下,对于同一级别的类型,什么是好的"打破"？

Answer 1

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我猜,妈妈和爸爸不共享相同的父母).所以我建议放弃这个案子.

一根树:

struct Mom {};
struct Son: Mom {};
struct Daughter: Mom {};

我建议,如果列表中有一个类型,算法只返回一个类型,所有类型都可以被转换为(例如LCA<Son, Daughter>::type没有LCA,因为我希望它们是兄弟姐妹).因此,我们在列表中搜索该类型,这是所有其他类型的基本类型.

因为只有上面的邻居类型相互比较,所以必须扩展比较以将每种类型相互比较(遗憾的是这是O(n ^ 2)).所以基本的想法是检查每种类型,如果它是所有其他类型的共同祖先.这只是的情况LCA.顺便说一句:以这种方式解决它有另一个好处,因为你会在"多根" - 场景中得到一个错误,但是如果多个根再次加入一个共同的根(这是列表的一部分),那么结果是正确的.

我们首先需要一个功能,它确定一种类型是否是所有其他类型的基本类型:

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将每个元素与整个模板参数包进行比较.第一个是all的基本类型.如果last也不是所有其他的基类型,则LCA再次派生TypeWrapper<TypeIsNotPartOfTheHierarchy>,这将引发典型的静态断言.

这个非常不方便.包装器将修复此问题:

template<typename... Ts>
struct LCA: detail::LCA<std::tuple<Ts...>, Ts...>
{};

有关树的LCA的完整代码,请访问:http://ideone.com/pYEPYl

Answer 2

1. std::enable_if如果第一个模板参数为 false，则会导致编译错误。回退到定义 void 类型的另一种替代方法是导致编译错误。

2. 我认为如果使用显式继承作为解析正确类型的方法，模板会更整洁，请参见下文。

3. 我不明白如何将复杂性降低到线性复杂性以下。不知何故，以某种方式，您必须迭代所有模板参数类型，才能选择其中之一。

4. std::is_base_of 并没有真正告诉您子类在超类之下有多深，只是一个是另一个的子类。此外，通过多重继承，给定的子类可能出现在超类以下的不同级别，因此语义有点混乱。

无论如何，我认为使用单独的类来执行成对类型比较，并使用继承，看起来更干净：

template<typename T1, typename T2, bool is_t1_base, bool is_t2_base>
class which_one_is_base;

// If T1 and T2 are the same, dontcare will be true.

template<typename T1, typename T2, bool dontcare>
class which_one_is_base<T1, T2, true, dontcare> {

public:
    typedef T1 type;
};

template<typename T1, typename T2>
class which_one_is_base<T1, T2, false, true> {

public:
    typedef T2 type;
};

template<typename T1, typename T2>
class select_base : public which_one_is_base<T1, T2,
                         std::is_base_of<T1, T2>::value,
                         std::is_base_of<T2, T1>::value>
{
};

//////////////////////////////////////////////////////////////////////

template<typename ...Ts> class LCA;

template<typename T1> class LCA<T1> {

public:
    typedef T1 type;
};

template<typename T1, typename T2, typename ...Ts>
class LCA<T1, T2, Ts...> :
    public LCA< typename select_base<T1, T2>::type, Ts...> {
};