2

The Covariance and Contravariance feature is well supported in C# and Java collections. However C++ doesn't support them in their STL containers. Why is it so?

For example the below code will compile in C# and Java but not in C++. (The syntax will have to be translated to the specific language though)

class Base
{

};

class Child : public Base
{

};

int main()
{
    std::vector<Base*> baseArray;
    std::vector<Child*> ChildArray;

    baseArray = ChildArray;

    return 0;
}
  • 4
    The C# counterpart of std::vector is List<T> which is invariant so your example would not compile. – Lee Oct 3 '19 at 16:31
  • The question of "why does language X not support feature Y?" is vague and not answerable. Language designers are not required to provide an explanation for why they did not do work that you happen to think they ought to have done, any more than you are required to provide explanations for "why not" questions I could ask you, like "why do you not live on a farm in France?" or "why did you not buy a car on January 3rd of last year?" You can clarify the question by phrasing it as a "what" question. – Eric Lippert Oct 3 '19 at 20:26
  • @EricLippert I agree to your argument but with due respect disagree to your conclusion. To a question "why do you not live on a farm in France?", a fairly acceptable answer could be "coz i can't afford it there" but it may not be agreeable to say that "coz the moon is blue" :) – Sisir Oct 4 '19 at 8:46
  • With this question, I am trying to understand 2 things actually: 1) Is it not possible to implement it in C++ due to the design of the language or it was just that the language designers thought to leave it aside for now? 2) How does C++ solve the problem that covariance is meant to solve? – Sisir Oct 4 '19 at 8:52
  • 2
9

The reason is the underlying object and memory models.

To simplify the reasoning:

  • In java and C#, objects of a class are managed by reference. Containers do not store directly the object value but a reference that says where to find the value. It is therefore technically easy to mix objects of different types in the same container (polymorphism) or to use the container for objects of covariant types. The only constraint is the language semantics. This facilitates significantly the implementation of covariant containers.

  • In C++, objects are managed by value, following the rules of its memory model, which basically requires that objects of a given type a stored within a fixed size (which of course can contain pointers to elements having a dynamic size). A container therefore has to know the type of its objects at compile-time. Unfortunately (or not) C++ also allows for separate compilation. So when you compile a container for Animals in one translation unit, the compiler might not know the size of a Cat (which might not even yet be developed). All this makes it extremely difficult to implement covariance in the language.

Interestingly, in C# you can have objects that are managed by value (in the case of a struct). But as this Microsoft documentation and this SO question explain, variance only applies to reference types.

Of course, all this is simplified explanations and language-lawyers could argue on some details, but i hope it helps to grasp the idea.

  • 1
    The optimism is that C++11 makes it possible to create containers that allow some static and dynamic casting during assignments and transfers. This article outlines the knowledge and techniques needed to create such containers. Of course it requires items to be stored via a reference type. An actual implementation may not be as efficient as a standard vector that stores data by value (it will be heavier in number of memory allocations) but it will make some programming tasks easier. – rwong Oct 4 '19 at 3:27
  • @rwong thank you for sharing this interesting article! Indeed, the use of containers of smart pointers is a common practice when a polymorphism is required. It is a powerful workaround for the missing covariance. Nevertheless not so easy to use as native language support. – Christophe Oct 4 '19 at 5:35
  • @Christophe: So by this, containers when used with pointers or reference types can be implemented to allow covariance in C++ as well for polymorphic reasons, right? – Sisir Oct 4 '19 at 13:17
  • 2
    Like you said, C# doesn't support variance for value types, only for reference type. Similarly, couldn't C++ have supported variance only for pointer types? – svick Oct 5 '19 at 9:01
  • 1
    @svick C++ does support variance for pointer types and reference types. std::vector<Base *> isn't a pointer or reference type. You can write a MyVector such that MyVector<Base *> bases; MyVector<Child *> children; bases = children; copies the contents, and that's fine because you can't add an OtherChild * into children via bases, because they remain distinct objects – Caleth Jan 31 at 10:46
