Ideally, in a OO language, what I want is to be able author a single class, but then "overload on immutable", so to speak. So there are some class members that are shared for both implementations, and then there are some that are only there when the object is mutable, or is immutable (in the most extreme case, there are no shared data members or method implementations at all, and only the API is common).
That would imply that a class definition effectively implicitly defines a trait derived from the common members - e.g. "Vector", having operations such as "size" or "[index]" - and then two distinct classes, e.g. "mutable Vector" and "immutable Vector", both implementing the trait, and providing some extra APIs where that makes sense.
This would be helped a lot by a full decoupling of classes from types, as some modern (and not so modern - e.g. OCaml is practically a golden standard here) languages do.