Let's suppose that we have a linear hierarchy of types like the following:
Then what I want is a mechanism to return the lowest common ancestor out of an arbitrary number of types in that lineage.
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
My use case is rather typical: In making some iterator
tools I want to extract the "most restrictive" iterator type, so since there's (kind of) a linear hierarchy in iterators I should to able to ascent the hierarchy as much as it's needed:
LCA<Bidirectional, RandomAccess, RandomAccess> -> Bidirectional LCA<RandomAccess, Input, Forward> -> Input
Is there a more concise / idiomatic way of handling of the error case where two or more types are strangers to the hierarchy? The current approach is to return void
which hopefully will give failure in most contexts where the type is actually used.
Is the use of an extra base
member in the first specialization problematic? Should I extract that functionality in a separate class and use it inline in type
to maintain uniformity?
Is there an algorithm that would reduce the number of instantiations? Is there a better way than pairwise comparisons, so that the complexity of the algorithm can be reduced?
Can anyone scale to non linear hierarchies and query by depth a hierarchy tree? What would be a good "tie breaker" in that case (for types in the same level)?
In ontologies, the lowest common ancestor is also known as the least common ancestor. In a tree data structure where each node points to its parent, the lowest common ancestor can be easily determined by finding the first intersection of the paths from v and w to the root.
Iterative Approach If both the nodes node1 and node2 are in the right subtree, then iteratively move to the right subtree. If both the nodes node1 and node2 are in the left subtree, then iteratively move to the left subtree. Otherwise, the current node is the lowest common ancestor.
I'd use derivation, because this is cleaner than type definitions. Here is some example 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; }
Technically you could use std::enable_if
instead of std::condition
, but using std::enable_if
would mean, that you have to derive from the if-true, if-false and if-types-not-compatible case. Using std::condition
is IMHO more readable. The type has to be wrapped once more to have a type, that could be enabled by the conditions and then deliver a typedef for using it outside.
In order get a compilation error, statically asserting it would give you a nice message instead of difficult template errors in the compiler output. Then you are free to use the void
to signalize an error. I would recommend to use an extra type to name this error. This also improves readability.
I think the base
member should be hidden, because else you reveal more than needed to the users and this may confuse them. The use of type derivation solves this issue.
I think, that it is not possible to improve the complexity O(n). You have to check each type at least once, if it could be the LCA
type. So every type is at least once part of a comparison.
The implementation above (as yours too) makes no point on other hierarchies than linear ones (e.g. LCA<Daughter, Grandma, Son>
will return Grandma
while LCA<Grandma, Daughter, Son>::type
will result in an error, because only the neighbour types are compared).
However there are two types of "branching inheritance" in C++ possible (and mixing it of course):
struct Dad {}; struct Mom {}; struct Son: Dad, Mom {};
For several cases the LCA
is undefined (e.g. LCA<Mom, Dad>::type
I guess, that Mom and Dad do not share the same parents). So I would recommend to drop this case.
struct Mom {}; struct Son: Mom {}; struct Daughter: Mom {};
I would recommend, that the algorithm returns only a type, if there is one type in the list, to which all types could be casted into (e.g. LCA<Son, Daughter>::type
has no LCA, because I hope that they are siblings). So we search that type in the list that is a base type of all others.
Because only neighbour types are compared to each other above, the comparison has to be extended to compare every type with each other (sadly this is O(n^2)). So the basic idea is to check for every type, if it is a common ancestor for all other types. This is only the case for the LCA
. BTW: Solving it that way has another advantage, because you will get an error in a "multiple roots"-scenario, but the correct result, if the multiple roots are joining again in a common root (that is part of the list).
We need first of all a functionality, that determines whether one type is a base type of all other or not:
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... > {};
To check whether a type is the common ancestor of all others, simply use IsCommonAncestor<std::true_type, Mom, Grandchild, Daughter, Son>::value
(which is here true, while IsCommonAncestor<std::true_type, Grandchild, Grandchild, Daughter, Son>::value
is false). Note that, the value is also false, if one type is not part of the type hierarchy.
Then some "facility" is needed, to iterate through the types and catch the only one, for which IsCommonAncestor<...>::value
is true:
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 {};
The LCA compares every element with the whole template parameter pack. The first that is the base type of all is used. If the last is also no base type of all others, LCA derives again from TypeWrapper<TypeIsNotPartOfTheHierarchy>
, which will raise the typical static assertion.
This one is very inconvenient. A wrapper will fix this:
template<typename... Ts> struct LCA: detail::LCA<std::tuple<Ts...>, Ts...> {};
Complete code for the LCA of a tree is available here: http://ideone.com/pYEPYl
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With