What exactly are covariant return types in C++?

Question

I get a compile error when I try to do this:

class A
{
    virtual std::vector<A*> test() { /* do something */ };
}

class B: public A
{
    virtual std::vector<B*> test() { /* do something */ };
}

I assume that A and B are covariant types, and hence A* and B* should also be (Correct?) By inference, I would have expected that std::vector<A*> and std::vector<B*> should be covariant as well, but this does not seem to be the case. Why?

Tragedy

My guess is that would allow B b = ...; vector<A*> x = b.test(); and now we you can add A* objects to a vector of Bs, which breaks the guarantees of vector<B*>. However my knowledge of C++ is very limited. – Kendakendal

Possible duplicate of C++, polymorphism vs. templatization of a function argument. Well, one of the answers there is an exact duplicate of one of the answers here. – Remise

Answer 1

Covariant return types allow overridden virtual member functions in a derived class to return a different type of object, as long as it can be used in all the same ways as the base class's return type. Computer scientists have (ever since Barbara Liskov) a theoretical definition of "can be used in the same ways": substitutability.

No, std::vector<B*> is not a subtype of std::vector<A*>, nor should it be.

For example, std::vector<B*> doesn't support the push_back(A*) operation, so it is not substitutable.

C++ doesn't try to infer subtype relationships for templates at all. The relationship will only exist if you actually specialize one and specify a base class. One reason for this, even on interfaces which are theoretically covariant (basically, read-only), is that C++'s version is actually stronger than Liskov substitution -- in C++ the compatibility has to exist at a binary level. Since the memory layout of collections of related objects may not match subobject placement, this binary compatibility isn't achieved. The restriction of covariant return types to be only pointers or references is also a consequence of the binary compatibility issue. A derived object probably wouldn't fit in the space reserved for the base instance... but its pointer will.

Cattery

re "The restriction of covariant return types to be only pointers or references is also a consequence of the binary compatibility issue." sounds likely on the surface. But it's not a clincher argument. Consider that it's trivial (for the compiler) to implement a check of required result storage size for a virtual function. This would be the cost of one implementation. Due to the C++ principle of not paying for what you don't use, general covariant functions would then have to be marked as such. So then we're into costs, of language complexity, execution time, code size, versus payoff. – Goglet

