template plantillas c++ templates c++11 variadic-templates template-meta-programming

plantillas - template function c++



Ancestro común más bajo en un linaje lineal de tipos (2)

1. aspecto técnico

Usaría la derivación, porque esto es más limpio que las definiciones de tipo. Aquí hay un código de ejemplo:

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

Técnicamente, podría usar std::enable_if lugar de std::condition , pero usar std::enable_if significaría que debe derivar del caso if-true, if-false y if-types-not-compatible. El uso de std::condition es en mi humilde opinión más legible. El tipo tiene que ser envuelto una vez más para tener un tipo, que podría ser habilitado por las condiciones y luego entregar un typedef para usarlo en el exterior.

Para obtener un error de compilación, afirmar estáticamente le daría un buen mensaje en lugar de errores de plantilla difíciles en la salida del compilador. Entonces eres libre de usar el void para señalar un error. Yo recomendaría usar un tipo extra para nombrar este error. Esto también mejora la legibilidad.

2. Tipo de base

Creo que el miembro de la base debe estar oculto, porque si no revelas más de lo necesario a los usuarios y esto puede confundirlos. El uso de la derivación de tipo resuelve este problema.

3. Complejidad

Creo que no es posible mejorar la complejidad O (n). Debe verificar cada tipo al menos una vez, si es del tipo LCA . Entonces, cada tipo es al menos una vez parte de una comparación.

4. Otras jerarquías (la parte hermosa)

La implementación anterior (como la tuya) no tiene sentido en otras jerarquías que las lineales (por ejemplo, LCA<Daughter, Grandma, Son> devolverá a la Grandma mientras que LCA<Grandma, Daughter, Son>::type dará como resultado un error, porque solo los tipos vecinos son comparados).

Sin embargo, hay dos tipos de "herencia de ramificación" en C ++ posibles (y la mezcla, por supuesto):

Árbol con múltiples raíces:

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

En varios casos, el LCA no está definido (por ejemplo, LCA<Mom, Dad>::type , supongo, que mamá y papá no comparten los mismos padres). Así que recomendaría dejar este caso.

Árbol con una raíz:

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

Yo recomendaría, que el algoritmo devuelva solo un tipo, si hay un tipo en la lista, en el que se puedan incluir todos los tipos (por ejemplo, LCA<Son, Daughter>::type no tiene LCA, porque espero que sean hermanos). Entonces buscamos ese tipo en la lista que es un tipo base de todos los demás.

Debido a que solo los tipos vecinos se comparan entre sí anteriormente, la comparación tiene que extenderse para comparar cada tipo entre sí (por desgracia, esto es O (n ^ 2)). Entonces la idea básica es verificar para cada tipo, si es un ancestro común para todos los otros tipos. Este es solo el caso del LCA . Por cierto: resolverlo de esa manera tiene otra ventaja, porque obtendrá un error en un "multi roots" -scenario, pero el resultado correcto, si las múltiples raíces se están uniendo nuevamente en una raíz común (que es parte de la lista).

Primero, necesitamos una funcionalidad que determine si un tipo es un tipo base de todos los demás o no:

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

Para verificar si un tipo es el ancestro común de todos los demás, simplemente use IsCommonAncestor<std::true_type, Mom, Grandchild, Daughter, Son>::value (que aquí es verdadero, mientras que IsCommonAncestor<std::true_type, Grandchild, Grandchild, Daughter, Son>::value es falso). Tenga en cuenta que, el valor también es falso, si un tipo no forma parte de la jerarquía de tipos.

Entonces se necesita alguna "instalación", para recorrer los tipos y capturar el único, para el cual IsCommonAncestor<...>::value es verdadero:

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

El LCA compara cada elemento con el paquete de parámetros de la plantilla completa. El primero que es el tipo de base de todo se usa. Si el último tampoco es un tipo base de todos los demás, el LCA se deriva nuevamente de TypeWrapper<TypeIsNotPartOfTheHierarchy> , que elevará la aserción estática típica.

Este es muy inconveniente. Un contenedor solucionará esto:

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

El código completo para el LCA de un árbol está disponible aquí: http://ideone.com/pYEPYl

Introducción

Supongamos que tenemos una jerarquía lineal de tipos como la siguiente:

Entonces, lo que quiero es un mecanismo para devolver el ancestro común más bajo de un número arbitrario de tipos en ese linaje.

Intento de código

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

Demo en vivo

Caso de uso

Mi caso de uso es bastante típico: al hacer algunas herramientas de iterator , quiero extraer el tipo de iterador "más restrictivo", así que como hay (algo así como) una jerarquía lineal en iteradores debería poder ascender la jerarquía tanto como sea necesario:

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

Preguntas

  1. ¿Hay una manera más concisa / idiomática de manejar el caso de error donde dos o más tipos son extraños para la jerarquía? El enfoque actual es devolver el void que con suerte dará fallas en la mayoría de los contextos donde se usa realmente el tipo.

  2. ¿El uso de un miembro base adicional en la primera especialización es problemático? ¿Debo extraer esa funcionalidad en una clase separada y usarla en línea para mantener la uniformidad ?

  3. ¿Hay algún algoritmo que reduzca el número de instancias ? ¿Hay una mejor manera que las comparaciones por pares, de modo que se pueda reducir la complejidad del algoritmo?

  4. ¿Alguien puede escalar jerarquías no lineales y consultar por profundidad un árbol de jerarquía? ¿Qué sería un buen "desempate" en ese caso (para tipos en el mismo nivel)?

  1. std::enable_if da std::enable_if resultado un error de compilación, si el primer parámetro de plantilla es falso. Otra alternativa para volver a definir un tipo vacío es dar como resultado un error de compilación.

  2. Creo que la plantilla será más clara si se utiliza la herencia explícita, como un medio para resolver el tipo correcto, ver a continuación.

  3. No veo cómo se puede reducir la complejidad por debajo de la complejidad lineal. De alguna manera, de alguna manera, debe iterar sobre todos los tipos de parámetros de la plantilla, para seleccionar uno de ellos.

  4. std :: is_base_of realmente no le da una indicación de qué tan profunda es la subclase debajo de la superclase, solo que esa es una subclase de la otra. Además, con la herencia múltiple, una subclase dada podría ocurrir en diferentes niveles debajo de la superclase, por lo que la semántica está un poco embarrada.

De todos modos, creo que el uso de una clase separada para realizar la comparación de tipo por pares, y el uso de la herencia, se ve más limpio:

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