Why can't I pass std::vector<Child*> as std::vector<Parent*>?

Introduction

This is a short post reflecting on some pretty basic C++ that bothered me because I felt like I didn't fully understand it. I felt that the language should be able to do more, and wanted to understand why it could not.

Subtype polymorphism and templates

In C++, subtype polymorphism allows pointers and references of child classes to be treated as their parents¹:

 1 class Parent;
 2 class Child : public Parent;
 3 
 4 void foo(Parent*);
 5 
 6 int main() {
 7     Child* child = new Child();
 8     foo(child);
 9     // ...
10 }

This is at the core of Object Oriented style programming in C++, and, like all forms of polymorphism, allows us to write code that is only tied to an interface, not its implementations. We can swap out implementations easily, making the code more flexible, as well as more testable: test doubles that implement the interface can be injected during tests.

C++ also provides another mechanism for polymorphism: templates. Templates allow us to parameterise interfaces by type. The template std::vector describes a growable list and is parametrised by the type the list contains.

Unfortunately, in C++, you cannot combine these two forms of polymorphism in a way that you might like to.

1 void bar(const std::vector<Parent*>&);
2 
3 int main() {
4     std::vector<Child*> children = {new Child()};
5     bar(children);  // Ill-formed (won't compile)
6     // ...
7 }

It's easy to explain this by pointing out that std::vector<Child*> does not inherit from std::vector<Parent*>, and so why would you expect to be able to use them interchangeably?

This explanation makes sense intuitively, but I found it to be lacking. I thought about this:

 1 void bar(const std::vector<Parent*>&);
 2 
 3 int main() {
 4     std::vector<Child*> children = {new Child()};
 5     std::vector<Parent*> children_as_parents =
 6         *reinterpret_cast<std::vector<Parent*>*>(&children);
 7     bar(children_as_parents);  // Well-formed (compiles)
 8 
 9     return 0;
10 }

I thought this would be "safe" (we'll see why not below): the memory layout will still be valid, as the vector contains pointers, so accessing elements of the vector would work as expected; and of course, because Child inherits from Parent, accessing the Parent members after the cast would also work as expected.

I thought: if I know that this is safe, why can't the compiler? If the compiler can know that it's safe, why doesn't the language allow it without circumventing the type system with reinterpret_cast?

The first problem: mutability

The example above is not actually safe because the vector is mutable. We could add pointers to other subtypes of Parent to children_as_parents while still being able to access children, which would now be undefined behaviour.

This suggests we could never have std::vector behave the way I've described with subtypes, and immutable containers would be needed instead.

The second problem: template specialization

The reinterpret_cast done above would only work because I know that the implementation of std::vector<Parent*> and std::vector<Child*> is identical.

However, that of course isn't the case in general for templates: part of their function is that you can specialise them for different type arguments.²

 1 template <typename T>
 2 class A {
 3     ...
 4 };
 5 
 6 template <> class A<Parent> {
 7     double m_;
 8 };
 9 
10 template<> class A<Child> {
11     int bar_;
12 };

If you were able to pass A<Child> as if it were A<Parent>, what could that look like?

When a Child object is copied to a Parent object, it is sliced. This just means that any data in the child object that isn't part of Parent is not copied.

 1 class Parent {
 2  public:
 3     virtual int foo() const {
 4         return 0;
 5     }
 6 };
 7 
 8 class Child : public Parent {
 9  public:
10     int foo() const override {
11         return foo_;
12     }
13 
14  private:
15     const int foo_ = 1;
16 };
17 
18 int main() {
19     Child child;
20     Parent parent = child;  // copy -- Child::foo_ is not copied
21     return parent.foo();  // returns 0, not 1
22 }

There's no obvious way for this to work for our template example above: A<Child> does not share the members of A<Parent>, how could it be sliced down?

Even if we were to take a reference (which means no slicing would occur), the problem is essentially the same: A<Parent> could have a method that A<Child> does not have.

A deeply dissatisfying "solution"

Of course, we can still write a function that could take a A<Parent> or A<Child>: with templating:

 1 class Parent {
 2  public:
 3     virtual int foo() const = 0;
 4 };
 5 
 6 class Child {
 7  public:
 8     int foo() const override {
 9         return 1;
10     }
11 };
12 
13 template <typename T>
14 int func(const std::vector<T*>& vec) {
15     return vec[0]->foo();
16 }

But what I wanted was to be able to express that my function can take a vector of any type that implements Parent. This doesn't express that. There's no way in C++ to explicitly constrain the types on templates. In C++20, concepts provide a minimal way to do this³, but:

• Concept constraints are implicitly met, not explicitly implemented

• Concepts are orthogonal to the subtype polymorphism I want to ergonomically take advantage of.

A summary

Ultimately, the explanation of why you can't pass std::vector<Child*> as std::vector<Parent*> is really the same explanation we had at the start: you can't pass templates of subtypes as templates of parents because the template itself is not a subtype.

But really, a more meta-explanation is that C++ lacks the ability to constrain template type arguments. This makes templates inherently inexpressive, and makes it difficult to harmoniously use templates with inherited types.

This is one place where Rust shines in comparison to C++.

A better world

I really like the way Rust approaches polymorphism. Traits are Rust's only mechanism for polymorphism. They provide a unified way for specifying both static and dynamic interfaces. They facilitate designs based on composition, reducing coupling. They allow for explicit constraint of type arguments in generics.⁴

In Rust, we can express the equivalent of what we wanted above easily:⁵

 1 trait Mag {
 2     fn magnitude(&self) -> f32;
 3 }
 4 
 5 struct Point {
 6     x: f32,
 7     y: f32,
 8 }
 9 
10 impl Mag for Point {
11     fn magnitude(&self) -> f32 {
12         f32::sqrt((self.x * self.x) + (self.y * self.y))
13     }
14 }
15 
16 fn magnitude_of_first<T>(vec: &Vec<T>) -> f32
17 where
18     T: Mag,
19 {
20     vec[0].magnitude()
21 }
22 
23 fn main() {
24     // The type hint is here for illustrative purposes
25     let v: Vec<Point> = vec![Point { x: 0.0, y: 1.0 }, Point { x: 2.0, y: 3.0 }];
26     dbg!(magnitude_of_first(&v));
27 }

This is the power of a more expressive type system, which to me is such a crucial part of a programming language. C++'s type system always falls flat for me, for many reasons: the limited expressiveness shown above; the lack of a way for the type system to to track object lifetime, so we have a library of smart pointers instead which can easily be abused; implicit type conversion that can make code less clear and cause bugs; references that are taken implicitly; a confusing value taxonomy.

I am definitely complaining here; but I also think part of developing a good understanding of a system is understanding its limitations, being able to understand why some things aren't possible, and knowing what a different system would (or does!) look like. I hope this Rust example has helped with that.

As always, if you have any C++ insight to share I'd appreciate it: it's a complex topic and I always have more to learn :)

Update 26th July 2020: variance

Matthew Fernandez kindly sent me this blog post about the concept of type variance, which gives us a more formal language to talk about some of the ideas discussed in this blog post, namely that C++ templates are invariant. I desired for them to be covariant.

From the linked blog post, "variance refers to how subtyping between more complex types relates to subtyping between their components". In Rust, implementing a trait does not create a subtype of that trait, so there's no concept of variance to apply to our example above.⁶

The issue of variance in C++ is relevant due to the use of both templates and subtyping; Rust's unified mechanism for polymorphism, with explicitly met constraints on type arguments, avoids this issue.