Determine if a type is of a more derived type than another at runtime

[LB]

I have a function like this:

template<typename T>
void f()
{
    //...
}

Is there any way I can construct a list of the types it is called with ordered from least derived to most derived? E.g.:

struct A {};
struct B : A {};
struct C : A {};
struct D : B, C {};
struct E : D {};

f<D>();
f<C>();
f<A>();
f<B>();
f<E>();

//list contains, in order: A, B and C in any order, D, E 

I am thinking it is possible with some clever template and polymorphism combos, but maybe not. As a last resort I know how to make it work by storing static type information in each class, but I'd like to avoid that if possible.

[JLBorges]

Intrusive:

#include <typeindex>
#include <type_traits>
#include <set>
#include <utility>
#include <iostream>

template < typename... > struct index_of { static constexpr int value = 0 ; };
template < typename... T > constexpr int index_of<T...>::value ;

template < typename T > struct index_of< T, decltype(T::index) >
{ static constexpr int value = T::index ; };
template < typename T > constexpr int index_of< T, decltype(T::index) >::value ;

static std::set< std::pair< int, std::type_index > > foo_types ;

template < typename T > void foo( T&& )
{
    using unqualified_type = typename std::remove_reference<T>::type ;
    foo_types.emplace( index_of<unqualified_type>::value, typeid(unqualified_type) ) ;

    for( auto pair : foo_types ) std::cout << pair.second.name() << ' ' ;
    std::cout << '\n' ;
}

template < typename... > struct base ;

template < typename BASE > struct base<BASE> : BASE
{ static constexpr int index = index_of<BASE>::value + 1 ; };

template < typename FIRST, typename... REST >
struct base< FIRST, REST... > : FIRST, REST...
{
    static constexpr int a = index_of<FIRST>::value ;
    static constexpr int b = index_of< base< REST... > >::value ;
    static constexpr int index = ( a < b ? b : a ) + 1 ;
};

struct A {};
struct B : base<A> {};
struct C : base<A> {};
struct D : base<B,C> {};
struct E : base<D> {};

int main()
{
     foo( D{} ) ; // D
     foo( B{} ) ; // B D
     foo( A{} ) ; // A B D
     foo( E{} ) ; // A B D E
     B b ; foo(b) ; // A B D E
     foo( C{} ) ; // A B C D E
}

http://coliru.stacked-crooked.com/a/6602c02f3f80c13d

Note: Fails with clang++ libc++ on linux, haven't investigated why.

[LB]

I have a working intrusive implementation already for another module, though I have not tested if it works under libc++ on linux yet.

[JLBorges]

The very same technique can be used in a non-intrusive manner.

I prefer the intrusive implementation; it does not have any run-time cost (ebo).

This non-intrusive implementation requires centralized knowledge of all the types in the hierarchies involved.
(One line requires manual maintenance when new derived classes are added.)

#include <typeindex>
#include <type_traits>
#include <set>
#include <utility>
#include <iostream>

template< typename... > struct type_seq {};

template< typename, typename... > struct depth_of ;

template< typename T, typename U > struct depth_of< T, type_seq<U> >
{ static constexpr int value = std::is_base_of<U,T>::value ; };

template< typename T, typename U > constexpr int depth_of< T, type_seq<U> >::value ;

template< typename T, typename FIRST, typename... REST  >
struct depth_of< T, type_seq< FIRST, REST... > >
{
    static constexpr int value = std::is_base_of<FIRST,T>::value +
                                 depth_of< T, type_seq<REST...> >::value ;
};

template< typename T, typename FIRST, typename... REST  >
constexpr int depth_of< T, type_seq< FIRST, REST... > >::value ;

static std::set< std::pair< int, std::type_index > > foo_types ;

template < typename TYPE_LIST, typename T > void foo( T&&  )
{
    using type = typename std::remove_cv< typename std::remove_reference<T>::type >::type ;
    foo_types.emplace( depth_of< type, TYPE_LIST >::value, typeid(type) ) ;

    for( auto pair : foo_types ) std::cout << pair.second.name() << ' ' ;
    std::cout << '\n' ;
}

struct A {};
struct B : A {};
struct C : A {};
struct D : B, C {};
struct E : D {};

namespace my
{
    // *** this type_seq needs to be maintained manually
    using types = type_seq< int, C, char, E, B, std::ios, A, std::ostream, D, double > ;
    template < typename T > void foo( T&& v ) { ::foo<types>( std::forward<T>(v) ) ; }
}

struct X {} ;

int main()
{
     my::foo( D{} ) ;
     my::foo( B{} ) ;
     my::foo( std::cout.flags() ) ;
     my::foo( A{} ) ;
     my::foo( std::cout ) ;
     my::foo( E{} ) ;
     B b ; my::foo(b) ;
     X xyz ; my::foo(xyz) ;
     my::foo( C{} ) ;
}

http://coliru.stacked-crooked.com/a/e3b3a550e50514ce

[LB]

Hmm, while I don't mind the runtime overhead for this case, I think I will just be forced to use an intrusive solution. Thanks though, I really appreciate your help!

[JLBorges]

The non-intrusive version too does not have any extra run-time overhead;
my reservations were about 'requires centralized knowledge of all the types in the hierarchies involved.'

The non-intrusive version appears to work as expected with clang++ / libc++ / linux too.
X bitmask-type A C B ostream D E is right. (B and C may be in any order.)
(I inadvertently omitted to remove the 'fails' tag in the echoed output.)

[LB]

Yeah, my problem is that I will never be able to know of all the types involved at compile time as my code will be used as a library.