Hacker News new | past | comments | ask | show | jobs | submit login
Covariance and Contravariance in C++ Standard Library (cpptruths.blogspot.com)
36 points by ingve on Nov 15, 2015 | hide | past | web | favorite | 4 comments

It is probably worth mentioning that the standard containers (and in general, any mutable container) cannot be covariant in their element type without compromising soundness. A vector<Circle•> should not have a push_back(Shape•) member function inherited from vector<Shape•>. (However, a vector<Circle•> could be safely copied to a vector<Shape•> via an implicit conversion.) Java arrays infamously covary, leading to dreaded ArrayStoreExceptions if misused.

(Edit: any way to write literal asterisks in HN?)

Java has a nice solution: An ArrayList<Ellipse> is an ArrayList<? extends Shape>. But it is also an ArrayList<? super Circle>.

The former is "read-only" (can read elements which are all guaranteed to be shapes). The latter is "write-only" (we can add circles to it, but not all elements in it are guaranteed to be circles).

I use quotes because it is not strictly true, but any writes or reads will be of the sort that they don't cause type problems. For instance you can call clear() on a ArrayList<? extends Shape>

Yeah I was really surprised to see a significant post on this with no mention of the hilarious dangers of variance, sharing, and overwrite-ability.

In Rust it ends up actually being pretty clean because mutability is inherited. Generic values are covariant because (as you note), they're by definition unshared. &T is covariant in T because you can't mutate T through an &. &mut T is invariant in T because you can mutate through it.

This therefore enables one to pass &Collection<T> where &Collection<U> is expected if T is a subtype of U, because we know the collection only supports "read only" operations. It's been a while since I've used C++ and never really touched const stuff, but if it works like Rust, that means a `Vector<T> &const` could be soundly covariant. It wouldn't work if you could get `T*`'s out of a `Vector<T> &const`.

That said, we don't have OOP-style inheritance in Rust, so variance only applies to lifetimes. This allows you to pass an &LongLived where an &ShortLived is expected.

I give a basic rundown here: https://doc.rust-lang.org/nightly/nomicon/subtyping.html

Note that I deviate from the academic standard and simply use "variance" for covariance, because the academic terms are dumb and confusing (so many Rust devs, even with PL backgrounds, were constantly getting confused when we used that terminology). Also you don't really need to care about contravariance anyway because it's also dumb and confusing (as this post notes).

The heavy asterisk didn't seem to work but this asterisk operator does: ∗. std::vector<const char ∗> to a foo bar.

Applications are open for YC Summer 2019

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact