Ancêtre commun le plus bas dans une lignée linéaire de types

Question

Intro

Supposons que nous avons une hiérarchie linéaire des types comme suit:

Alors ce que je veux, c'est un mécanisme de retour le plus bas de l'ancêtre commun d'un nombre arbitraire de types dans cette lignée.

Tentative De Code

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

Démonstration En Direct

Cas D'Utilisation

Mon cas est assez typique: Dans certains iterator outils je veux extraire les "plus restrictives" itérateur de type, donc depuis il n'y a (un peu) une hiérarchie linéaire dans les itérateurs je dois à mesure de l'ascension de la hiérarchie, autant que de besoin:

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

Questions

1. Est-il plus concis / idiomatiques moyen de la manipulation de l'erreur au cas où deux ou plusieurs types sont étrangers à la hiérarchie? L'approche actuelle est de retour void , ce qui devrait donner de l'échec dans la plupart des contextes où le type est réellement utilisée.

2. Est l'utilisation d'un extra - base membre dans la première spécialisation problématique? Dois-je extraire cette fonctionnalité dans une autre classe et de l'utiliser inline en type afin de maintenir l'uniformité?

3. Est-il un algorithme qui permettrait de réduire le nombre d'instanciations? Est-il une meilleure façon que les comparaisons par paires, de sorte que la complexité de l'algorithme peut être réduit?

4. Quelqu'un peut-échelle non linéaire des hiérarchies et de la requête en fonction de la profondeur d'un arbre hiérarchique? Quel serait un bon "tie breaker" dans ce cas (pour les types dans le même niveau)?

Answer 1

1. L'aspect technique

J'avais utilisation de la dérivation, parce que c'est plus propre que les définitions de type. Voici un exemple de code:

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

Techniquement, vous pouvez utiliser std::enable_if au lieu de std::condition, mais à l'aide de std::enable_if signifierait que vous avez à tirer du si-c'est vrai, si faux et si-types-pas-compatibles cas. À l'aide de std::condition est à mon humble avis plus lisible. Le type doit être emballé une fois de plus pour avoir un type, qui pourrait être activée par les conditions et de fournir une définition de type pour l'utilisation à l'extérieur.

Afin d'obtenir une erreur de compilation, de manière statique en affirmant qu'il serait de vous donner un joli message au lieu de difficile de modèle erreurs dans la sortie du compilateur. Ensuite, vous êtes libre d'utiliser l' void pour signaler une erreur. Je vous recommande d'utiliser un type supplémentaire de nom de cette erreur. Ce qui améliore également la lisibilité.

2. Type de Base

Je pense que l' base membre doit être caché, parce que sinon vous dévoiler plus que nécessaire pour les utilisateurs et qu'il peut les confondre. L'utilisation de la dérivation de type résout ce problème.

3. La complexité

Je pense qu'il n'est pas possible d'améliorer la complexité O(n). Vous devez vérifier chaque type au moins une fois, si elle pouvait être l' LCA type. Ainsi, chaque type est au moins une fois le cadre d'une comparaison.

4. D'autres hiérarchies (la belle partie)

La mise en œuvre au-dessus (comme le vôtre) n'a pas de point sur les autres hiérarchies que ceux linéaires (par exemple, LCA<Daughter, Grandma, Son> sera de retour Grandma tout LCA<Grandma, Daughter, Son>::type entraînera une erreur de, parce que seulement le voisin types sont comparées).

Cependant, il existe deux types de "ramification de l'héritage" en C++ possible (et en le mélangeant bien sûr):

Arbre avec des racines multiples:

struct Dad {};
struct Mom {};
struct Son: Dad, Mom {};

Pour plusieurs cas, l' LCA n'est pas défini (par exemple, LCA<Mom, Dad>::type , je suppose, que Maman et Papa ne partagent pas les mêmes parents). Donc je vous conseille de laisser tomber cette affaire.

Arbre avec une racine:

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

Je recommande, l'algorithme retourne uniquement un type, si il y a un type dans la liste, à laquelle tous les types de pourrait être intégré dans (par exemple, LCA<Son, Daughter>::type n'a pas de LCA, parce que j'espère qu'ils sont frères et sœurs). Donc, nous sommes la recherche de ce type dans la liste qui est un type de base de tous les autres.

Parce que seul voisin types sont comparés les uns aux autres au-dessus, la comparaison doit être prolongée de comparer tous les type les uns avec les autres (malheureusement, ce n'est O(n^2)). Donc l'idée de base est de vérifier, pour chaque type, si c'est un ancêtre commun pour tous les autres types. C'est seulement le cas pour l' LCA. BTW: le Résoudre de cette façon a un autre avantage, parce que vous obtiendrez une erreur dans une de "multiples sources"-scénario, mais le résultat correct, si les multiples racines de rejoindre à nouveau dans une racine commune (qui fait partie de la liste).

Nous avons besoin tout d'abord d'une fonctionnalité, qui détermine si un type est un type de base de tous les autres ou pas:

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

Pour vérifier si un type est l'ancêtre commun de tous les autres, il suffit d'utiliser IsCommonAncestor<std::true_type, Mom, Grandchild, Daughter, Son>::value (qui est ici, alors IsCommonAncestor<std::true_type, Grandchild, Grandchild, Daughter, Son>::value est faux). Notez que la valeur est également faux, si un type ne fait pas partie de la hiérarchie des types.

Ensuite, une certaine "facilité" est nécessaire, pour itérer sur les types et attraper le seul, pour qui IsCommonAncestor<...>::value est vrai:

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

L'ACV compare chaque élément avec l'ensemble du paramètre de modèle pack. La première c'est le type de base de tout est utilisé. Si le dernier est également pas de type de base de tous les d'autres, LCA dérive à nouveau à partir de TypeWrapper<TypeIsNotPartOfTheHierarchy>, ce qui va lever le typique statique affirmation.

C'est très gênant. Un wrapper résoudre ce problème:

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

Code complet de l'ACV d'un arbre est disponible ici: http://ideone.com/pYEPYl

Answer 2

1. std::enable_if provoque une erreur de compilation, si le premier paramètre du modèle est faux. Une autre alternative à tomber à la définition d'un type void est le résultat d'une erreur de compilation.

2. Je pense que le modèle sera plus net si explicite l'héritage est utilisé comme un moyen de régler le type correct, voir ci-dessous.

3. Je ne vois pas comment la complexité peut être réduite au-dessous de complexité linéaire. En quelque sorte, d'une certaine façon, vous avez pour itérer sur tous les modèle les types des paramètres, afin de sélectionner l'un d'entre eux.

4. std::is_base_of n'a pas vraiment vous donner une indication de la profondeur de la sous-classe descend en dessous de la super-classe, c'est juste que l'un est une sous-classe de l'autre. En outre, avec l'héritage multiple, une sous-classe peut se produire à différents niveaux en dessous de la super-classe, donc, sur le plan sémantique, il y a un peu boueux.

De toute façon, je pense que l'utilisation d'une catégorie distincte pour effectuer les combinaisons de type de comparaison, et l'utilisation de l'héritage, semble plus propre:

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