There is also another consideration, namely that the usual "manual" implementation of covariance for e.g. a smart pointer as function result, relies on computed conversion rather than a base class relationship. So a C++ feature for covariant results based on inheritance, would not help with smart pointers, i.e. would not help with what seems to be most common case. :( – Goglet

@Alf: And a specific implementation could, as an extension, permit that, if the sizing issue were the only implication of binary compatibility. Calling the right destructor would be another issue of concern to a by-value covariant return. – Cattery

Answer 2

An apple is a fruit.

A bag of apples is not a bag of fruit. That's because you can put a pear in a bag of fruit.

Remise

You can put a pear in a bag of apples, you should only not mix bananas with other fruit. :-P – Modulator

You of course mean a handle to the pear. Otherwise you might end up with pear slices. – Cattery

@Kay: You can put a (handle to a) pear into a bag of fruit containing apples. But not into a bag of apples. – Cattery

@Kay except strawberries... bananas and strawberries sliced, with a bit of lemon juice and sugar... yummy! – Kendakendal

@BenVoigt Strangely I happen to have a bag of fruit in my kitchen and I've just picked an apple and a pear. No slices or handles inside as far as I can see. – Remise

@n.m. From the observed behavior, it sounds as if you may actually have a bag<std::unique_ptr<fruit>> – Cattery

@BenVoigt Spare me the technical terms, I just want a delicious juicy bite of an apple! Mmm... – Remise

@Kay: This reminds me of the old Groucho Marx saw: Time flies like an arrow, fruit flies like a banana. – Tragedy

a bag of apples IS a bag of fruit. A bag of fruit isn't necessarily a bag of apples. – Sclerotomy

Answer 3

The C++ FAQ answers this directly in [21.3] Is a parking-lot-of-Car a kind-of parking-lot-of-Vehicle? ("You don't have to like it. But you do have to accept it.")

SO question Getting a vector into a function that expects a vector is asking the same thing. And the answer is that while it seems safe at first to allow covariance of generic types, in particular containers of a derived type being treated as containers of the base type, it is quite unsafe.

Consider this code:

class Vehicle {};
class Car : public Vehicle {};
class Boat : public Vehicle {};

void add_boat(vector<Vehicle*>& vehicles) { vehicles.push_back(new Boat()); }

int main()
{
  vector<Car*> cars;
  add_boat(cars);
  // Uh oh, if that worked we now have a Boat in our Cars vector.
  // Fortunately it is not legal to convert vector<Car*> as a vector<Vehicle*> in C++.
}

Setting

Answer 4

The standard defines covariance for C++ purposes in §10.3 [class.virtual]/p7:

The return type of an overriding function shall be either identical to the return type of the overridden function or covariant with the classes of the functions. If a function D::f overrides a function B::f, the return types of the functions are covariant if they satisfy the following criteria:

• both are pointers to classes, both are lvalue references to classes, or both are rvalue references to classes¹¹³
• the class in the return type of B::f is the same class as the class in the return type of D::f, or is an unambiguous and accessible direct or indirect base class of the class in the return type of D::f
• both pointers or references have the same cv-qualification and the class type in the return type of D::f has the same cv-qualification as or less cv-qualification than the class type in the return type of B::f.

¹¹³Multi-level pointers to classes or references to multi-level pointers to classes are not allowed.

Your functions fail on the first point, and, even if you bypass it, fails on the second - std::vector<A*> is not a base of std::vector<B*>.

Roanna

First point is easy enough to work around. Bigger problem is the second. – Cattery

Answer 5

Templates do not "inherit" covariance, because different template specializations may be completely 100% unrelated:

template<class T> struct MD;

//pets
template<> struct MD<A*> 
{
    std::string pet_name;
    int pet_height;
    int pet_weight;
    std::string pet_owner;
};

//vehicles
template<> struct MD<B*>
{
    virtual ~MD() {}
    virtual void fix_motor();
    virtual void drive();
    virtual bool is_in_the_shop()const;
}

std::vector<MD<A*>> get_pets();

How would you feel if get_pets returned a vector where some of those were actually vehicles instead? It seems to defeat the point of the type system right?

Radu

Writable collections aren't covariant, regardless of specialization. – Cattery

Answer 6

This doesn't work because

1. you are not returning pointers or references, which is required for covariant returns to work; and
2. Foo<B> and Foo<B> have no inheritance relationship regardless of Foo, A and B (unless there's a specialization that makes it so).

But we can work around that. First, note that std::vector<A*> and std::vector<B*> are not substitutable for each other, regardless of any language restrictions, simply because std::vector<B*> cannot support adding an A* element to it. So you cannot even write a custom adapter that makes std::vector<B*> a substitute of std::vector<A*>

But a read-only container of B* can be adapted to look like a read-only container of A*. This is a multi-step process.

Create an abstract class template that exports a readonly container-like interface

template <class ApparentElemType>
struct readonly_vector_view_base
{
    struct iter
    {
        virtual std::unique_ptr<iter> clone() const = 0;

        virtual ApparentElemType operator*() const = 0;
        virtual iter& operator++() = 0;
        virtual iter& operator--() = 0;
        virtual bool operator== (const iter& other) const = 0;
        virtual bool operator!= (const iter& other) const = 0;
        virtual ~iter(){}
    };

    virtual std::unique_ptr<iter> begin() = 0;
    virtual std::unique_ptr<iter> end() = 0;

    virtual ~readonly_vector_view_base() {}
};

It return pointers to iterators, not iterators themselves, but don't worry, this class will be only used by an STL-like wrapper anyway.

Now create a concrete wrapper for readonly_vector_view_base and its iterator, so that it contains a pointer to, and delegate its operations to, a readonly_vector_view_base.

template <class ApparentElemType>
class readonly_vector_view
{
  public:
    readonly_vector_view(const readonly_vector_view& other) : pimpl(other.pimpl) {}
    readonly_vector_view(std::shared_ptr<readonly_vector_view_base<ApparentElemType>> pimpl_) : pimpl(pimpl_) {}

    typedef typename readonly_vector_view_base<ApparentElemType>::iter iter_base;
    class iter
    {
      public:
        iter(std::unique_ptr<iter_base> it_) : it(it_->clone()) {}
        iter(const iter& other) : it(other.it->clone()) {}
        iter& operator=(iter& other) { it = other.it->clone(); return *this; }

        ApparentElemType operator*() const { return **it; }

        iter& operator++() { ++*it; return *this; }
        iter& operator--() { --*it; return *this; }
        iter operator++(int) { iter n(*this); ++*it; return n; }
        iter operator--(int) { iter n(*this); --*it; return n; }

        bool operator== (const iter& other) const { return *it == *other.it; }
        bool operator!= (const iter& other) const { return *it != *other.it; }
      private:
        std::unique_ptr<iter_base> it;
    };

    iter begin() { return iter(pimpl->begin()); }
    iter end() { return iter(pimpl->end()); }
  private:
    std::shared_ptr<readonly_vector_view_base<ApparentElemType>> pimpl;
};

Now create a templatized implementation for readonly_vector_view_base that looks at a vector of a differently typed elements:

template <class ElemType, class ApparentElemType>
struct readonly_vector_view_impl : readonly_vector_view_base<ApparentElemType>
{
    typedef typename readonly_vector_view_base<ApparentElemType>::iter iter_base;

    readonly_vector_view_impl(std::shared_ptr<std::vector<ElemType>> vec_) : vec(vec_) {}

    struct iter : iter_base
    {
        std::unique_ptr<iter_base> clone() const { std::unique_ptr<iter_base> x(new iter(it)); return x; }

        iter(typename std::vector<ElemType>::iterator it_) : it(it_) {}

        ApparentElemType operator*() const { return *it; }

        iter& operator++() { ++it; return *this; }
        iter& operator--() { ++it; return *this; }

        bool operator== (const iter_base& other) const {
            const iter* real_other = dynamic_cast<const iter*>(&other);
            return (real_other && it == real_other->it);
        }
        bool operator!= (const iter_base& other) const { return ! (*this == other); }

        typename std::vector<ElemType>::iterator it;
    };

    std::unique_ptr<iter_base> begin() {
        iter* x (new iter(vec->begin()));
        std::unique_ptr<iter_base> y(x);
        return y;
    }
    std::unique_ptr<iter_base> end() {
        iter* x (new iter(vec->end()));;
        std::unique_ptr<iter_base> y(x);
        return y;
    }

    std::shared_ptr<std::vector<ElemType>> vec;
};

OK, as long as we have two types where one is convertible to another, such as A* and B*, we can view a vector of B* as if it's a vector of A*.

But what does it buy us? readonly_vector_view<A*> is still unrelated to readonly_vector_view<B*>! Read on...

It turns out that the covariant return types are not really necessary, they are a syntactic sugar to what is available in C++ otherwise. Suppose C++ doesn't have covariant return types, can we simulate them? It's actually pretty easy:

class Base
{
   virtual Base* clone_Base() { ... actual impl ... }
   Base* clone() { return clone_Base(); } // note not virtual 
};

class Derived : public Base
{
   virtual Derived* clone_Derived() { ... actual impl ... }
   virtual Base* clone_Base() { return clone_Derived(); }
   Derived* clone() { return clone_Derived(); } // note not virtual 

};

It's actually pretty easy and there's no requirement for the return type to be pointers or references, or have an inheritance relationship. It is enough that there is a conversion:

class Base
{
   virtual shared_ptr<Base> clone_Base() { ... actual impl ... }
   shared_ptr<Base> clone() { return clone_Base(); } 
};

class Derived : public Base
{
   virtual shared_ptr<Derived> clone_Derived() { ... actual impl ... }
   virtual shared_ptr<Base> clone_Base() { return clone_Derived(); }
   shared_ptr<Derived> clone() { return clone_Derived(); } 
};

In a similar fashion, we can arrange A::test() to return a readonly_vector_view<A*>, and B::test() to return a readonly_vector_view<B*>. Since these functions are now not virtual, there is no requirement for their return types to be in any relationship. One just hides the other. But inside they call a virtual function that creates (say) a readonly_vector_view<A*> implemented in terms of readonly_vector_view_impl<B*, A*> which is implemented in terms of vector<B*>, and everything works just as if they were real covariant return types.

struct A
{
    readonly_vector_view<A*> test() { return test_A(); }
    virtual readonly_vector_view<A*> test_A() = 0;
};

struct B : A
{
    std::shared_ptr<std::vector<B*>> bvec;

    readonly_vector_view<B*> test() { return test_B(); }

    virtual readonly_vector_view<A*> test_A() {
        return readonly_vector_view<A*>(std::make_shared<readonly_vector_view_impl<B*, A*>>(bvec));
    }
    virtual readonly_vector_view<B*> test_B() {
        return readonly_vector_view<B*>(std::make_shared<readonly_vector_view_impl<B*, B*>>(bvec));
    }
};

Piece of cake! Live demo Totally worth the effort!

Anticatalyst

This is not a complete implementation of a vector_view, just a proof of concept. A complete implementation would be many many times longer. – Remise

Not sure why this was edited but the edit didn't go to well, some code is lost and other is de-formatted. – Remise

Answer 7

Covariance only happens when you are returning a pointer or a reference to a class, and the classes are related by inheritance.

This is clearly not happening, both because std::vector<?> is not a pointer nor reference, and because two std::vector<?>s have no parent/child relationship.

Now, we can make this work.

Step 1, create an array_view class. It has a begin and end pointer and methods and a size method and all you might expect.

Step 2, create an shared_array_view, which is an array view that also owns a shared_ptr<void> with a custom deleter: it is otherwise identical. This class also insures that the data it is viewing lasts long enough to be viewed.

Step 3, create a range_view, which is a pair of iterators and dressing on it. Do the same with a shared_range_view with an ownership token. Modify your array_view to be a range_view with some extra guarantees (contiguous iterators mainly).

Step 4, write a converting iterator. This is a type that stores an iterator over value_type_1 which either calls a function, or implicitly converts to a const_iterator over value_type_2.

Step 5, Write a range_view< implicit_converting_iterator< T*, U* > > returning function for when T* can be implicitly converted to U*.

Step 6, write type erasers for the above

class A {
  owning_array_view<A*> test_() { /* do something */ }
  virtual type_erased_range_view<A*> test() { return test_(); };
};

class B: public A {
  owning_array_view<B*> test_() { /* do something */ };
  virtual type_erased_range_view<A*> test() override {
    return convert_range_to<A*>(test_());
  }
};

Most of what I describe has been done by boost.

Sycosis

There's no covariance here. Users of b.test() directly don't see a more specific return type than users via (A&)b – Cattery

Alas, the return types are the same for A::test and B::test. – Remise