When Is C++ Covariance the Best Solution

What are the drawbacks of C++ covariance return types?

The chief limitation of covariant return types as implemented in C++ is that they only work with raw pointers and references. There are no real reasons not to use them when possible, but the limitation means we cannot always use them when we need them.

It is easy to overcome this limitation while providing identical user experience, without ever relying to the language feature. Here's how.

Let's rewrite our classes using the common and popular non-virtual interface idiom.

struct AbstractFactory
{
    Base *create() {
      return create_impl();
    }

  private:
    virtual Base* create_impl() = 0;
};

struct ConcreteFactory : public AbstractFactory
{
    Derived *create() {
      return create_impl();
    }

  private:
    Derived *create_impl() override {
        return new Derived;
    }
};

Now here something interesting happens. create is no longer virtual, and therefore can have any return type. It is not constrained by the covariant return types rule. create_impl is still constrained, but it's private, no one is calling it but the class itself, so we can easily manipulate it and remove covariance altogether.

struct ConcreteFactory : public AbstractFactory
{
    Derived *create() {
      return create_impl();
    }

  private:
    Base *create_impl() override {
        return create_impl_derived();
    }

    virtual Derived *create_impl_derived() {
        return new Derived;
    }
};

Now both AbstractFactory and ConcreteFactory has exactly the same interface as before, without a covariant return type in sight. What does it mean for us? It means we can use smart pointers freely.

// replace `sptr` with your favourite kind of smart pointer

struct AbstractFactory
{
    sptr<Base> create() {
      return create_impl();
    }

  private:
    virtual sptr<Base> create_impl() = 0;
};

struct ConcreteFactory : public AbstractFactory
{
    sptr<Derived> create() {
      return create_impl();
    }

  private:
    sptr<Base> create_impl() override {
        return create_impl_derived();
    }

    virtual sptr<Derived> create_impl_derived() {
        return make_smart<Derived>();
    }
};

Here we overcame a language limitation and provided an equivalent of covariant return types for our classes without relying on a limited language feature.

Note for the technically inclined.

    sptr<Base> create_impl() override {
        return create_impl_derived();
    }

This here function implicitly converts ("upcasts") a Derived pointer to a Base pointer. If we use covariant return types as provided by the language, such upcast is inserted by the compiler automatically when needed. The language is unfortunately only smart enough to do it for raw pointers. For everything else we have to do it ourselves. Luckily, it's relatively easy, if a bit verbose.

(In this particular case it could be acceptable to just return a Base pointer throughout. I'm not discussing this. I'm assuming we absolutely need something like covariant return types.)

C++ covariance in parameters

The return type is permissible since derived inherits from base, but the function parameter can't work - not all base instances will be a derived also. What's supposed to happen in the cases where func is called on a pointer to base with a parameter that's not a derived? The most derived implementation isn't callable.

Is there a way to forward declare covariance?

You can fake it quite easily, but you lose the static type checking. If you replace the dynamic_casts by static_casts, you have what the compiler is using internally, but you have no dynamic nor static type check:

class Foo;
class Bar;

class Foo
{
public:
  Bar* bar();
protected:
  virtual Bar* doBar();
};

class Bar;
{
public:
  Foo* foo();
public:
  virtual Foo* doFoo();
};

inline Bar* Foo::bar() { return doBar(); }
inline Foo* Bar::foo() { return doFoo(); }

class ConcreteFoo;
class ConcreteBar;
class ConcreteFoo : public Foo
{
public:
  ConcreteBar* bar();
protected:
  Bar* doBar();
};

class ConcreteBar : public Bar
{
public:
   ConcreteFoo* foo();
public:
   Foo* doFoo();
};

inline ConcreteBar* ConcreteFoo::bar() { return &dynamic_cast<ConcreteBar&>(*doBar()); }
inline ConcreteFoo* ConcreteBar::foo() { return &dynamic_cast<ConcreteFoo&>(*doFoo()); }

C++ containers, covariance and template

You can let Derived::getData() return QVector<Data*>. When you need to use it, find out if the pointers in QVector is to Data or DerivedData, using dynamic_cast or similar method.

Fast implementation of covariance of two 8-bit arrays

I have another nice solution!

At first I want to mention some mathematical formulas:

averageX = Sum(x[i])/size;
averageY = Sum(y[i])/size;

And therefore:

Sum((x[i] - averageX)*(y[i] - averageY))/size = 

Sum(x[i]*y[i])/size - Sum(x[i]*averageY)/size - 
Sum(averageX*y[i])/size + Sum(averageX*averageY)/size = 

Sum(x[i]*y[i])/size - averageY*Sum(x[i])/size - 
averageX*Sum(y[i])/size + averageX*averageY*Sum(1)/size =   

Sum(x[i]*y[i])/size - averageY*averageX - 
averageX*averageY + averageX*averageY = 

Sum(x[i]*y[i])/size - averageY*averageX;     

It allows to modify our algorithm:

float SigmaXY(const uint8_t * x, const uint8_t * y, size_t size, float averageX, float averageY)
{
    uint32_t sum = 0; // If images will have size greater then 256x256 than you have to use uint64_t.
    for(size_t i = 0; i < size; ++i)
        sum += x[i]*y[i];
    return sum / size - averageY*averageX;
} 

And only after that we can use SIMD (I used SSE2):

#include <emmintrin.h>

inline __m128i SigmaXY(__m128i x, __m128i y)
{
    __m128i lo = _mm_madd_epi16(_mm_unpacklo_epi8(x, _mm_setzero_si128()), _mm_unpacklo_epi8(y, _mm_setzero_si128()));
    __m128i hi = _mm_madd_epi16(_mm_unpackhi_epi8(y, _mm_setzero_si128()), _mm_unpackhi_epi8(y, _mm_setzero_si128()));
    return _mm_add_epi32(lo, hi);
}

float SigmaXY(const uint8_t * x, const uint8_t * y, size_t size, float averageX, float averageY)
{
    uint32_t sum = 0;
    size_t i = 0, alignedSize = size/16*16;
    if(size >= 16)
    {
        __m128i sums = _mm_setzero_si128();
        for(; i < alignedSize; i += 16)
        {
            __m128i _x = _mm_loadu_si128((__m128i*)(x + i));
            __m128i _y = _mm_loadu_si128((__m128i*)(y + i));
            sums = _mm_add_epi32(sums, SigmaXY(_x, _y));
        }
        uint32_t _sums[4];
        _mm_storeu_si128(_sums, sums);
        sum = _sums[0] + _sums[1] + _sums[2] + _sums[3];
    } 
    for(; i < size; ++i)
        sum += x[i]*y[i];
    return sum / size - averageY*averageX;
}

---

Related Topics