Inheritance of interface implementation in C++

I'm trying to improve legacy code with following COM interfaces structure:

IBase <- IMammal <- IPet <- ICat
                  \       \- IDog
                   \
                    \- ICattle <- ICow

I can't rearrange or change this interface, but I'd like to improve implementations. We have several implementations:

CMammal <- CPet <- CCat
         \       \- CDog
          \
           \- CCattle <- CCow

So, we have some common mammal implementation CMammal::age(), CMammal::sex(), some pet implementation: CPet::findBed(), CPet::goThrowughStairs()

And some cattle/cow implementation: CCattle::goShed(), CCow::moo().

The problem: I'd like to propagate age(), sex() implementation to pets as well as to cattle, but I have no idea how should I do this.

Straighforward solution looks impossible to me:

class CPet : CMammal, IPet { ... } 

because both CMammal and IPet are derived from IBase, so CCat::foo() { IBase::bar(); } will fail to compile because IBase is ambiguous.

The only solution I managed to find is to use template class for implementations:

template <typename Interface> class CMammal : Interface 
    { ... };
template <typename Interface> class CPet : CMammal<Interface >
    { ... };
template <typename Interface> class CCattle : Interface  
    { ... };

// "end-point" classes:
class CCat : CPet<ICat> { ... }; // maybe, at least it able to compile
class CDog : CPet<IDog> { ... };
class CCow : CCattle<ICow> { ... }; 

That solution looks at list possible to implement in terms of C++, but there is issue: template classes has to be declared in header, so I got a lot of very big headers, possibly slower compilation and I'm not sure what will happen with binary size.

So, I'm still looking for a better solution and got stuck at this point.

Is there any idea how to implemnt this in more clear and efficient way? Maybe, some ideas about what I have to learn about?

Old alternative is several defines like this:

#define DECLARE_MAMMAL     int sex(); int age();
#define DEFINE_MAMMAL(cls) int cls::sex() { ...; } int cls::age() { ...; } 

class CCat : ICat
{
   DECLARE_PET
   DECLARE_MAMMAL
   ...
};

// -.cpp-
DEFINE_PET(CCat)
DEFINE_MAMMAL(Cat)

// -.h-
class CCow : ICow
{
   DECLARE_CATTLE
   DECLARE_MAMMAL
   ...
};

// -.cpp-
DEFINE_CATTLE(CCow)
DEFINE_MAMMAL(CCow)

This solution has short headers, no copy-paste, but extreemely hard to debug.