4

C++ templates are invariant. In other words, they don't support covariance or contravariance.

So, the reason, STL containers are not covariant, is because C++ doesn't support that.

Note that std::vector is mutable, so it cannot be covariant anyway, it needs to be invariant, otherwise it wouldn't be type-safe.

  • 2
    3 things; i know they are invariant and that's why the question is why are they invariant? Second is, even the List<T> or ArrayList<T> from C# and Java are mutable right? WHat has mutability to do with variance? – Sisir Oct 3 '19 at 15:38
  • They are invariant because that's the only thing C++ supports. They can't be covariant because C++ doesn't support covariance. – Jörg W Mittag Oct 3 '19 at 15:53
  • @Sisir: The covariance of arrays in C# was introduced before generics were available; however, it's problematic. If you do baseArray = childArray, then you can do the assignment baseArray[i] = instanceOfBase (where instanceOfBase is not an instance of Child), and crash your program (see this. – Filip Milovanović Oct 3 '19 at 15:54
  • 5
    @Sisir: "WHat has mutability to do with variance?" – Umm … everything? At least, when talking about collections. Read-only collections can be covariant, write-only collections can be contravariant, mutable collections must be invariant because neither covariance nor contravariance are type-safe. – Jörg W Mittag Oct 3 '19 at 16:11
  • 2
    @Sisir: "1 more this is there something as a write-only collection" – Sure: an output stream, a logger, a Set (if you interpret a set as its characteristic function, then you can only add items to the set and ask the set whether the item is in there, but you can't take out an item or enumerate the set). – Jörg W Mittag Oct 3 '19 at 16:50
1

In Java, generics are invariant; you would need to use bounded wildcards to achieve covariance or contravariance. To do what you want, in Java it would need to be declared like this:

List<? extends Base> baseArray;
List<Child> childArray;
baseArray = ChildArray;

By using the ? extends wildcard, Java prevents you from adding any elements other than null into the list using the reference of type List<? extends Base>, since the wildcard stands for an unknown type and you don't know that what you're adding is an instance of that type. You can only get elements out of it.

(It is true that arrays in Java are covariant, but it seems like you are talking about generic containers here, not arrays.)

C++ doesn't have bounded wildcards. The most common use case of bounded wildcards in Java is when you accept a collection parameter that the method only needs to read out of, so it doesn't really care about the exact type argument, only that the type argument is a particular type or its subtype:

void printListOfBase(List<? extends Base> list) {
    // you can call methods of Base on the elements of list
}

In C++, you can achieve the same thing with templates without needing any bound, because C++ template instantiations are "duck-typed". Unlike in Java, where a generic class or method is only compiled once and you must prove to the compiler when compiling the class/methd that what you are doing is type-safe giving the bounds, in C++, a templated class or function is compiled separately for each instantiation (i.e. each type argument used), and so the compiler can check when compiling a specific instantiation whether the type works or not, without needing bounds specified beforehand:

void printListOfBase<T>(std::vector<T> list) {
    // you can call methods of Base on the elements of list
    // and it will compile as long as T has such a method
}

As for your particular case of having a local variable of a wildcard-parameterized type, that is much less common and there is no direct equivalent for it in C++.

1

In C# and Java, when you do x = y;1, you now have (at least) two names for the same Object. In C++ you still have two distinct objects, but some code ran and they presumably have the same value now.

The semantics of baseArray = ChildArray in C++ would be very different if it were allowed, it would be a copy operation.

You can copy the contents of ChildArray into baseArray, but not with =

baseArray.assign(ChildArray.begin(), ChildArray.end());

The boost library has a helper for situations like this

#include <boost/range/iterator_range.hpp>

baseArray = boost::copy_range<decltype(baseArray)>(ChildArray);

Footnote 1: Assuming x and y aren't primitives. In that case it matches the C++ case.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.