Самый низкий общий предок в линейной линии типов

Ответ 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 case. Использование std::condition является IMHO более читаемым. Тип должен быть завернут еще раз, чтобы иметь тип, который может быть включен условиями, а затем доставить typedef для его использования снаружи.

Чтобы получить ошибку компиляции, статически утверждающее это даст вам приятное сообщение вместо сложных ошибок шаблона в выводе компилятора. Затем вы можете использовать void, чтобы сигнализировать об ошибке. Я бы рекомендовал использовать дополнительный тип, чтобы назвать эту ошибку. Это также улучшает читаемость.

2. Базовый тип

Я думаю, что член base должен быть скрыт, потому что иначе вы обнаружите больше, чем нужно пользователям, и это может смутить их. Использование вывода типа решает эту проблему.

3. Сложность

Я думаю, что невозможно улучшить сложность O (n). Вы должны проверять каждый тип хотя бы один раз, если это может быть тип LCA. Таким образом, каждый тип является хотя бы частью сравнения.

4. Другие иерархии (красивая часть)

Реализация выше (как и ваша) не имеет смысла в других иерархиях, чем линейные (например, LCA<Daughter, Grandma, Son> вернет Grandma, а LCA<Grandma, Daughter, Son>::type приведет к ошибке, потому что сравниваются только соседние типы).

Однако существует два типа "наследования ветвления" на С++ (и, конечно, смешение):

Дерево с несколькими корнями:

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

В некоторых случаях LCA есть undefined (например, LCA<Mom, Dad>::type Я думаю, что у мамы и папы нет одинаковых родителей). Поэтому я бы рекомендовал отказаться от этого случая.

Дерево с одним корнем:

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

Я бы рекомендовал, чтобы алгоритм возвращал только тип, если в списке есть один тип, к которому могут быть добавлены все типы (например, LCA<Son, Daughter>::type не имеет LCA, потому что я надеюсь, что они являются братьями и сестрами). Поэтому мы ищем этот тип в списке, который является базовым типом всех остальных.

Поскольку только соседние типы сравниваются друг с другом выше, сравнение должно быть расширено для сравнения каждого типа друг с другом (к сожалению, это O (n ^ 2)). Поэтому основная идея состоит в том, чтобы проверять каждый тип, если он является общим предком для всех других типов. Это относится только к LCA. BTW: Решение этого способа имеет еще одно преимущество, потому что вы получите ошибку в "кратном корне" -ценоном, но правильный результат, если несколько корней снова объединяются в общий корень (который является частью списка).

Нам нужна прежде всего функциональность, которая определяет, является ли один тип базовым типом всего другого или нет:

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). Обратите внимание, что значение также неверно, если один тип не является частью иерархии типов.

Затем требуется некоторое "средство", чтобы перебирать типы и улавливать единственный, для которого 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

Ответ 2

• std::enable_if приводит к ошибке компиляции, если первый параметр шаблона является ложным. Другой альтернативой возврату к определению типа void является ошибка компиляции.

• Я думаю, что шаблон будет более аккуратным, если используется явное наследование, как средство разрешения правильного типа, см. ниже.

• Я не вижу, как сложность может быть уменьшена ниже линейной сложности. Так или иначе, вам нужно перебрать все типы параметров шаблона, чтобы выбрать один из них.

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